240.1

高速化のためのトリックのつもりが、低速化につながるケースもあるので、メモ付き探索では注意が必要？

250

N回の乗継で目的地を目指すとき、最速で目的地に着くときの時間を答えよ、という問題。各乗継に、可能な開始時刻と終了時刻が与えられる。

各乗継で現在時刻から一番早く次の乗継を開始できる時刻を求めるだけ。

600

山の断面図が与えられるので、断面上の任意の点から見ることのできる点のうち、山から垂直方向に一番近い点までの距離を求めよ、という問題。

山の断面上の任意の点から見える点というのは、断面の各パーツを延長したすべての直線よりも上側にある領域になる。各部分について一番上にある直線を求め、山の断面との距離を計算して最小の点を求めれば良い。

900

N個の連続データをそれぞれ目的の場所に移動させる。同じ移動先の連続するデータはまとめて移動することができ、移動したデータのあった部分は詰めてそれ以降考える。このとき移動を終了させるのに必要な最小の移動回数を求めよ、という問題。

ある分割されたデータをまとめて移動させるためには、その間にあるデータをすべて移動させる必要がある。すべての分断されたものについて、間を移動させる処理をメモしながら試せばおしまい。状態は移動先をフレッシュなアルファベットにでも置き換えて文字列として処理すれば良い。

この文字列をさらにアルファ変換(abaとbabは同じになるような変換)をしてやることで、メモの効率を高めようとしたところ、アルファ変換のコストがそこそこ大きかった模様。(もしくはアルファ変換の関係で余計ヒットしなくなったということも考えられる？)そもそも選択される領域の数はそんなに多くないのと、同じ場所が選択されたときに処理を繰り返さなければいいので、そのままメモすれば十分な速度で終わるらしい。

そもそも、i番目からj番目までのデータを移動するコストをDPで計算すればおしまいみたい。i番目からj番目までのデータを移動するコストはi+1番目からj番目までのコスト+1か、i番目のデータとk番目のデータの移動先が等しい時にi+1番目からk番目までのコストとk番目からj番目までのコストの和のうちの最小値。