ABC004を解いた

先週末のABCは参加するのをすっかり忘れていました．

というわけで，今回はAtCoder Beginner Contest 004を解いてみました．公式の解説はこちら．

A 流行

自力完答
「倍返しだ」が流行っていた事を思い出した．入力された数値をただ2倍して表示するだけ．簡単．

B 回転

自力完答
4x4の行列を180度回転させる問題．16個の変数を用意するより，2次元配列を使ったほうがコーディング時間を短縮できる気がする．普通に2次元配列で実装したが，他の方の解答の中にすごくPythonらしい書き方をしているものがあったので，それを参考に修正してみた． なかなか奇妙な見た目をしている．

C 入れ替え

自力完答
6枚のカードに何回か入れ替え操作を行なって，その結果を出力する．公式解説の通り，30回入れ替えると元の並びに戻ることに気づけるかどうかが鍵．割とすんなり解けた．

D マーブル

自力で40点，解説見て100点
全てのマーブルを最小コストで並べる問題．単純に考えると，最初にマーブルの入ってるそれぞれの箱を中心として，マーブルを左右に移動させていけば解けるが，それでは40点しかもらえなかった．公式解説を読むと，どうやら動的計画法を使えばいいらしい．他の方の解答を参考にしつつ実装したのがこちら． DPテーブルをdp[現在の位置][残マーブル数]とすると，以下のような漸化式ですべてのテーブルの値が求まる．基本的に最小値を求める問題なので，DPテーブルの初期値は10⁹にした．

dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1] + iにマーブルをおいた時の操作数)

マーブルは必ず赤，緑，青の順番で並ぶため，置く場所がわかれば操作数はすぐに求まる．DPテーブルを埋めたあとは，残マーブル数が0の列を取り出し，その中の最小値を取れば答えが求まる．

動的計画法のポイントは，問題から変数をうまく取り出して漸化式を立てられるかどうかだと思った．