ABC109 D - Make Them Even
こんばんは、久しぶりにABC4完でき、嬉しかったのでwrite upします。
最近は4完どころか3完すらままならないことが稀によくあります。。。C問題の難化激しくないですかね。
さて、問題はこちら。
「偶数枚のコインが置かれたマスの数を最大化してください」
ということから、奇数枚のコインがあるマス二つの間を移動すればいいことがわかります。
最初は出力方法が複雑だけど簡単だなーって解いたんですが、WA。
問題をよく読み返してみると
「まだ選んだことのないマス」
という制約がありました。2WAでようやく気付いた←
考えた結果、このような方向に従ってコインを移動すれば、ルートが被り同じマスを2度選ぶ必要がないことがわかりました。
左上からスタートし、右へ進んでいって、改行したら次は左へ進んでいきます。
たとえば、4*4のマスで(1,2)のコインを(2,1)へ移したいときは、
(1,2) → (1,3) → (1,4) → (2,4) → (2,3) → (2,2) → (2,1) と移動することになります。
これを、奇数のマスが2つ未満になるまで繰り返せばACです。
時間ギリギリで、いいコードにはできませんでしたが、とりあえず解けたので良かったです。
