Codeforces Round #659 (Div. 1) 感想

問題

Dashboard - Codeforces Round #659 (Div. 1) - Codeforces

感想

遅解き1完。よわ。

くやしいけど、これが自分の実力なんだと受け止めるしかない。

青落ち。。。

A - String Transformation 1

めっっっちゃ時間かかった（約80分）。迷走に迷走を重ねました。。。

コンテスト中に考えたこと：

• 一回の操作で、できるだけ多く にできるとうれしい。→ 一度に操作できるのは同じ文字だけだから、同じ文字が増えると嬉しいだろう。
• A = aaaa, B = bbcc のとき、aaaa → bbaa → bbcc とするときと、aaaa → bbbb → bbcc では操作回数は変わらない。ならば、同じ文字が多い後者の方が良いだろう。

このことからエスパーして、a からアルファベット順に次のような操作を繰り返せばいいと考えた：

1. 今見てるアルファベットを とする。 かつ であるすべての について を列挙して、その中で一番小さいものを とする。
2. 操作によって、 かつ であるすべての について とする（そのような がなければ操作は行わない）。

これを実装して提出するとACを得た。

僕はこれを dp[i][j] := (A[k] = i かつ B[k] = j である k の個数) を管理することで実現したけど、コンテスト後のTLを眺めるとUnion-Findを使ったかしこい実装があるみたいだった。 どうするんだろう。

提出コード

リンク： http://codeforces.com/contest/1383/submission/87909429

int dp[21][21];
 
void solve() {
    int Q;
    cin >> Q;
    set<int> st1, st2;
    while (Q--) {
        ll N;
        cin >> N;
        string A, B;
        cin >> A >> B;
        bool ok = true;
        for (ll i = 0; i < N; i++) {
            if (A[i] > B[i]) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            prints()(-1);
            continue;
        }
 
        for (ll i = 0; i < N; i++) {
            ++dp[A[i] - 'a'][B[i] - 'a'];
        }
 
        ll ans = 0;
        for (ll i = 0; i < 20; i++) {
            ll mn = L_INF;
            for (ll j = i + 1; j < 20; j++) {
                if (dp[i][j] > 0) {
                    mn = min(mn, j);
                }
            }
            if (mn != L_INF) {
                ++ans;
                for (ll j = 0; j < 20; j++) {
                    dp[mn][j] += dp[i][j];
                    dp[i][j] = 0;
                }
            }
        }
 
        prints()(ans);
    }
}

B - GameGame

解けず。。。

上位bitで優勢ならば下位bitがどうだろうが関係ない。なので、上位bitから見ていき決着がどうなるかを判定する。

以下を上位のbitから確認していく（ の要素のうち、今注目している位のbitが立っているものの個数を とする。）：

• が偶数のとき、どのようにしても取ることになるbitの個数は2人とも偶数になるか奇数になるかなので、今の位では決着はつかない。
• のとき、先手が最初にbitを一つ取ってしまえば、あとは後手がbitを取るたびに先手もbitをとれば先手のbitの個数を奇数、後手の個数を偶数にできるから、先手が勝つ。
• のとき、
  • が奇数のとき、後手は先手がbitを取らなかったとき自分もbitを取らないようにすれば、先手のbitの個数を偶数、後手の個数を奇数にできるから、後手が勝つ。
  • が偶数のとき、先手は最初にbitを取らない選択をし、そのあとは後手がbitを取らなかったときに自分もbitを取らないようにすれば、先手のbitの個数を奇数、後手の個数を偶数にできるから、先手が勝つ。

コンテスト後提出コード

リンク：http://codeforces.com/contest/1383/submission/87929206

void solve() {
    int Q;
    cin >> Q;
    Vl A;
    Vl cs;
    while (Q--) {
        ll N;
        cin >> N;
        A.resize(N);
        for (ll i = 0; i < N; i++) {
            cin >> A[i];
        }
 
        cs.assign(60, 0);
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < 60; j++) {
                if (A[i] >> j & 1) {
                    ++cs[j];
                }
            }
        }
 
        int ans = 0;
 
        for (ll i = 59; i >= 0; i--) {
            if (~cs[i] & 1) continue;
            if (cs[i] % 4 == 1) {
                ans = 1;
            }
            else {
                if (N & 1) {
                    ans = -1;
                }
                else {
                    ans = 1;
                }
            }
            break;
        }
 
        if (ans == 1) {
            prints()("WIN");
        }
        else if (ans == 0) {
            prints()("DRAW");
        }
        else {
            prints()("LOSE");
        }
    }
}

C以降

読めてないので割愛。