AtCoder Beginner Contest 265

　Eまで五完だが、Eは嘘でした。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 265 EまでACしたけどEは嘘解法。
A Y円払う回数全探索
B,C シミュレーション
D 二分探索
E https://t.co/GyNtjNzmsIと同じようにやったら通った。自分のコードでは(i,j,k)で障害物にぶつかるものを列挙しているので、300^6の計算量のはず。（簡単に落ちるケースを作れた）

— titia (@titia_til) August 21, 2022

E - Warp

　解法ツイートを見て改めてACした。

　（A, B）をi回、(C, D)をj回、(E, F)をk回使ったときは何通り？　という非常に自然なDPで良かった。

　最初見たとき包除原理に見えてしまい、そこから方針転換できなかったのは反省。

F - Manhattan Cafe

　解説放送を見てAC。

　単純なDPを累積和で高速化する問題だが、単純なDPすら思いつかなかった。

　というか、そもそも誤読していた。（格子点の数も二つだけと思ってなかったし、制約ももっと大きいものと思っていた）

　N次元空間などと言われると、苦手意識があるためまともに考えられなくなる気がする。空間把握などが必要な問題が解けないのは仕方ない部分もあるが、今回の問題は、定義に従ってDPを組むだけなので、空間把握などは不要な問題だった。

　苦手意識があると、つい考えることをやめてしまいたくなるが、ちゃんと問題を読み、定義に従って考えよう。

G - 012 Inversion

　解説放送を見てAC。

　セグ木を使いそう、というのは一目で分かった。セグ木の各要素として何を持てば良いか、というところで詰まってしまったが、これも自然に考えれば分かるものだった。落ち着いて考えれば自力で思いつけたと思う。

　ただ、実装には苦戦した。遅延セグ木を使うのだが、可換性が成り立たない演算があるため、自分のライブラリ（これ自体あまり整備されていないのだが）を修正しないといけない部分が多かった。この辺は慣れておきたい（遅延セグ木の整備もすべきか……）。

　難しくはないのだが、実際に通すのは結構大変。