▲「お兄ちゃん、聞きたい問題があるんだけど」
■「どうした？」
▲「Codeforces #585 (Div.2) の D 問題なんだけど」
■「なんでこの問題？」
▲「ふと思い立ったの。この問題を解こうって」
■「ふと思い立つものなの！？」
▲「まあ、そんなことで見てみたんだけど、分からないんだよね」
■「じゃあ、問題を見てみよう」
Ticket Game
問題概要
▲「問題はこんな感じ」
‘?’ を含む $n$ 桁の数字の列が書かれたチケットがある。$n$ は偶数であり、’?’ の数も偶数である。
前半 $\frac{n}{2}$ 文字の数字の和と後半 $\frac{n}{2}$ 文字の数字の和が等しいとき、それは “幸福のチケット” である。
Monocarp と Bicarp の二人が交互に、好きな場所の ‘?’ に $0$ から $9$ までの整数を入れるゲームをする。
先手である Monocarp は “幸福のチケット” が嫌いなので、最終結果が “幸福のチケット” になることを阻止すれば勝ちである。
後手である Bicarp は “幸福のチケット” が好きなので、最終結果が “幸福のチケット” になれば勝ちである。
両者が最適に行動したときの勝者を出力せよ。
$2\le n\le 2\cdot 10^5$
■「ゲーム問題か。1 つ目のサンプルは、? が無いからすでに決着していて、前半の和と後半の和がともに 5 で等しいから後手の勝ちだね」
▲「うん。2 つ目のサンプルは “??” だけど、先手が入れた数と同じ数をもう一つの ? に入れたら、絶対に後手が勝てるね」
■「そうだね。3 つ目と 4 つ目のサンプルはちょっとややこしいね」
最初の考察
■「で、どこまで考えた？」
▲「まず、前半と後半に分けて考えると、同じ側の中では、’?’ の位置は関係ないなと思った。それと、すでに埋まってる数についても、前半と後半それぞれの合計だけ考えればいいよね。どうせ全部足すんだから」
■「そうだね」
▲「それで、前半と後半の差が 0 になるかどうかが大事だから、（前半の和）ー（後半の和）の値を基準に考えようかなと思った」
■「良いね。こうすると、考える値が 1 つで済むようになる」
▲「だけどそれだと、前半の ‘?’ に数字を入れるとこの値が増えて、後半の ‘?’ に入れるとこの値が減ることになるんだよね。操作が 2 種類あるから困っちゃった」
■「ふむふむ」
▲「DP みたいなことをしたくても、（前半の残り ‘?’ 数）と（後半の残り ‘?’ 数）みたいなのを持たないといけない気がして、$O(n^2)$ になっちゃうんだよね。$n$ が $2\cdot 10^2$ まであり得るから TLE だよ」
■「なるほど。考えたのはそこまで？」
▲「うん。もうお手上げだよー」
定番テクニック
■「困っている理由は、操作が 2 種類あることだよね」
▲「うん。前半の ‘?’ に入れるか後半の ‘?’ に入れるかで効果が変わるからね。最後にどっちを残すかも大事だし」
■「操作が 2 種類あって困ったときの定番テクニックに “操作を変換して同一視する” というのがある」
▲「変換して同一視？」
■「2 種類の操作をうまく言い換えたりして、1 種類の操作とみなすこと」
▲「どうやってやるの？」
■「（前半の和ー後半の和）の値が、前半の ‘?’ に数字を入れると $+0\sim +9$ になって、後半の ‘?’ に入れると $-9\sim -0$ になる」
▲「うん」
■「前半だとプラスで後半だとマイナスだから、効果が変わっちゃうんだよね」
▲「うん」
■「じゃあ、プラスとマイナスで効果が同じになるようにしよう」
▲「どういうこと？」
■「$+x\sim +y$ の範囲と $-y\sim -x$ の範囲が一致するには、どうすればいい？」
▲「あ、マイナスにすると順序が入れ替わるから $x$ と $y$ の位置が入れ替わってるんだね。これが一致するには…… $x=-y$ ？」
■「正解。そうしよう」
▲「そうしようって、どうやって……」
■「考えてみよう」
▲「うーん…… 前半の ‘?’ に数字を入れると $-x\sim +x$ になるようにするには…… あ！ 最初に $4.5$ が入ってるってことにすれば、$0$ を入れると $-4.5$ になるし、 $9$ を入れると $+4.5$ になる！」
■「正解！ 全ての ‘?’ に最初は $4.5$ が入っていることにして（前半の和ー後半の和）を計算しておけば、前半でも後半でも、’?’ に数字を入れるとその値が $-4.5\sim +4.5$ になる」
▲「へー、すごいね。天才じゃん」
対称戦略
■「ということで、操作は 1 つになった。（前半の和ー後半の和）を $-4.5\sim +4.5$ する操作だ」
▲「ここからどうするの？」
■「考えよう」
▲「えっと、この値が最終的に $0$ になっていれば後手の勝ちだよね。だから、先手はこの値を 0 から遠ざけようとするんだね。正なら $+4.5$ して、負なら $-4.5$ する」
■「そうだね」
▲「それで、後手は $0$ に近づけようとするから、正なら $-4.5$ して、後手なら $+4.5$ するよね。あれ、これって先手と後手が操作しても値が変わらないじゃん」
■「そうなるね」
▲「ってことは、最初にこの値が $0$ なら後手が勝ちで、そうじゃないなら先手が勝ちってこと？」
■「そうなりそうだね。こういう、相手の操作の対称的な操作を繰り返すことを、対称戦略と僕は呼んでいる。そのままだけど」
▲「聞いたことある！ 『円形のテーブルに牛乳瓶の蓋を交互に置いて、蓋どうしが触れたら負け』っていうゲームで、先手がど真ん中に置いて、あとは後手が置いた場所の反対側に置くようにすれば、後手が置けたら先手も置けるから先手必勝、ってやつ！」
■「ちょっと違う気もするけど、そういうことなのかな？ まあいいや。これをちゃんと証明してみよう」
必勝法の証明
▲「証明ってどうやってやるの？」
■「いくつか方法はあるけど、2 通りやってみよう。まず、素直な証明から。（前半の和ー後半の和）が $0$ なら後手が勝つということを証明してみよう」
▲「うーん…… 先手の操作での変化をちょうどプラマイで打ち消す操作をすれば、この値が $0$ のまま ‘?’ の数が減るから、これを繰り返せば後手が絶対に勝つね」
■「そうだね。これは ‘?’ の数が偶数だから成り立つことだ。また、操作は $-4.5\sim +4.5$ だから、必ず打ち消す操作が存在するね」
▲「そこまで確認しないと正しい証明にならないんだね」
■「次は、この値が $0$ 以外なら先手が勝つという証明」
▲「この値が正なら、先手が $+4.5$ すれば、後手がどうやっても元より $0$ に近づくことは無いよね。最小でも $-4.5$ で元に戻すだけだから」
■「そうだね。負の場合も、$-4.5$ として同様だね」
▲「だから、後手は絶対に $0$ にはできない」
■「OK。これで証明終わり」
▲「これだけ？ 簡単だね」
■「じゃあ、もう一つの証明をやってみよう」
後ろから考える
▲「もう一つの証明ってどんなの？」
■「DP っぽい考え方。ゲーム問題の定番テクニックとして、”後ろから考える” というものがある」
▲「後ろから？」
■「決着した状態から、一手ずつ後退していく。後退しながら、”ここから勝てるか” とか “ここから勝つ条件” とかを計算していく」
▲「うーん、よくわかんない」
■「今回は、“（前半ー後半）の値がどの範囲にあればここから勝てるか” を見ていこう」
▲「“（前半ー後半）の値がどの範囲にあればここから勝てるか” か。最後の後手の手番だと、$-4.5\sim 4.5$ の範囲にあれば勝てるよね」
■「うん。その範囲にあれば、かならず $0$ にできるね。その前の先手番では？」
▲「えっと、先手は $-4.5\sim 4.5$ の範囲に入れたら負けるから、ここから脱出したいんだよね。でもこれ、ほとんどの場合で脱出できるよね？」
■「そうだね。脱出できないのはどんな場合？」
▲「 0 のときだね。先手番の時点で、（前半ー後半）が $0$ だったら、どうあがいても $-4.5\sim +4.5$ の範囲に入っちゃうね」
■「そうだね。だから、$0$ のときのみ後手勝ち、それ以外だと先手勝ち」
▲「じゃあ、その前の後手番は、この値を $0$ にすれば勝ちだから…… って、さっきと同じじゃん！」
■「そう。勝つための条件がずっと一緒。先手番なら $0$ であること、後手番なら $-4.5\sim +4.5$ の範囲に入っていること」
▲「これが永遠に続くんなら、DP で逐次計算する必要無いね」
■「そういうことで、最初の状態で（前半ー後半）が $0$ なら後手勝ち、そうでないなら先手勝ち」
▲「当たり前だけど、同じ結果になったね」
■「じゃあ実装しようか」
実装・提出
▲「実装は簡単だね。数字列には ‘?’ がある場合があるから string で受け取って、前半と後半で処理を分けるんだよね。で、（前半ー後半）が $0$ かどうかで判定。これでいいかな？」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <iostream> using namespace std; int main() { int n; string S; // 数字列は文字列で受け取る cin >> n >> S; double sum = 0; // 前半 - 後半 を計算 for (int i = 0; i < n; i++) { if (i < n / 2) { // 前半（足す） if (S[i] == '?') { sum += 4.5; // ? なら 4.5 を足す } else { sum += S[i] - '0'; // ? でないならその数を足す } } else { // 後半（引く） if (S[i] == '?') { sum -= 4.5; // ? なら 4.5 を引く } else { sum -= S[i] - '0'; // ? でないならその数を引く } } } // 前半 - 後半 == 0 なら Bicarp の勝ち, そうでないなら Monocarp の勝ち if (sum == 0) { cout << "Bicarp" << endl; } else { cout << "Monocarp" << endl; } return 0; } |
▲「あ、double の一致判定を == でやるのはダメなんだっけ、double だと誤差もあるからもっと慎重にしないとダメか」
■「そうだね。でも実は、今回に限っては大丈夫なんだ」
▲「どうして？」
■「今回、double を使っている理由は、$4.5$ という小数があるからだよね。でも、小数は $4.5$ しか無い」
▲「うん」
■「doulbe では、数が 2 進数で表現されているんだけど、それは（整数$\times 2^e$）というような形で表現されているんだ。だから、2 の整数乗である $0.5$ や $0.25$ などは正確に表せるんだ」
▲「ややこしいー」
■「つまり、$4.5$ は $9\times 2^{-1}$ として表現されているということ。だから、2 の整数乗で表現できない $0.1$ などとは違い、今回の桁数程度では丸め誤差が発生せず厳密な値を持てるんだ」
▲「よくわかんないけど、それに頼ったらダメな気がするから、安全にいくよ」
■「まあ、それが良いね。もっと誤差を恐れるなら、2 倍して全て整数で計算するというのもあるけど、今回はそこまでしなくて大丈夫」
▲「差が四捨五入して 0 になればいいから、差の絶対値が 0.5 未満なら OK ってことにすればいいかな。これでいいはず」
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <cmath> // std::abs #include <iostream> using namespace std; int main() { int n; string S; // 数字列は文字列で受け取る cin >> n >> S; double sum = 0; // 前半 - 後半 を計算 for (int i = 0; i < n; i++) { if (i < n / 2) { // 前半（足す） if (S[i] == '?') { sum += 4.5; // ? なら 4.5 を足す } else { sum += S[i] - '0'; // ? でないならその数を足す } } else { // 後半（引く） if (S[i] == '?') { sum -= 4.5; // ? なら 4.5 を引く } else { sum -= S[i] - '0'; // ? でないならその数を引く } } } // 前半 - 後半 == 0 なら Bicarp の勝ち, そうでないなら Monocarp の勝ち if (abs(sum) < 0.5) { cout << "Bicarp" << endl; } else { cout << "Monocarp" << endl; } return 0; } |
▲「これで提出して…… やった、AC！」
■「おめでとう。ちなみに sum == 0 で判定したものも AC になるよ。おすすめはしないけどね」
▲「変なことはしない！」
▲「終わってみれば簡単な問題だった気もするけど、定番テクニックが詰まった良い問題だね」
■「そうだね。今回はあまり意識しなくても大丈夫だったけど、後ろから考えないとダメなゲーム問題もあるので、そっちの考え方も理解しておいてね」
▲「はーい」