ZONeエナジープログラミングコンテスト “HELLO SPACE”のきろく

ZONeエナジープログラミングコンテスト “HELLO SPACE”に参加、レートを大幅に冷やしてしまいました...

A - UFO襲来 / UFO Invasion (100点)
B - 友好の印 / Sign of Friendship (200点)
D - 宇宙人からのメッセージ / Message from Aliens (300点)
C - MAD TEAM (400点)
E - 潜入 / Sneaking (500点)
F - 出会いと別れ / Encounter and Farewell (600点): 未提出
結果、感想

A - UFO襲来 / UFO Invasion (100点)

長さは $12$ 文字なので愚直に書くこともできますがfor文を用いてi文字目から4文字の部分文字列がZONeであるかどうかを判別すればいいです。

B - 友好の印 / Sign of Friendship (200点)

距離 $d,$ 高さ $h$ の遮蔽物が邪魔にならないのはUFOと遮蔽物の上端を結ぶ直線とタワーの交点以上上った時であり、その高さを $x$ とすると三角形の相似より $h-x:d = H-x:D$ 依り $\displaystyle x = \frac{Dh-Hd}{D-d}$ であるため答えは $\displaystyle \max\left\{0,\,\max_{i} \frac{Dh_i-Hd_i}{D-d_i}\right\}$ となります。

D - 宇宙人からのメッセージ / Message from Aliens (300点)

実際に文字列を反転させるのは文字列長ほどの計算量を要するので時間がかかります。反転しているかどうかbool型の変数を用意しておき、その状態に合わせて前後から文字を追加できるようにdequeを利用します。
後半の同じ文字を取り除くのは文字を1文字ずつ取り出していくとき、答えの文字列の末尾と追加する文字が同じときに取り除き、そうでないときそのまま追加するとすることによって実現することができます。

C - MAD TEAM (400点)

最小値の最大化なので二分探索であることは思いつきましたがそれに必要な判定方法をコンテスト中に思いつくことができませんでした。
答えが $x$ 以上かどうかを考える時各人の各能力が $x$ 以上かどうかしか考える必要がなく、5 bitの数と考え、状態を圧縮し、3人を選んだ時に全てがtrueになるかどうかを判定すればいいことが分かります。3人を選ぶときは各人の5 bitの数を集合などに入れてやることで高々 $32$ 種類しか考える必要がなくなり、そこから重複を許して3つ選んでやることでOKかどうか分かります。

E - 潜入 / Sneaking (500点)

愚直に辺を張ると辺の本数が $O(R^2C)$ となり、Dĳkstra法でも間に合わないなと考えていました。何かこれでも通る人は通るみたいですね...~~通しとけばよかった~~

$x$ 軸の負方向への移動は $+1$ がなければ隣の頂点へのコスト $1$ の辺で表すことができます。そこで頂点を2階層とし、 $x$ 軸の負方向への移動だけは2階層目で、その他は1階層で行うことにします。1階層から2階層の対応する頂点へはコスト $1,$ その逆はコスト $0$ とすることで、問題文の移動を $O(RC)$ 本の辺で表現することができ、Dĳkstra法で十分間に合う本数になります。