#毎日C問題 ABC240-C 「Jumping Takahashi」

挨拶

Rute(リュート)です。
普段は、競技プログラミングの問題を解く事、趣味の音楽ゲームをプレイすることが趣味の大学４年生です。

#毎日C問題 という企画が再開して早11日目。
皆さんは毎日連続で解けていますか？
私は大学の研究などが忙しく、毎日は解けていませんが
時間が空いた時に解いてみようと思い参加を続けています。

問題概要

問題の直接のURLは https://atcoder.jp/contests/abc240/tasks/abc240_c から

解法

TLE解法 : N回のジャンプに対してbit全探索

明らかに、N≦100であるから、動きをbit全探索などの方法で全探索する解法は実行時間制限超過(TLE)となりそうである。
より効果的に毎回の移動を処理出来る方法はないのだろうか。

AC解法：動的計画法を用いたジャンプのシミュレーション

Xより大きい座標の位置にジャンプした段階で条件である「座標Xの位置にいるようにする」ことが不可能になる。
以下、考える座標は0からXまでのX+1通りとする。
また、ジャンプの回数はN回であることが分かっている。

よって、以下の様なdp(動的計画法)テーブルを作成すれば良い。

dp[i][j] = i回目のジャンプで座標jに到達しているか。
到達していれば1、そうでなければ0が入っているものとする。
0回目の移動では、座標0の位置にいることが分かっているので、
dp[i][j] に対して
i = 0かつj = 0のとき1、
それ以外の(i,j)の組においては0と初期化する。

そして、N回のジャンプのシミュレーションを行う.
i(1≦i≦N)回目のジャンプに対して、0からXまでの座標で配列の全探索を行う.
もし dp[i-1][j] = 1のとき、
i-1回目のジャンプが終了した段階で、座標jへの到達が可能である
したがって
i回目のジャンプで座標jから座標j+a[i-1]または座標 j + b[i-1]へ移動することが可能である。
(ジャンプの回数と配列の座標の位置を合わせているため、座標がそれぞれj + a[i-1]、j + b[i-1]になっていることに注意する必要がある。) 
あとは、 j + a[i-1]、j + b[i-1]がX以下かそうでないかを確認し、
X以下であるならば、
dp[i][j + a[i-1]] = dp[i-1][j]
dp[i][j + b[i-1]] = dp[i-1][j]
とdpテーブルの遷移を行う。

これをN回のジャンプに対して行うため、シミュレーションの計算量はO(NX)となり、制約内で高速に計算することが出来た。

ソースコード

Submission #32532428 - AtCoder Beginner Contest 240

感想

2/20(コンテスト当日)以来、ABC240のC問題を解いていなかった。
問題を久々に見て、N≦100、X≦10000であることから即座に動的計画法を用いる問題であると気づいた。
以前よりも高速に解法に気づいた(解いた事があるので覚えているのかもしれないが)ため、成長していると感じた。

回答時間は5分程度。
また#毎日C問題 に関してブログ記事を書ける機会があれば、解いた感想等を共有していきたいと思う。