197.1

250

チェスのナイトの動きで、与えられた点すべてに移動できる点をすべて答えよという問題。

候補の地点は最初の点から移動できる8点で、それぞれについて残りの点に移動できるかどうかを判定すればおしまい。

600

グラフ上で始点から終点までのパスの取り得る長さのうち、2番目に短いものを答えよという問題。

各点について、到達時のコストとして可能なものをすべて覚えておく。値の範囲はグラフを2周するものがあり得るので最大枝コストと点数の積の倍程度で、問題制約から1000よりちょっと少ないくらい。同様にパス長は100くらい必要。さらにすべての枝について吟味する必要があり、枝は点数の二乗だけ存在する。これを真面目に計算すると250MステップくらいになりTLEになる。

実際には各点のうち実現可能なコストについてのみすべての枝を吟味すれば良く、実現可能なコストがかなり疎なのでTLEはしない。(もしかすると悪い例がたまたま入っていなかっただけのような気もするけれども。)

1000

ロボットが水をまく。目的地と井戸の上にはいけない。井戸と目的地に隣接した時に、水を回収したりまいたりできる。水の出し入れや場所の移動のコストを1としたときに、水をまく最小コストを答えよという問題。

目的地は高々4つしかないので、それぞれを巡回する順番を全通り試し、そのうち最小のものを答えれば良い。各巡回路における最小コストは、残り必要な水の量と持てる水の量のうちで最小のものを井戸に回収しに行き、目的地に巡回することを考えると、巡回するべき地点の順番、つまり井戸と各目的地をどのように巡回するかが分かるので、それらに隣接する点すべてを吟味して最小コストをBFSでもすればいいと思う。