NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ，自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので，過去にブックマークされた記事は URL が変わってしまっている可能性があります……．

Educational Codeforces Round 73 (Rated for Div. 2) E. GameWithString

競技プログラミング (問題解説)

問題: https://codeforces.com/contest/1221/problem/E

問題概要

Alice と Bob が2人でゲームをする．先攻は Alice である．

'.' と 'X' のみからなる，$ \left| s \right| (\leq 3 \times 10^5) $ を満たす文字列 s がある．

この文字列 s から， Alice は $ a (\leq 3 \times 10^5) $ 個， Bob は $ b (\leq 3 \times 10^5) $ 個連続している '.' をすべて 'X' に変える操作を行う．どちらも操作ができなくなったとき，最後に操作したプレイヤーの勝利となる．ただし $ a \gt b $ が必ず成り立つ．

2人が最適に操作を選択したとき，Alice が勝利するかどうかを答えよ．

解法概要

参考: keymoon さんのツイート

連続する $ v $ 個の '.' を，" $ v $ の要素" と呼ぶこととする．

$ a \gt b $ より， Bob が有利なゲームである．なぜならば，Alice が操作ができず Bob は操作ができる要素 ($ b \le v \lt a $ となる $ v $ の要素) が1つでもあるならば，Alice は負けてしまうからである．残りの要素が「2人とも操作できない要素」と「Alice が操作ができず Bob は操作ができる要素」だけになったとき，Alice のターンなら Alice は操作ができずに負けるし， Bob のターンなら Bob が操作した後やはり Alice は操作ができず負ける．

Bob しか操作できない要素がなければ，最適な戦略は Bob は自分だけが操作できる要素を作り出すこと，Alice は Bob だけが操作できる要素を作らせないこととなる． Bob しか操作できない要素を作り出すには，$ 2b \le v $ となるような要素に対して片側を $ b \le i \lt a $ 個だけ残して操作すればよい．

これらの戦略を頑張って場合分けで実装する． 場合分けの詳細はソースコードのコメント参照．

ソースコード

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool solve() {
    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    if(s.back() != 'X') s += 'X';
    int n = s.length(), continuous_cnt = 0;

    // '.' が何個続くかを格納したベクトル v を作る
    vector<int> v;
    for(int i=0;i<n;++i) {
        if(s[i] == 'X') {
            if(continuous_cnt >= b) {   // b未満の要素は2人とも取れないので考えなくていい
                v.push_back(continuous_cnt);
            }
            continuous_cnt = 0;
        } else {
            ++continuous_cnt;
        }
    }

    int cnt = 0;
    int max_v = 0;
    for(int vv: v) {
        if(vv < a) return false; // Bob しか取れない要素
        else if(vv < 2*b) ++cnt; // 2人とも取れて，かつ Bob が自分か取れない要素を作り出せない要素
        else {                   // Bob が自分しか取れない要素を作り出せる要素
            if(max_v) {
                return false;
            } else {
                max_v = vv;      // 1つだけなら Bob しか取れない要素を作られる前に阻止できる
            }
        }
    }

    // Bob しか取れない要素の作成を阻止してからの戦い

    // この地点で max_v 以外は (a <= vv && vv < b) な要素だけでできている
    if(max_v) {
        /*
         * Alice は最初のターンで max_v から a 個を取ったものと仮定する
         * (他の要素から取ると，max_v ( >= 2*b) を用いて Bob しか取れない要素を作り出されてしまうので)
         */
        for(int i=0;i<=max_v-a;++i) {   // Alice が最初のターンで取る位置は全探索
            int j = max_v - (i+a);  // Alice がa個取ると max_v が i 個と j 個に分かれる
            if((b <= i && i < a) || (b <= j && j < a) || 2*b <= i || 2*b <= j) {
                // Bob しか取れない要素ができちゃったり，
                // 次の Bob のターンで Bob しか取れない要素を作られてしまうような取り方はしたくない
                continue;
            } else {
                // (a <= vv && vv < b) な要素 + 最初のターンで取った分 + i から取れる分 + j から取れる分
                // の合計が奇数ならそのように取ればいい
                if((cnt + 1 +  ((a <= i)?1:0) + ((a <= j)?1:0)) % 2) return true;
            }
        }
        // 勝てる手筋がなければアウト
        return false;
    }

    // (a <= vv && vv < b) な要素だけなら，単純に要素数の偶奇
    return cnt % 2;
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(nullptr);
    int q;
    cin >> q;
    while(q--) {
        cout << (solve()?"YES":"NO") << endl;
    }
}

所感

Codeforces 紫になりました！　 これで AtCoder，Codeforces，TopCoder SRM の色がすべて違うことに……

鬼場合分けもそろそろ本番で解けるようにならないとな．

f:id:noimin:20190920235324p:plain