393.1

慎重にやるだけ...。できれば苦労しないけど...。

250

K人の対象に対してすべてに順位付けをして投票する。各投票について順位が一番上の対象に投票されているとみなして集計し、過半数を取得した対象があればそれに決定し、そうでなければ最小得票数の対象を除去して繰り返す。選ばれる対象を答えよ、という問題。

愚直にやるだけ。

500

N個のライトの点灯パターンがいくつか与えられる。どのパターンかは分からないが、そのうちの一つを実行したときの結果のパターンがいくつか与えられるので、正常に動作しているか故障しているか判定不能かをそれぞれのライトについて答えよ、という問題。ただし矛盾がある場合はその旨答える。

どれかのパターンで動作したライトは正常に動作するはず。点灯パターンのどれかにマッチするはずだが、どれにおいても動作するはずのライトは正常に動作するか壊れているかのいずれか。後は判定できていないライトに対して推論を適用していくだけ。そのうち収束するはずなので、愚直にやるだけ。

1000

N個の地点がある。そのうちの一点を指定された時間に出発し、別の一点に指定された時間に到達するような物体が何パターンかある。各物体について、他の物体またはN個の地点からの距離の最小値を常に計算しておき、これの最大値を求よ、という問題。

バイナリサーチの回数だけ幾何やるだけ。