面白かったけど場合分けが怖かった
問題概要
"...X......XX..X..X.XXX...X..."
のような '.' と 'X' からなる長さ の文字列が与えられる。
- 先手は連続する 個の '.' をすべて 'X' に置き換える
- 後手は連続する 個の '.' をすべて 'X' に置き換える
という操作を交互に行う。先に操作を行えなくなった方が負け。双方最善を尽くしたとき、どちらが勝つか?
ただし、 であることが保証されているものとする。
制約
考えたこと
やはり や くらいで解ければ OK。
すごくややこしいし、一見 Grundy っぽさ (盤面が本質的に分裂していくため) もあるのだけど、不公平ゲームだし Grundy はそのままでは扱いづらい。
ちょっとアドホックにいろいろ考えてみよう。少しわかってくるのは
- 先手が初手何も打てなかったらどうしようもない
- もし長さが 以上 未満の区間があったらその時点で先手はどうしようもない
- 先手が手を打ったあとにもし長さが 以上の区間があったらその時点で先手はどうしようもない (後手が必ず長さ の区間を作れるため)
ということがわかる。よって解法としては、長さ 以上 未満の区間がないことを確認した上で、長さ 以上の区間 ( 個とする) の長さを抜き出してきて、
- 空だったらアウト
- その中に長さ 以上の区間が 2 個以上あったらアウト
- 長さ 以上の区間が 1 個含むときは、なんとかそれを解体しなければならない (後述)
- 長さ 以上の区間がなければ、 が奇数個なら先手勝ち、偶数個なら後手勝ちになる。
長さ 以上の区間が 1 個だけ含まれるとき
ここの場合分けはあまりにもしんどいので、こういうときは探索に頼ってしまってよいと思う!!!!!!!探索量は でおさえられるので、 で済む。
すなわち、長さ 以上の区間に対して長さ の区間をどのように置くかを全探索する。各場合について
- もし長さ 以上の区間が再び生じたらダメ
- もし長さ 以上 未満の区間が生じたらダメ
- そうでなければ、分割後に「長さ 以上の区間の個数」がどうなったかを数えて、それが偶数だったら先手勝ち
全探索して先手勝ちになるパターンが存在しなかったら、後手勝ち。
#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; } }