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

A,Bしか解けないという情けない結果でしたが入茶しました．

A - UFO襲来

【解法1：ゼロ以上の切片の最大値】
直線「UFO - 遮蔽物上端」の傾きから切片を求める．ゼロ以上の切片のうち最大値が答え．
Editorial - ZONe Energy Programming Contest

【解法2：傾きの最小値】
直線「UFO - 遮蔽物上端」の傾きの最小値を求めると

\begin{aligned}
\max(0, H-(\text{傾きの最小値})\times D)
\end{aligned}

が答え．

今の実力ではできない問題でした．答えはわかりやすいです．
Editorial - ZONe Energy Programming Contest

総合力がx以上になるか判定する関数（check(x)）をつくる．
- N人の能力値がx以上なら1，未満なら0に変換する．Sをset()にすることで重複がなくなり，2^5=32通り以下になるので，3人の組み合わせを全探索できる．
- 3人のうち誰か1人がx以上の能力値を持っていれば（ビットが1なら）チームの能力もx以上（ビットが1）→3人の能力値のOR演算を取れば良い
- すべての能力値がx以上なら，総合力もx以上→3人の能力値のOR演算で，全てのビットが1であればよい
- ORをとって5つ全てのビットが1（31=sum(1 << i for i in range(5))）になる組み合わせがあればTrue．
check(x)を使って，xについて二分探索する．初期値は確実に可能な0と，確実に不可能な10**9 + 1．

【2021.05.05追記】
以下のCable masterが，まさにこの解き方でした．
Pythonで蟻本3-1 - 二分探索 - 競プロはじめました

この前のABC199 C - IPFL（AtCoder Beginner Contest 199 - 競プロはじめました）と類似の問題です．文字の反転は最後に1回やれば良いです．

今回大きく違うのは，文字の追加・削除が先頭か末尾にしか起きないことです．

結局，リストでいじってTLEから抜け出せませんでした．

deque というデータ構造を使うと間に合うようです．
Editorial - ZONe Energy Programming Contest