区間を整理する考え方が楽しかった。
問題概要
下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。
この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、
番目の赤い区間の内部の任意の点にコマを移動できる。
個のクエリが与えられる。各クエリでは、コマの初期位置
が与えられる。上記のルールに則ってコマを動かすとき、コマの位置の最大値を答えよ。
制約
- クエリの個数はテストケース全体を通して
以下である
考えたこと
色々単純化してよいことがわかった。
番目の黒い区間が
、赤い区間が
とするとき、次のように単純化してよい。
- コマの座標
が
ならば、
に移動できると考えてよい (右端が存在しないとしても変わらない)
- コマを移動させるとき、赤い区間の右端以外に動かす場合は考えなくてよい
これだけ単純化すれば、次の DP ができる。なお、各区間を黒い区間の左端の順にソートしておくこととする。
dp[i] ← 番目の黒い区間の左端から出発して到達できる地点の最大値
