Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）Eまで。FとGを行き来して、結局Fで5WAが取れず終了。
B 実装問題だがどう書くか迷った
C bit全探索
D DP
E 01BFS

— titia (@titia_til) February 11, 2023

F - Teleporter Takahashi

　解説AC。

　コンテスト後、乱択で良いのでは？　と思って実装するもWAやTLEがでてしまい、解説を見た。

　結論からいうと、乱択でも解けるが、結構ケアしなくてはいけない部分が多かった。

・二回の操作をセットにする。二回操作した結果、近付いていたら採用する

・[a, b], [c, d]の範囲で乱択しても上手くいかない。[a, a+1], [c, c+1]で乱択すると良かった。（2*2の範囲があれば偶奇が一致する点ならどこへでもいける）

・a=bやc=dについてケアしなくてはダメ。奇数でないとたどりつけないなら、最初に一回処理しておく

　とすればACできた。

　ただこれでは、解説にある内容大体が分かっていないと書けないので、乱択のうまみはあまりない。

G - Shopping in AtCoder store

　Convex Hull Trickという情報を得てAC。ただ、書き方を忘れていて実装に苦戦した。

　今回は、はじめに必要な直線群が何かを調べ、その後、三分探索によって答えを求める、という方針で解いた。直線群を求めるところ（外積を使って不要な直線を消去する部分）は同じ処理でできることに気を付けよう。

　その上で、max/minを知りたいindexが単調ならdequeを使って処理することができる。（今回も、クエリソートすればそうやって処理が可能）