AGC020 A Move and Win
AtCoderを始めたもののバイトの関係でコンテストに参加できずにいましたが，時間があったのでAGCにチャレンジしてみました．
目次！
結果
A問題だけACです．翌日，B問題もACしました．B問題についても別に書きます．
A : Move and Win
いくつかの具体例を試すとすぐに法則が見えました．10分弱だったと思います．
問題の設定
- AliceとBorysがゲームをする
マスに区切られたテープがある．左から
と番号が振ってある
- ゲームスタート時AliceとBorysはそれぞれこのテープの第
マス，第
マスにいる
- 必ずAliceが先行でターンプレイヤーは右か左に
マスだけ進む
- ターンプレイヤーが動きたいと思う方向に相手プレイヤーがいる場合，その方向に進むことはできない
- ターンプレイヤーがテープの左端(右端)にいる場合，左側(右側)に移動することができない
- ターンプレイヤーが左右どちらにも移動できなかった場合，そのプレイヤーは敗北する
- プレイヤーは勝つために最適な行動をする
答えるべきもの
- このゲームの勝利者
制約
解説
僕がこの問題を解いたときの思考過程をなぞりながら書きます．
AliceとBorysの動き方のパターンはたくさんあるように思われます．
それを全て試すわけにはいかないので，コード書く前に紙に実際の例を書いて何か法則を見つけようと思いました．
N=2 のとき
もっとも単純な時です．
先行のAliceはゲームのルールより左側にも右側にも進むことができません．
よってこのときはBorysが勝つのでテープの右側には"Borys"と書いています．
N=3 のとき
2番目に単純な時です．AliceとBorysの初期位置は3通り．
真ん中のパータンの時は"Alice"が勝ちます．
N=4 のとき
AliceとBorysの初期位置は例えば以下のようなものがあります．そろそろ法則が見えてきます．
どちらが勝つのか
ゲームを進行していってAliceのターン開始時に二人の位置が
Alice Borys
と隣り合ってしまったら"Borys"が勝ちます．
Alice 空きマス Borys
になる場合は“Alice”が勝ちます．
二人の初期配置によって勝敗が決まる
AliceとBorysの初期配置の空きコマが偶数の時．すなわち，
となれば"Borys"が勝ちます．
"Borys"が勝たないときは"Alice"が勝ちます．elseで書けばよいです．
以上より次のようなコードを提出しました．
