けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Educational Codeforces Round 73 F. Choose a Square (R2500)

区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする!!!

問題へのリンク

問題概要

二次元平面上の  N 点が与えられる (いずれも  x, y 座標が 0 以上の格子点)。各点にはスコア  c_i が与えられる。

対角線のうちの一つが  y = x 上にあるような正方形のうち、正方形の内部または辺上の点のスコアの総和から、正方形の一辺の長さを引いた値が最大となるものを求めよ。

制約

  •  1 \le N \le 5 \times 10^{5}

考えたこと

一見絶望的な気持ちになったのだが

  • 二次元平面上の頂点
  • 区間

とが一対一対応していて、一方を他方に置き換えることで問題の見通しがよくなることがよくある。今までは区間を平面上の点とみることで見通しよくなるパターンを多く経験してきたけど、今回は平面上の点を区間としてみると見通しがよくなる。

各点  (x_i, y_i)区間 [  x_i, y_i ] とみなすことができる ( x_i \gt y_i だったら区間 [  y_i, x_i ])。そして正方形もまた区間 [  l, r ) と考えることができる。

そうすると、問題は

  •  N 個の区間が与えられる
  • 区間であってそこに含まれる区間のスコアん総和から、区間の長さを引いた値が最大となるものを求めよ

という問題と考えることができる。

平面走査へ

区間に関する問題だと思えたならば、区間を始点または終端でソートするのが定石。ここでは始点でソートしてみる。そして

をすべて考えてスコアが最大のものを求めればよいことになる (与えられた区間の始点終点は始点・終点とよび、問題で考える区間の始点終点は左側・右側とよぶことにする)。ここで、

  • まず最も左にある区間の始点を左側として固定したとき
  • 右側を各区間の終端に設定した場合のスコアを一旦求めておく

ことにする。そして左側を少しずつ右へ持って行ったときに、各右側のスコアは自然に更新していくことができる。具体的には左側を右に動かしたことによって、区間 [s, t) の s が外れるとき、t よりも右側にある点についてはその区間のスコアを引くことになる。よって

  • 区間加算 (全体として  N 回実施することになる)
  • 区間最大値

を求めることのできるセグメントツリーが欲しい。遅延評価つきの Starry Sky Tree がピッタリである。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 区間加算と、区間最大値取得
template<class Monoid, class Action> struct StarrySky {
    const Monoid INF;
    const Action ZERO;
    int SIZE;
    vector<pair<Monoid, int> > dat;
    vector<Action> lazy;
    
    StarrySky(int n, const Monoid &inf, const Action &zero) : INF(inf), ZERO(zero) {
        init(n);
    }
    void init(int n) {
        SIZE = 1;
        while (SIZE < n) SIZE <<= 1;
        dat.assign(SIZE * 2, {-INF, -1});
        lazy.assign(SIZE * 2, ZERO);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE] = {v, a}; }
    void build() {
        for (int k = SIZE - 1; k > 0; --k)
            dat[k] = max(dat[k*2], dat[k*2+1]);
    }
    
    /* update [a, b) */
    inline void evaluate(int k) {
        if (lazy[k] == ZERO) return;
        if (k < SIZE) lazy[k*2] += lazy[k], lazy[k*2+1] += lazy[k];
        dat[k].first += lazy[k];
        lazy[k] = ZERO;
    }
    inline void update(int a, int b, const Action &v, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b) lazy[k] += v, evaluate(k);
        else if (a < r && l < b) {
            update(a, b, v, k*2, l, (l+r)>>1), update(a, b, v, k*2+1, (l+r)>>1, r);
            dat[k] = max(dat[k*2], dat[k*2+1]);
        }
    }
    inline void update(int a, int b, const Action &v) { update(a, b, v, 1, 0, SIZE); }
    
    /* get [a, b) */
    inline pair<Monoid,int> get(int a, int b, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b)
            return dat[k];
        else if (a < r && l < b)
            return max(get(a, b, k*2, l, (l+r)>>1), get(a, b, k*2+1, (l+r)>>1, r));
        else
            return {-INF, -1};
    }
    inline pair<Monoid,int> get(int a, int b) { return get(a, b, 1, 0, SIZE); }
    inline Monoid operator [] (int a) { return get(a, a+1).first; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE; ++i) { cout << (*this)[i]; if (i != SIZE) cout << ","; }
        cout << endl;
    }
};


const long long INF = 1LL<<60;
using pll = pair<long long, long long>;
using Item = pair<pll, long long>;

int main() {
    int N; cin >> N;
    vector<Item> v(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i].first.first >> v[i].first.second >> v[i].second;
        if (v[i].first.first > v[i].first.second)
            swap(v[i].first.first, v[i].first.second);
    }
    sort(v.begin(), v.end());

    // 座標圧縮
    vector<long long> alt;
    for (int i = 0; i < N; ++i) {
        alt.push_back(v[i].first.first);
        alt.push_back(v[i].first.second);
    }
    sort(alt.begin(), alt.end());
    alt.erase(unique(alt.begin(), alt.end()), alt.end());
    alt.push_back(alt.back() + 1);

    // 区間の始点終点で整理
    int M = alt.size();
    vector<vector<int> > ends(M+1), starts(M+1);
    for (int i = 0; i < N; ++i) {
        int right = lower_bound(alt.begin(), alt.end(), v[i].first.second) - alt.begin();
        int left = lower_bound(alt.begin(), alt.end(), v[i].first.first) - alt.begin();
        ends[right].push_back(i);
        starts[left].push_back(i);
    }

    // 初期状態
    StarrySky<long long, long long> ss(M+1, INF, 0);
    long long sum = 0;
    for (int i = 0; i < M; ++i) {
        long long len = alt[i] - alt[0];
        for (auto id : ends[i]) sum += v[id].second;
        ss.set(i, sum - len);
    }
    ss.build();
    auto cur = ss.get(0, M);
    long long res = cur.first;
    int rx = alt[0];
    int ry = alt[cur.second];

    // 区間の左側を一通り試す
    for (int i = 1; i < M; ++i) {
        long long lenadd = alt[i] - alt[i-1];
        ss.update(i, M, lenadd);
        for (auto id : starts[i-1]) {
            int right = lower_bound(alt.begin(), alt.end(), v[id].first.second) - alt.begin();
            ss.update(right, M, -v[id].second);
        }
        auto cur = ss.get(i, M);
        if (res < cur.first) res = cur.first, rx = alt[i], ry = alt[cur.second];
    }
        
    cout << res << endl;
    cout << rx << " " << rx << " " << ry << " " << ry << endl;
}

Educational Codeforces Round 73 E. Game With String (R2400)

面白かったけど場合分けが怖かった

問題へのリンク

問題概要

"...X......XX..X..X.XXX...X..."
のような '.' と 'X' からなる長さ  N の文字列が与えられる。

  • 先手は連続する  a 個の '.' をすべて 'X' に置き換える
  • 後手は連続する  b 個の '.' をすべて 'X' に置き換える

という操作を交互に行う。先に操作を行えなくなった方が負け。双方最善を尽くしたとき、どちらが勝つか?

ただし、 a \gt b であることが保証されているものとする。

制約

  •  1 \le (クエリ数) \le 3 \times 10^{5}
  •  1 \le N \le 3 \times 10^{5}
  •  (全クエリの N の総和) \le 3 \times 10^{5}

考えたこと

やはり  O(N) O(N\log{N}) くらいで解ければ OK。
すごくややこしいし、一見 Grundy っぽさ (盤面が本質的に分裂していくため) もあるのだけど、不公平ゲームだし Grundy はそのままでは扱いづらい。

ちょっとアドホックにいろいろ考えてみよう。少しわかってくるのは

  • 先手が初手何も打てなかったらどうしようもない
  • もし長さが  b 以上  a 未満の区間があったらその時点で先手はどうしようもない
  • 先手が手を打ったあとにもし長さが  2b 以上の区間があったらその時点で先手はどうしようもない (後手が必ず長さ  b区間を作れるため)

ということがわかる。よって解法としては、長さ  b 以上  a 未満の区間がないことを確認した上で、長さ  a 以上の区間 ( M 個とする) の長さを抜き出してきて、

  • 空だったらアウト
  • その中に長さ  2b 以上の区間が 2 個以上あったらアウト
  • 長さ  2b 以上の区間が 1 個含むときは、なんとかそれを解体しなければならない (後述)
  • 長さ  2b 以上の区間がなければ、 M が奇数個なら先手勝ち、偶数個なら後手勝ちになる。

長さ  2b 以上の区間が 1 個だけ含まれるとき

ここの場合分けはあまりにもしんどいので、こういうときは探索に頼ってしまってよいと思う!!!!!!!探索量は  N でおさえられるので、 O(N) で済む。

すなわち、長さ  2b 以上の区間に対して長さ  a区間をどのように置くかを全探索する。各場合について

  • もし長さ  2b 以上の区間が再び生じたらダメ
  • もし長さ  b 以上  a 未満の区間が生じたらダメ
  • そうでなければ、分割後に「長さ  a 以上の区間の個数」がどうなったかを数えて、それが偶数だったら先手勝ち

全探索して先手勝ちになるパターンが存在しなかったら、後手勝ち。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool solve(long long a, long long b, const string &S) {
    vector<long long> v;
    int N = S.size();

    // ... を区間ごとに切り出す
    for (int i = 0; i < N; ++i) {
        if (S[i] == '.') {
            int j = i + 1;
            while (j < N && S[j] == '.') ++j;

            // b 以上 a 未満あったら負け
            if (j - i >= b && j - i < a) return false;

            if (j - i >= a) v.push_back(j - i);
            i = j;
        }
    }
    sort(v.begin(), v.end(), greater<long long>());
    
    // 初手何もできなかったら負け
    if (v.empty()) return false;

    // 2b 以上を残したら負け (まず 2b 以上が 2 箇所以上あったら負け)
    if (v.size() >= 2 && v[1] >= b*2) return false;

    // 全探索 (v[0] を分割する)
    for (long long i = 0; i + a <= v[0]; ++i) {
        long long j = v[0] - i - a;

        // 2b を与えてはいけない
        if (i >= b*2 || j >= b*2) continue;

        // b 以上 a 未満を与えてはいけない
        if (i >= b && i < a) continue;
        if (j >= b && j < a) continue;

        // 操作後に「a 以上」の区間が何個残るかを数える
        int con = 0;
        if (i >= a) ++con;
        if (j >= a) ++con;
        con += (int)v.size() - 1;
        if (con % 2 == 0) return true;
    }
    return false;
}

int main() {
    int CASE; cin >> CASE;
    while (CASE--) {
        long long a, b; string S;
        cin >> a >> b >> S;
        if (solve(a, b, S)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Educational Codeforces Round 73 D. Make The Fence Great Again (R1700)

いかにも Greedy にできなさそうなので DP!!!

問題へのリンク

問題概要

長さ  N の整数数列  a_1, a_2, \dots, a_N が与えられる。今、数列の各項の値を整数分だけ増加させるなどして、数列のどの隣り合う二項も値が異なるようにしたい。

 i 項目を 1 増加させるのに要するコストは  b_i で与えられる。目的を達成するための最小コストを求めよ。

制約

  •  1 \le (クエリ数) \le 3 \times 10^{5}
  •  1 \le N \le 3 \times 10^{5}
  •  (N の総和) \le 3 \times 10^{5}

考えたこと

 O(N) で解ければ OK。こういうの、まずは Greedy に...とつい考えてしまう。しかし (2, 2, 3, 3) と並んでるところを、(3, 2, 4, 3) とか (2, 4, 3, 4) とかなんか色々なパターンが考えられて、やばそう

そこで DP できないか考えてみる。そしてちょっと考えると、

  • どの項も 3 以上増やす必要はない

ということがわかる。なぜなら、その項の左右の項がどのような状態であったとしても、

  • 「+0」 (そのまま)
  • 「+1」
  • 「+2」

の 3 種類のうちのどれかは被らずに生き残るからだ。よって「+3」するメリットはない。

DP へ

ここまでくれば、もうこの問題と一緒。

  • dp[ i ][ 0, 1, 2 ] := 最初の i 項について、最後の項を「+0」「+1」「+2」それぞれの場合についての、最小コスト

として DP すれば OK。

atcoder.jp

#include <iostream>
#include <vector>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
int CASE;

int main() {
    cin >> CASE;
    while (CASE--) {
        int N; cin >> N;
        vector<long long> a(N), b(N);
        for (int i = 0; i < N; ++i) cin >> a[i] >> b[i];

        vector<vector<long long> > dp(N+1, vector<long long>(5, INF));
        dp[0][0] = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= 2; ++j) {
                for (int k = 0; k <= 2; ++k) {
                    if (i > 0 && a[i-1] + j == a[i] + k) continue;
                    chmin(dp[i+1][k], dp[i][j] + b[i] * k);
                }
            }
        }
        long long res = INF;
        for (int j = 0; j <= 2; ++j) chmin(res, dp[N][j]);
        cout << res << endl;
    }
}

Educational Codeforces Round 73 C. Perfect Team (R1200)

ペアリング系の問題

問題へのリンク

問題概要

以下の問題が  Q 問出題されるのでそれぞれ答えよ:

  • コーダーが  c 人、数学に強い人が  m 人、なんでもない人が  x 人いる
  • ここからコーダー 1 人以上、数学強い人が 1 人以上を含む 3 人チームを最大何組できるか求めよ

考えたこと

  • コーダーや数学人材的に、min(c, m) 組しか作れない
  • また (c + m + x) / 3 組までしか作れない

これらの小さい方を答えれば OK。

たとえば  c = 5, m = 3, x = 100 だったら、そもそも数学に強い人が 3 人しかいないので 3 チームしか作れない。 c = 3, m = 5, x = 100 だったら、コーダーが 3 人しかいないので 3 チームしか作れない。

反対に  c m も大きいが  x が足りないケースもある。たとえば  c = 70, m = 70, x = 1 の場合、コーダーも数学に強い人も潤沢にいるが、結局 (70 + 70 + 1) ÷ 3 = 47 チームしか作れない。

#include <iostream>
#include <string>
using namespace std;

int CASE;
long long c, m, x;

long long solve() {
    long long res = min(c, m);
    res = min(res, (c+m+x)/3);
    return res;
}

int main() {
    cin >> CASE;
    while (CASE--) {
        cin >> c >> m >> x;
        cout << solve() << endl;
    }
}

AOJ 2712 Escape (JAG 夏合宿 2015 day2G)

こどふぉでまったく同じ問題が出た!!!
始点の入力の仕方が異なるのみ (こっちでは始点はノード 1 に固定、こどふぉでは始点 s を入力で与える)

drken1215.hatenablog.com

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M, S = 0;
vector<long long> w;
using Graph = vector<vector<int> >;
Graph G;

void dfs(vector<int> vs, vector<long long> &dist) {
    for (auto v : vs) {
        for (auto nv : G[v]) {
            if (dist[nv] != -1) continue;
            dist[nv] = dist[v] + w[nv];
            dfs({nv}, dist);
        }
    }
}

long long solve() {
    vector<int> deg(N, 0);
    for (int v = 0; v < N; ++v) {
        for (auto nv : G[v]) {
            ++deg[v];
            ++deg[nv];
        }
    }
    for (int v = 0; v < N; ++v) deg[v] /= 2;

    queue<int> que;
    for (int v = 0; v < N; ++v) if (v != S && deg[v] == 1) que.push(v);

    vector<bool> fucked(N, false);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        fucked[v] = true;
        for (auto nv : G[v]) {
            --deg[nv];
            if (nv != S && deg[nv] == 1) que.push(nv);
        }
    }

    long long res = 0;
    vector<int> vs;
    vector<long long> dist(N, -1);
    for (int v = 0; v < N; ++v) if (!fucked[v]) {
            res += w[v];
            vs.push_back(v);
            dist[v] = 0;
        }

    dfs(vs, dist);
    long long ma = 0;
    for (int v = 0; v < N; ++v) ma = max(ma, dist[v]);
    return res + ma;
}


int main() {
    cin >> N >> M;
    w.resize(N);
    for (int i = 0; i < N; ++i) cin >> w[i];
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    cout << solve() << endl;
}