ZONeエナジープログラミングコンテスト “HELLO SPACE”参加しました。

A - UFO襲来

S[i] = "Z", S[i+1] = "O". S[i+2]="N", S[i+3]="e"とすればok

解説 - ZONeエナジープログラミングコンテスト “HELLO SPACE”

B - 友好の印

公式解答通りでした。

座標空間(縦をh, 横をd)として、UFOと遮蔽物を結ぶ直線を考えます。この直線の切片が求めたい値になります.
直線は$ h = \frac{H - h_i}{D - d_i}d + ans$となります。 ansが求めたい切片です。

各遮蔽物を見ていって、ansが最大になるようにします。

また、図を書くとわかりますが、UFOと遮蔽物の頂点を結ぶ直線を考えたとき、「どの遮蔽物にもぶつからないとき」=「ansが最大になる」ことがわかります。

解説 - ZONeエナジープログラミングコンテスト “HELLO SPACE”

D - 宇宙人からのメッセージ

毎回文字列を反転させていると時間を食うので、ここはABC199の C - IPFL と同じようにします。つまり、反転したかどうかをbool値一つに保存しておきます。このbool=trueなら、最後にTを反転して出力すればいいです。

末尾に付け加える部分は、反転していなければ末尾に、していれば先頭に付け加えれば辻褄が合います。

連続2文字を消すのは、末尾に追加し終わってからやってもいいんでしょうけれど、色々とめんどくさかった(連続する文字列を消す操作を1度しかしないと、消した後で2文字が連続するケースがあるので、何度も繰り返し処理しないといけない)ので、以下の解答のように、末尾や先頭に付け加えるときに、付け加えた結果文字が連続にならないように処理しました。
Message from Aliens [ZONeエナジープログラミングコンテスト “HELLO SPACE” D] - はまやんはまやんはまやん

なおC#で組んでいたら、Last()の処理でハマったので、TLEを出してしまった。これは別記事にしてあります。

LinkedListのLast(), Lastプロパティの速度比較について - umem0chiの日記

C - MAD TEAM

2分探索っぽいと思っても、そこから先をどう落とし込めばいいのか全然わからなかった問題。
結局以下の解答を真似ました。
MAD TEAM [ZONeエナジープログラミングコンテスト “HELLO SPACE” C] - はまやんはまやんはまやん

各人の情報をlim以上かどうかの5bitに圧縮して、bitパターンの総数(32通り)の3乗だけ調べればいいというのが、素敵だと思いました。ここまでいらない情報を削ぎ落としちゃってもいいんですね~

解説 - ZONeエナジープログラミングコンテスト “HELLO SPACE”

まとめ

二分探索は慣れが必要だと思う。