Codeforces Round #658 (Div. 1) 感想

問題

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

感想

3完。はじめての Div.1 だった。

どちらかといえば成功寄りの感触だったんだけどレート変動は 1900→1904 (+4) の微増。聞いてた通り Div.1 はきびしいな～～。

まぁ、青落ちしなかっただけでも良しとしよう。

A1 - Prefix Flip (Easy Version)

後ろから見ていく。 $a_i = b_i$ なら無視して、 $a_i \neq b_i$ なら、i → 1 → i と操作すればいい。

操作回数の上限は明らかに $3n$ なのでこれでOK。

これはすぐに思いつけた。しかし、、、

提出コード

リンク： http://codeforces.com/contest/1381/submission/87536376

void solve() {
    ll Q;
    cin >> Q;
    Vl ans;
    while (Q--) {
        ll N;
        cin >> N;
        string A, B;
        cin >> A >> B;
        ans.clear();
        for (ll i = N - 1; i >= 0; i--) {
            if (A[i] != B[i]) {
                ans.emplace_back(i);
                ans.emplace_back(0);
                ans.emplace_back(i);
            }
        }
        cout << ans.size() << " ";
        if (!ans.empty()) {
            for (auto ai : ans) {
                cout << ai + 1 << " ";
            }
        }
        cout << "\n";
    }
}

A2 - Prefix Flip (Hard Version)

Easy はすんなりと解けた一方でこちらには結構時間をかけてしまった（Easy: 14分、Hard: 40分）。

順位表を見ると強い人は Easy と Hard をほぼ同時に提出していてすごいな～と思った。こういう Easy と Hard の違いが制約だけの場合は Easy を解き始める前に Hard の制約も見ておくべきっぽいな。

結局、Hard 解は Easy 解の考え方を少し改良するだけでよかった。実装は段違いで大変だけど。

Easy 解での操作は、i 番目の要素を一度先頭に移動させて、反転させ、もう一度 i 番目に戻した。でも、よく考えると i 番目の要素を先頭に移動させる操作はムダであって、元々先頭にある要素を操作によっていい感じにしてから i 番目に移動させるほうが良い。

つまり、次の手順を i を N から 1 まで動かしながら実行すればいい：

$a_1 = b_i$ なら、操作によって $a_1$ を反転させる。
$a[1 \ldots i$ ] に対して操作を行う。

これなら明らかに操作回数は $2n$ 以内で済む。

各操作（反転・reverse）を愚直にシミュレートするのでは間に合わないから、実装は工夫する必要がある。

提出コード

リンク：http://codeforces.com/contest/1381/submission/87562309

void solve() {
    ll Q;
    cin >> Q;
    Vl ans;
    while (Q--) {
        ll N;
        cin >> N;
        string A, B;
        cin >> A >> B;
        ans.clear();
        bool is_rev = false;
        if (N & 1) {
            for (ll i = N - 1; i >= 0; i--) {
                if (~i & 1) {
                    ll idx = N / 2 - i / 2;
                    if (!is_rev) {
                        if (A[idx] == B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    else {
                        if (A[idx] != B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    ans.emplace_back(i);
                }
                else {
                    ll idx = i / 2 + N / 2 + 1;
                    if (!is_rev) {
                        if (A[idx] == B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    else {
                        if (A[idx] != B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    ans.emplace_back(i);
                }
                is_rev ^= true;
            }
        }
        else {
            for (ll i = N - 1; i >= 0; i--) {
                if (i & 1) {
                    ll idx = N / 2 - 1 - i / 2;
                    if (!is_rev) {
                        if (A[idx] == B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    else {
                        if (A[idx] != B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    ans.emplace_back(i);
                }
                else {
                    ll idx = i / 2 + N / 2;
                    if (!is_rev) {
                        if (A[idx] == B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    else {
                        if (A[idx] != B[i]) {
                            ans.emplace_back(0);
                        }
                    }
                    ans.emplace_back(i);
                }
                is_rev ^= true;
            }
        }
        cout << ans.size() << " ";
        for (auto ai : ans) {
            cout << ai + 1 << " ";
        }
        cout << "\n";
    }
}

B - Unmerge

$p$ は

[ $a$ 由来のシーケンス] + [ $b$ 由来のシーケンス] + [ $a$ 由来のシーケンス] + [ $b$ 由来のシーケンス] + ...

のように構成される（上では $a$ から始めているけど、もちろん $b$ から始まる場合もある）。

そして、 $\mathrm{merge}(a, b)$ の定義から、各シーケンスの先頭はそれより左のすべての $p$ の要素より真に大きくないといけないことが分かる。

つまり、「それより左のすべての $p$ の要素より真に大きい」という条件を満たしている要素のみが、「 $a$ 由来」と「 $b$ 由来」の境界となりうる。なので、この条件を満たす $p$ の要素を左から順に $p_{d_1} (= p_1), p_{d_2}, \ldots, p_{d_s}$ とおくと、連続部分列 $p[d_i \ldots d_{i+1}-1$ ] は「すべて $a$ 由来」か「すべて $b$ 由来」かのどちらかとなる。

よって、元の問題は、「各 $p[d_i \ldots d_{i+1}-1$ ] について「 $a$ 由来」とするか「 $b$ 由来」とするかを割り振るとき、 $p = \mathrm{merge}(a, b)$ かつ $|a| = |b| = n$ となるような割り振りは存在するか？」という問題に帰着される。

で、実は、どのように割り振っても $p = \mathrm{merge}(a, b)$ は満たされるので、あとは $|a| = |b| = n$ とできるかを調べればいい。これは各 $p[d_i \ldots p_{i+1}-1$ ] の長さを集めた集合における部分和問題だから DP で解くことができる。

計算量は時間・領域ともに $O(n^2)$ 。

部分和問題に落とし込めた時、めっちゃ気持ちよかったな～～。

提出コード

リンク：http://codeforces.com/contest/1381/submission/87579524

int dp[4010][2010];
 
void solve() {
    ll Q;
    cin >> Q;
    Vi P;
    vector<Vi> tm;
    Vi tm_tmp;
    while (Q--) {
        ll N;
        cin >> N;
        P.resize(N * 2);
        for (ll i = 0; i < N * 2; i++) {
            cin >> P[i];
        }
        tm.clear();
        tm_tmp.clear();
        ll cur = P[0];
        tm_tmp.emplace_back(P[0]);
        for (ll i = 1; i < N * 2; i++) {
            if (P[i] < cur) {
                tm_tmp.emplace_back(P[i]);
            }
            else {
                tm.emplace_back(tm_tmp);
                tm_tmp.clear();
                tm_tmp.emplace_back(P[i]);
                cur = P[i];
            }
        }
        if (!tm_tmp.empty()) {
            tm.emplace_back(tm_tmp);
        }
 
        int nz = (int)tm.size();
        for (ll i = 0; i <= nz; i++) {
            for (ll j = 0; j <= N; j++) {
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 1;
 
        for (ll i = 0; i < nz; i++) {
            int d = (int)tm[i].size();
            for (ll j = 0; j <= N; j++) {
                dp[i + 1][j] |= dp[i][j];
                if (j - d >= 0) {
                    dp[i + 1][j] |= dp[i][j - d];
                }
            }
        }
 
        // for (ll i = 0; i <= nz; i++) {
        //     for (ll j = 0; j <= N; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << "\n";
        // }
 
        bool ok = dp[nz][N];
        cout << (ok ? "YES\n" : "NO\n");
    }
}