ARC064 D An Ordinary Game

Submission #3727392 - AtCoder Regular Contest 064

所見

11月まるまる引退してしまったね、最近残業が増加しており悲しい

問題概要

文字列が与えられる。端を除く文字を先手と後手が順番に取っていく。ただしその文字を取り除くと同じ文字が隣り合うときは取り除くことができない。先に文字を取り除けなくなった方が負けの時、先手後手のどちらが勝つかを求めよ。

取った方針

少し考えると終了状態がababa とかbaba みたいな2文字の繰り返しになることはすぐにわかる。が、そこからなにもできず終了

正しい方針

端は取り除くことができないことに着目する。与えられた文字列とゲーム終了時の文字列の両端は変化しないので、両端が同じかどうかで終了状態の長さの偶奇がわかる。
終了状態の長さの偶奇が分かれば取る個数の偶奇もわかるので、どちらが勝つかが分かる。

得られた知見

• ここから何を得ればいいんだ(絶望)

解くのに必要な要素

• 思いついてほしそうな顔をしている->実験
• 両端が同じなら奇数個、違うなら偶数個残ることに気づけば最後までいける気がする

周辺調査によって得られた知見

特になし