Codeforces #51 C Pie or Die

題意是﹕給出一個N x M的棋盤，現有K個黑色的棋子(位置可以重覆)。每一回合可以選一個棋子向四個方向移動，然後對方會把棋盤的一條邊封掉。當玩家可以推一個棋子越過一條未封掉的邊為勝。問雙方用最優策略下，玩家能否勝出。

最初有幾個想法﹕
1. 永遠只選同一個棋子去移動。
2. 可移動回合有限，為2N+2M。
3. 最終棋子的終點是棋盤的任意一個角(直觀想的是這些格子需要封兩次才能防止棋子勝出)
4. 3x3的棋盤任意棋子必勝，故推測存在棋子距離邊的步數最少者少於3為必勝。

但畫出5x5的棋盤想了想也覺得任意棋子也可以勝出，但沒法証明，又不知是否有更大的可能…
故看了題解，答案果然是以棋子最少距離步少於5為勝。証明的方法還是很巧妙的。

只要到達最近的邊的距離至少是5步的話，那麼首四步會把棋盤上屬於那條邊的兩個角落的邊都封掉(總共剛好四條邊)，那麼在第五步的話最快會扺達其中一條邊，那麼只需要封住該邊，之後無論那棋子怎樣移動都把那最近的邊封掉，結論是必然是輸局。

下次一定要好好想想再拓展的情況…