393.1

今回からサマータイム。比較的過ごしやすい時間になりました。それでも結構しんどいですが...。

250

N人の候補者がいる時に、優先順序付きで投票を行い、過半数票を得る人が出るまで、得票数の一番少ない人を除去していく、という非常にありがちな問題。

書いてある通りに実装しましょう。既に除去した人は0票になるから、0票の人を除去しないルーチンにしてしまったので、除去忘れが発生して間違えた...。昔同じような問題を解いた記憶はあるのですが...。

500

複数個のランプの点灯パターンが与えられ、実際に観測された点灯パターンから、どのランプが壊れているか(つかないか)判定せよという問題。

一回でもついたランプは故障していない。で、ついたランプが特定のパターンと完全に一致するもののどれかが観測されたものなので、そのいずれにおいても点灯しているものがついていなければ、そのランプは壊れている。それ以外は分からない。ついたランプがどのパターンにもマッチしない場合には矛盾すると答えておく。

要はこれで正しいと判断できるかどうかで、実装自体は余り苦にならない問題。2次元配列使えばいいのに、longの1次元配列使ってややこしくしたような気がする...。

1000

空港から飛行機に電波を出す。また、飛行機は別の飛行機に電波を届けることが可能である。この状況で、すべての飛行機が常に電波の届く状態にしておくために必要な、電波の届く距離を最小にせよ、という問題。

電波の届く距離についてバイナリサーチ。時系列順に、ある飛行機がある空港から電波の届く範囲に出入りしたり、飛行機間で電波が届く距離に出入りしたりというイベントをソートする。後は、そのすべての状況において、すべての飛行機が空港と結合しているかどうかを判定すれば良い。

ひたすら実装あるのみ。250に手間取って(結果的に間違って)全然終わる見込みなし。解き方分かっただけいいか...。