492.1

今年最後のSRMなんだけど、結局いまいちな結果に終わってしまった。

250

一直線上に木が立っているので、木の一番上の点が同一直線状に乗るように木を削るとき、少なくとも何本削らないとダメか答えよ、という問題。

直線として考えられるのは元の木のうちの任意の二本を通る直線。この直線のうち、木の一番上の点ができるだけ多く乗るものを探す。全部ダメだったら一番小さいのに高さを揃えるので、N-1本切らないとダメ。

550

見てない。

1000

二点間の移動コストが与えられる。二点間の移動を制限する値があり、その値とその値に移動コストを加えたものが、指定された区間に入っているときにのみ移動できる。移動の後にその値は移動コスト分だけ増分される。この値はコストNでN増やすことがでるが、N減らすにはNと固定のコストがかかる。このとき、目的地に向かって移動するときの最小コストを求めよ、という問題。

基本はダイクストラ。二点間の移動コストから全二点間の移動コストを計算する。(これはO(N^3)でできる。)こうすると、移動を制限する区間の先頭で移動するか末尾に間に合うように移動するかだけに変更できる。(ある点を経由してすぐに別の点に移動できるような場合、全二点間の移動コストが分かっているため、そのようなパスも別途計算される。)こうすると、現在位置と、前にいた位置と、制限の区間(前からか後からか)、という状態に変形できるので、後はダイクストラ。