読者です 読者をやめる 読者になる 読者になる

オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 004 D: マーブル

問題文

abc004.contest.atcoder.jp

解法

箱の番号とマーブルの残り個数を状態として適当な位置からDPする。

各色を独立に考えようとすると、状態数が 2000 * 300 * 300 * 300 になってしまう。しかし、無駄な移動をしないなら、すべてのマーブルの移動後は赤・緑・青の順番で並ぶ。そのため、すべてのマーブルの残り個数をまとめて考えることで、状態数を 2000 * 300 * 3 まで減らせる。あとは残り個数に応じてどの色のマーブルを配置するか場合分けすればよい。

各マーブルの移動回数は各マーブルの移動距離と考えられるので、そこまで複雑にはならなかった。