#毎日C問題 ABC240-C 「Jumping Takahashi」
挨拶
Rute(リュート)です。
普段は、競技プログラミングの問題を解く事、趣味の音楽ゲームをプレイすることが趣味の大学4年生です。
#毎日C問題 という企画が再開して早11日目。
皆さんは毎日連続で解けていますか?
私は大学の研究などが忙しく、毎日は解けていませんが
時間が空いた時に解いてみようと思い参加を続けています。
問題概要
問題の直接のURLは https://atcoder.jp/contests/abc240/tasks/abc240_c から
![](https://assets.st-note.com/img/1655545863216-ApoEhsJa3z.png?width=1200)
解法
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)となり、制約内で高速に計算することが出来た。
ソースコード
感想
2/20(コンテスト当日)以来、ABC240のC問題を解いていなかった。
問題を久々に見て、N≦100、X≦10000であることから即座に動的計画法を用いる問題であると気づいた。
以前よりも高速に解法に気づいた(解いた事があるので覚えているのかもしれないが)ため、成長していると感じた。
回答時間は5分程度。
また#毎日C問題 に関してブログ記事を書ける機会があれば、解いた感想等を共有していきたいと思う。
![](https://assets.st-note.com/img/1655547085070-oBavX1eNhj.png?width=1200)
この記事が気に入ったらサポートをしてみませんか?