345.1

難易度がおかしいセット...。

250

x軸y軸に沿って道がある。x軸に沿ってy座標が奇数のところではx軸方向にマイナスの向きにしか進めず、y軸に沿ってx座標が奇数のところではy軸方向にマイナスの方向にしか進めず、それ以外は逆向きにしか進めない。目的地までの最短距離を答えよ、という問題。

ある程度近くまで移動してから、探索しても良さそうな雰囲気。

500

いくつかの箱の上に石がいくつか乗っている。二人で交互に石を一つずつどける。箱の上にある最後の石をどけると、箱の中身をもらうことができる。相手が最適に行動するとして、自分はどれだけもらうことができるか答えよ、という問題。

取り敢えず、一個しか乗っていないものは例外処理。それ以外は残りの石の数の偶奇で決まる。やるだけ。

1000

N個の都市にいくつかの拠点を置き、拠点のない都市から拠点への距離の最大値を最小化したい。このとき、その値を求めよ、という問題。

可能かどうかを距離を二分探索しつつ求めれば良い。N個の都市には高々N本しか辺がないことを使ってうまくやる問題らしい。詳細不明。