AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)

　Fまで。

　Fは初めから解法は合っていたので、どうしたら良かったのか悩む。定数倍高速化を頑張るより、codonを試す方が良いんだろうか？

コンテストへのリンク

コンテスト後のツイート

F DPと復元をやるだけ。だが、普通に書くとPyPyだとTLE&MLE。高速化しても2caseでTLEが取れず困ったし、ランダムテストしてもどういうケースで落ちているか分からない→ダメ元でcodonで提出したらACした。えー。
G 遅延セグ木で解けそうだが……。

— titia (@titia_til) January 17, 2026

G - Takoyaki and Flip

　解説・解説放送を見てAC。

　遅延セグメント木を使うとは分かっていたが、基本的なことからおかしかった。

　もつデータを（最大値, flipしているか）だけで良い気がしていたが、それだと、複数の皿が「全て表か、全て裏か」の二通りの状態しか表せないので明らかに間違っている。

　それを解消するため、表の皿が何枚で裏の皿が何枚か、というのをもつようにすれば自然と遅延セグメント木に乗る。

　ただし、遅延させるものは、

・(a, b)　a回flipした後、b加算

　なのだが、(a, b)の後に(c, d)を行うのと、(c, d)の後に(a, b)を行うのとで結果が違うことに注意が必要だった。

　自分が解いてきた問題は、ここが可換なことが多かった気がする。順番に注意しなくてはいけなかった。

　ところで、PyPyだと1873msなのだが、codonだと301msでした。codon凄い！