Ccmmutty logo
Commutty IT
・19 min read

水色コーダーが ABC 全問解説する【ABC278】

競技プログラミングAtCoderAtCoderBeginnerContest
https://cdn.magicode.io/media/notebox/a18a98c4-2073-4ddc-9c3d-13bd6986da5f.jpeg

AtCoder Beginner Contest 278

5 完の水パフォでした。5 完は最速でも水パフォだし、6 完しなきゃいけないやつだった…(´・ω・｀)

A - Shift

「公式解説のように地道に 22 重ループで解く」とか、「先頭の要素の削除と末尾への要素の追加ができるクラスを使う」とか、「kk 回操作を行うとどうなるかを考えたりする」とかで解ける。
22 重ループのやつは公式解説にまかせて、他の 22 つを置いときますね。
まずは、「先頭の要素の削除と末尾への要素の追加ができるクラスを使う」やつ。vector とか queue とか deque とか。まあ、vector は「先頭の要素の削除」に O(N)O(N) かかるので、両方の操作を O(1)O(1) でできる queue とか deque とかを使うといいかな。queue は配列みたいに a[i] とかで値を取得できないので、今回の場合、deque が便利そう。
↓ で、こんな感じ。オーダーは O(N+K)O(N+K) かな。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;

    cin >> n >> k;

    deque<int> a(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < k; ++i) {
        a.pop_front();
        a.push_back(0);
    }

    for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';
    }
}
次は、「kk 回操作を行うとどうなるかを考えたりする」やつ。
kk 回操作すると、AA は、(A1+K,A2+K,…,AN+K)(A_{1+K}, A_{2+K}, \ldots , A_{N+K}) になる。(ただし、Ai=0A_i=0 (i>N)(i > N)。)
なので、1+K>N1+K>N (⇔K≧N)(\Leftrightarrow K \geqq N) のとき、AA の要素は全部 00。そうでなければ、(A1+K,A2+K,…,AN,0,…,0)(A_{1+K}, A_{2+K}, \ldots , A_N, 0, \ldots , 0)。
↓ こんな感じ。オーダーは O(N)O(N)。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, k;

    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (k >= n) {  // K >= N なら全部 0
        for (int i = 0; i < n; ++i) cout << 0 << ' ';
    } else {  // そうでないなら K+1 ~ N (0-indexed なら K ~ N-1) まで出力 (残りは 0)
        for (int i = k; i < n; ++i) cout << a[i] << ' ';
        for (int i = 0; i < k; ++i) cout << 0 << ' ';
    }

    return 0;
}

B - Misjudge the Time

時刻が AB\text{AB} 時 CD\text{CD} 分のとき、AC\text{AC} 時 BD\text{BD} 分も時刻に見えるか、つまり、A×10+C<24\text{A} \times 10+\text{C} < 24 かつ B×10+D<60\text{B} \times 10+\text{D} < 60 かどうかを判断すればいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int h, m;

    cin >> h >> m;

    int M = m;  // 最初は m 分からのループ
    for (int i = h;; i = (i + 1) % 24) {  // 無限ループ (i = h, h + 1, …, 23, 0, …)
        int a = i / 10, b = i % 10;

        for (int j = M; j < 60; ++j) {  // 最初は m それ以外は 0 からスタート
            int c = j / 10, d = j % 10;

            if (a * 10 + c < 24 && b * 10 + d < 60) {
                cout << i << ' ' << j;
                return 0;  // 無限ループなので答えが見つかったら終了させる
            }
        }
        M = 0;  // 以降 0 分からのループ
    }

    return 0;
}
↓ 11 重ループでも。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int h, m;

    cin >> h >> m;

    // 時刻 (60 進数) を 10 進数に変換して 1 重ループに
    for (int i = h * 60 + m;; i = (i + 1) % (24 * 60)) {  // 無限ループ
        int H = i / 60, M = i % 60;  // 時刻 (60 進数) に戻す
        int a = H / 10, b = H % 10;
        int c = M / 10, d = M % 10;

        if (a * 10 + c < 24 && b * 10 + d < 60) {
            cout << H << ' ' << M;
            return 0;  // 無限ループなので答えが見つかったら終了させる
        }
    }

    return 0;
}

C - FF

N≤109N \leq 10^9 なので、全員分管理するのは無理。Q≤2×105Q \leq 2 \times 10^5 なので、フォローする側を AA、フォローされる側を BB とした組 (A,B)(A, B) を与えられた分だけ管理すればいい。「(A,B)(A, B) がフォロー状態」かつ「(B,A)(B, A) がフォロー状態」なら "Yes"、違うなら "No" を出力すれば OK。組を管理するなら連想配列のクラスを使うと便利。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q;

    cin >> n >> q;

    // true ならフォローしている
    map<pair<int, int>, bool> follow;
    // 配列の値が bool 値なので、map を set に置き換えて、
    // bool 値を要素の有無に置き換えることも可能

    for (int i = 0, t, a, b; i < q; ++i) {
        cin >> t >> a >> b;
        if (t == 1) {
            follow[{a, b}] = true;  // a が b をフォローした
        } else if (t == 2) {
            follow[{a, b}] = false;  // a が b をフォロー解除した
        } else if (t == 3) {
            // 「a が b をフォローしている」かつ「b が a をフォローしている」
            // なら "Yes"、違うなら "No"
            cout << (follow[{a, b}] && follow[{b, a}] ? "Yes" : "No") << '\n';
        }
    }

    return 0;
}

D - All Assign Point Add

遅延セグ木のテンプレ。D 問題で遅延セグ木はないかぁ(._.)　操作 11 をそのままやると O(N)O(N) なので、O(Q)O(Q) 回やると間に合いません。代入 (操作 11) は操作 22 か操作 33 の直前に実行されていれば十分なので、操作 22 か操作 33 のときに、操作 22 か操作 33 で指定された要素にだけ代入すれば、クエリ毎に O(1)O(1) で済む。「最後に操作 11 が現れたときのクエリ番号」と、要素ごとの「代入したときのクエリ番号」を保持しておけば、代入済みかどうか判断できる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, q;
    int num;         // 操作 1 で代入する値
    int reset = -1;  // 操作 1 が最後に現れたのは何番目のクエリか

    cin >> n;

    vector<ll> a(n);
    vector<int> updated(n, -1);  // 何番目のクエリのときに代入したか
    for (int i = 0; i < n; ++i) cin >> a[i];

    cin >> q;
    for (int i = 0, t, index, add; i < q; ++i) {
        cin >> t;
        if (t == 1) {
            cin >> num;  // 代入する値の更新
            reset = i;   // 操作 1 が最後に現れたときのクエリ番号を更新
        } else if (t == 2) {
            cin >> index >> add;
            --index;  // 0-indexed
            if (updated[index] < reset) {  // 最後に代入したときより後に操作 1 が現れていたなら
                a[index] = num;      // 代入する
                updated[index] = i;  // 代入したときのクエリ番号を更新
            }
            a[index] += add;  // 加算
        } else if (t == 3) {
            cin >> index;
            --index;  // 0-indexed
            if (updated[index] < reset) {  // 最後に代入したときより後に操作 1 が現れていたなら
                a[index] = num;      // 代入する
                updated[index] = i;  // 代入したときのクエリ番号を更新
            }
            cout << a[index] << '\n';  // 出力
        }
    }

    return 0;
}

E - Grid Filling

実装がちょっとめんどくさいやつ (このユーザ解説と同じ) を思いついて間に合わなかった…(´・ω・｀)
数字の種類が N≤300N \leq 300 しかないので、数字ごとに 22 次元累積和を取れば、個数の区間和を各数字 O(1)O(1) で求められるので、各数字の個数が 00 かそうじゃないかで種類数をカウントすればいい。すると、すべての (k,l)(k, l) の組について、数字の種類数を O(HWN)O(HWN) で求められる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// 2 次元累積和
void CumulativeSum2D(vector<vector<int>> &a) {
    int h = a.size(), w = a[0].size();

    // 縦に累積和
    for (int i = 1; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            a[i][j] += a[i - 1][j];
        }
    }

    // 横に累積和
    for (int i = 0; i < h; ++i) {
        for (int j = 1; j < w; ++j) {
            a[i][j] += a[i][j - 1];
        }
    }

    return;
}

int main() {
    int H, W, n, h, w;

    cin >> H >> W >> n >> h >> w;

    // 累積和を取りたいので縦横 1 ずつ余分に取る
    vector<vector<vector<int>>> count(
        n, vector<vector<int>>(H + 1, vector<int>(W + 1)));

    // 累積和用に 1-indexed
    for (int i = 1, a; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            cin >> a;
            --a;
            ++count[a][i][j];
        }
    }

    // 数字ごとに累積和
    for (int i = 0; i < n; ++i) {
        CumulativeSum2D(count[i]);
    }

    // 種類数の計算
    for (int k = 0; k <= H - h; ++k) {
        for (int l = 0; l <= W - w; ++l) {
            int ans = 0;  // 種類数
            for (int num = 0; num < n; ++num) {
                // 全区間の和
                int areaAll = count[num][H][W];
                // 塗りつぶす区間の和
                int areaFill = count[num][k + h][l + w] - count[num][k][l + w] -
                               count[num][k + h][l] + count[num][k][l];

                // 塗りつぶしていないマスに num があるなら種類数を 1 加算
                if (areaAll - areaFill > 0) ++ans;
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

F - Shiritori

「22 人対戦のゲームだから Grundy 数だ！」と思って解いたけど、bool 値で事足りるらしい…。 多分、「複数ゲームの同時進行」パターンとか、「11 つのゲームだけど、操作で複数ゲームに分割できる」パターンとかのときに Grundy 数が有効なのかな…？
「複数ゲームの同時進行」パターンの例は、石取りゲームの山が複数あるバージョンとか。「11 つのゲームだけど、操作で複数ゲームに分割できる」パターンの例は、今回の G 問題とか。
せっかく Grundy 数で解いたので、それを置いとく。公式解説では「集合 + 最後の文字」を状態として持ってたけど、文字列の数が N≤16N \leq 16 なので、私は「集合 + 最後に選んだ文字列の番号」を状態として解いた。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// Grundy 数を求めるやつ
// 文字列の数 n、集合 st、最後に選んだ文字列の番号 p、全文字列 s、Grundy 数 grundy
int cal(int n, int st, int p, vector<string> &s, vector<vector<int>> &grundy) {
    // Grundy 数を求め終わっていたらそのまま返す
    if (grundy[p][st] != -1) return grundy[p][st];

    // 全ての文字列を使い切っていたら 0 を返す
    if (st == 0) {
        grundy[p][st] = 0;
        return 0;
    }

    set<int> num;  // 遷移先の Grundy 数
    for (int i = 0; i < n; ++i) {
        if (st & (1 << i)) {  // 文字列 i を使っていないなら
            if (st != ((1 << n) - 1)) {  // しりとりの最初の手番でないなら
                // 最後に選んだ文字列の最後の文字と文字列 i の最初の文字が
                // 等しくないなら continue
                if (s[p][s[p].length() - 1] != s[i][0]) continue;
            }
            // 最後に選んだ文字列の番号を i にして、集合から i を抜いて再帰
            int k = cal(n, st ^ (1 << i), i, s, grundy);
            // 遷移先の Grundy 数に追加
            if (num.find(k) == num.end()) num.insert(k);
        }
    }

    // Grundy 数を求める
    {
        int i = 0;
        // 0 から数字の小さい順に遷移先にその数字があるか調べ、
        // なければそれを Grundy 数として終了し、それを返す
        for (auto itr = num.begin(); itr != num.end(); ++itr) {
            if (*itr != i) {
                grundy[p][st] = i;
                return i;
            }
            ++i;
        }
        grundy[p][st] = i;
        return i;
    }
}

int main() {
    int n;

    cin >> n;

    vector<string> s(n);

    // Grundy 数
    // grundy[最後に選んだ文字列の番号][選んでない文字列の集合]
    // Grundy 数を求める前は -1
    vector<vector<int>> grundy(n, vector<int>(1 << n, -1));

    for (int i = 0; i < n; ++i) cin >> s[i];

    // Grundy 数が 0 なら後手必勝、それ以外なら先手必勝
    cout << (cal(n, (1 << n) - 1, 0, s, grundy) == 0 ? "Second" : "First");

    return 0;
}

G - Generalized Subtraction Game

愚直に Grundy 数を求めると O(N2(R−L))O(N^2(R-L)) だから TLE になるね。(ここまでしか分からなかった。)
「真似っこ戦略」と呼ばれる戦略があるらしい。同じ状態の 22 つのゲームがあったとき、先手が片方のゲームを操作した場合、後手がもう片方のゲームで全く同じ操作をすれば、先手が先に操作不能になるという話っぽい。
つまり、同じ状態の 22 つのゲームに対して、先手が片方のゲームを操作すると同じ状態ではなくなるので、後手が同じ状態に戻すという流れ。Grundy 数を考えてみても、同じ状態の 22 つのゲームの XOR は、同じ数字 22 つの XOR なので 必ず 00 になることがわかり、後手必勝だとわかる。
この問題の場合、NN と 「取り除く枚数」の偶奇を一致させられるなら、11 回目の操作でちょうど真ん中を取り除くことで、同じ状態の 22 つのゲームに分割できる。つまり、先手必勝である。NN と 「取り除く枚数」の偶奇を一致させられない場合というのは、「取り除く枚数」の偶奇を選択できない場合、つまり L=RL = R のときで、かつ、NN と LL の偶奇が一致していないときのみである。
NN と 「取り除く枚数」の偶奇を一致させられるときは、真似っこ戦略を取ればいい。そうでない場合、L=RL = R だから Grundy 数は O(N2)O(N^2) で求められるので間に合う。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// field (カードが存在する区間の集合を [key, value) で管理したもの) の更新
// 更新によって変化した Grundy 数の差分 cmd を返す
// つまり、[更新前の Grundy 数] xor cmd = [更新後の Grundy 数]
// 引数は、操作 x, y、カードが存在する区間の集合 field、Grundy 数 grundy
int updateField(int x, int y, map<int, int> &field, const vector<int> &grundy) {
    auto itr = field.upper_bound(x);  // カード x が存在する区間の次の区間
    --itr;  // カード x が存在する区間に移動

    // 更新によって変化した Grundy 数の差分
    // (itr->second - itr->first は区間の大きさ (カード数))
    int cmd = grundy[itr->second - itr->first];

    /* カード x が存在する区間 [itr->first, itr->second) を                   */
    /* 区間 [itr->first, x) と 区間 [x + y, itr->second) に分割する [ここから] */

    // カードを取り除いた後の右側 (正方向) の区間 [x + y, itr->second) の大きさが 0 でないなら
    if (x + y < itr->second) {
        field[x + y] = itr->second;  // 区間 [x + y, itr->second) の追加
        cmd ^= grundy[itr->second - (x + y)];  // Grundy 数の差分を更新
    }

    // カードを取り除いた後の左側 (負方向) の区間 [itr->first, x) の大きさが 0 なら
    if (itr->first == x) {
        field.erase(itr);  // 区間 [itr->first, itr->second) を消す
    } else {  // 0 でないなら
        itr->second = x;  // 区間 [itr->first, itr->second) を 区間 [itr->first, x) に更新
        cmd ^= grundy[x - itr->first];  // Grundy 数の差分を更新
    }

    /* カード x が存在する区間 [itr->first, itr->second) を                   */
    /* 区間 [itr->first, x) と 区間 [x + y, itr->second) に分割する [ここまで] */

    return cmd;
}

// 自分のターンの操作を実行する
// 引数は、現在の状態の Grundy 数 cmd、取り除くカード数 y、
// 　　　　カードが存在する区間の集合 field、Grundy 数 grundy
void op(int cmd, int y, map<int, int> &field, const vector<int> &grundy) {
    // Grundy 数を 0 にする操作が可能な区間を探す
    auto itr = field.begin();
    int size;  // 区間の大きさ
    int toZero;
    // 区間の Grundy 数 grundy[size] を toZero に遷移させると、
    // 全体の Grundy 数を 0 にできる
    for (; itr != field.end(); ++itr) {
        size = itr->second - itr->first;
        toZero = cmd ^ grundy[size];
        // toZero < [区間の Grundy 数] なら toZero に遷移できるので終了
        if (toZero < grundy[size]) break;
    }
    // 区間の Grundy 数 grundy[size] を操作によって toZero にすると
    // 操作後の全体の Grundy 数が 0 になる

    assert(itr != field.end());  // そのような区間は必ず存在する

    // 操作後のGrundy 数が 0 になるような操作の検索
    for (int i = 0; i <= size; ++i) {
        if ((toZero ^ grundy[i] ^ grundy[size - i - y]) == 0) {  // 見つけたら
            cout << itr->first + i << ' ' << y << endl;  // 操作方法を出力

            // field の更新
            // 操作後の Grundy 数は 0 になるので、[updateField の返り値] == cmd
            assert(updateField(itr->first + i, y, field, grundy) == cmd);
            break;
        }
    }
}

int main() {
    int n, l, r;
    int a, b;

    cin >> n >> l >> r;

    // 「L = R」かつ「N と L の偶奇が一致していない」なら Grundy 数を求める
    if (l == r && (n - l) % 2) {
        // 連続で k 枚並んでいる状態のときの Grundy 数
        vector<int> grundy(n + 1);

        // Grundy 数を求める
        for (int i = 1; i <= n; ++i) {
            if (i - l < 0) continue;  // 取り除けないなら grundy[i] == 0;
            vector<bool> num(n);
            for (int j = 0; j <= i - l; ++j){
                num[grundy[j] ^ grundy[i - l - j]] = true;
            }
            for (; grundy[i] < n; ++grundy[i]) {
                if (!num[grundy[i]]) break;
            }
        }

        map<int, int> field;  // カードが存在する区間の集合を [key, value) で管理
        int cmd = grundy[n];  // 現在の状態の Grundy 数

        field[1] = n + 1;  // field に区間 [1, n + 1) を追加

        if (cmd) {  // Grundy 数が 0 でないなら
            cout << "First" << endl;  // 先手
            op(cmd, l, field, grundy);  // 自分の操作を実行
        } else {  // 0 なら
            cout << "Second" << endl;  // 後手
        }

        cin >> a >> b;
        while (b) {
            cmd = updateField(a, b, field, grundy);  // 相手の操作を反映
            op(cmd, l, field, grundy);  // 自分の操作を実行

            cin >> a >> b;
        }

    } else {  // 違うなら「真似っこ戦略」
        // N と R の偶奇が一致していないなら (r - 1) 枚、一致しているなら r 枚取り除く
        int y = r - (n - r) % 2;
        // 真ん中を取り除くときの位置
        int x = n / 2 - y / 2 + 1;
        // 真似っこするときの位置の差分
        int range = x + y - 1;

        // 先手必勝
        cout << "First" << endl;
        cout << x << ' ' << y << endl;
        cin >> a >> b;

        while (b) {
            // 真似っこ
            if (a >= range) {
                cout << a - range;
            } else {
                cout << a + range;
            }
            cout << ' ' << b << endl;

            cin >> a >> b;
        }
    }
    return 0;
}

Ex - make 1

編集中…

Discussion

コメントにはログインが必要です。