かわわんの色々

数学とか自転車とか競プロとか音楽とか

AGC020 A Move and Win

AtCoderを始めたもののバイトの関係でコンテストに参加できずにいましたが,時間があったのでAGCにチャレンジしてみました.

目次!

結果

A問題だけACです.翌日,B問題もACしました.B問題についても別に書きます.

A : Move and Win

A - Move and Win

いくつかの具体例を試すとすぐに法則が見えました.10分弱だったと思います.

問題の設定

  • AliceとBorysがゲームをする
  • Nマスに区切られたテープがある.左から1,2,3,\cdots,Nと番号が振ってある
  • ゲームスタート時AliceとBorysはそれぞれこのテープの第Aマス,第Bマスにいる
  • 必ずAliceが先行でターンプレイヤーは右か左に1マスだけ進む
  • ターンプレイヤーが動きたいと思う方向に相手プレイヤーがいる場合,その方向に進むことはできない
  • ターンプレイヤーがテープの左端(右端)にいる場合,左側(右側)に移動することができない
  • ターンプレイヤーが左右どちらにも移動できなかった場合,そのプレイヤーは敗北する
  • プレイヤーは勝つために最適な行動をする

答えるべきもの

制約

  • 2 \leq N \leq 100
  • 1 \leq A \leq B \leq N

解説

僕がこの問題を解いたときの思考過程をなぞりながら書きます.

AliceとBorysの動き方のパターンはたくさんあるように思われます.

それを全て試すわけにはいかないので,コード書く前に紙に実際の例を書いて何か法則を見つけようと思いました.

N=2 のとき

もっとも単純な時です. f:id:kebobokawawan:20180116155100p:plain

先行のAliceはゲームのルールより左側にも右側にも進むことができません.

よってこのときはBorysが勝つのでテープの右側には"Borys"と書いています.

N=3 のとき

2番目に単純な時です.AliceとBorysの初期位置は3通り. f:id:kebobokawawan:20180116155121p:plain

真ん中のパータンの時は"Alice"が勝ちます.

N=4 のとき

AliceとBorysの初期位置は例えば以下のようなものがあります.そろそろ法則が見えてきます. f:id:kebobokawawan:20180116155128p:plain

どちらが勝つのか

ゲームを進行していってAliceのターン開始時に二人の位置が

Alice Borys

と隣り合ってしまったら"Borys"が勝ちます.

Alice 空きマス Borys

になる場合は“Alice”が勝ちます.

f:id:kebobokawawan:20180116155747p:plain

二人の初期配置によって勝敗が決まる

AliceとBorysの初期配置の空きコマが偶数の時.すなわち,

(B - 1 - A) \, \verb|%| \, 2\, ==\, 0

となれば"Borys"が勝ちます.

f:id:kebobokawawan:20180116160025p:plain

"Borys"が勝たないときは"Alice"が勝ちます.elseで書けばよいです.

以上より次のようなコードを提出しました.

Submission #1975697 - AtCoder Grand Contest 020