N個の点を表す数列Xが与えられる。このうちのいずれかの点がオフィスだが、その点がオフィスであるかどうかは実際に訪れるまでわからない。ここで座標0からスタートし一定の速度vで一次元上を動き回るとき、どこにオフィスがあった場合でも必ずabs(Xi)以下の時間でオフィスにたどり着くようにしたい。最適な移動をしたとき取りうる最小の速度vを求めよ。問題の二分探索臭がすごいので二分探索を考える。すると解くべき問題は「速度vを決め打つ。速度vで最適に動き回ったとき、Xのすべての点に時間abs(Xi)以下でたどり着くことは可能か」となる。ここで移動の特性を考えると点aから点bに移動したときa-b間にある点はすべてついでに取れるこのことから移動のパターンは「必ず外側が広がっていくようにジグザグに移動する」しかない(飛び地での移動も既に訪れた区間の内部をまた訪れるのも無意味)ということがわかる。これを生かすと以下の区間DPが生える。上の特性からこのdpは外側に広がって区間を伸ばすような遷移しか考える必要がない。遷移は(左端or右端)×(左端or右端)の以下4パターンとなる。(右端から右に一個進む)遷移の際現在決め打っている速度で新たな点Xに時間abs(X)以内で到達できない場合は題意が満たされずその遷移は取れないのでスルーする。してにぶたんを回していく。なるとつまりジグザグが広がっていく形か~→それyukicoderでやったやつじゃんとなって区間DPが生えた。1~Nまでの番号がついたN個のパネルがある。N個のタスクと2つの部屋がある。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。