AtCoder Beginner Contest 396

　Fまで。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 396 Fまで。Eで詰まったのは良くない。
B stack
C Bは累積和、Wは累積和の累積max
D 使ったマスと今いるマスを見て全探索。再帰で書いた。
E bitごとに見る。連結成分ごとに見る。
F 最初の転倒数を求め、Mになるところで値が変化。遅延セグ木で管理。

— titia (@titia_til) March 8, 2025

G - Flip Row or Col

　解説放送を見てAC。

　一回解説放送を見も二回できず、もう一度見返してAC。それほど難しい考え方ではないはずなのだが、理解に苦労した。

　なお、アダマール変換は（アダマール変換を使う解法も）理解できていない。

Codeforces Round 1034 (Div. 3)

　ギリギリ全完。

　Cが難しかったのだが、難しかったといっている人が少なかった……。

　Gは、最初の提出がTLEになったとき諦めかけたが、STATUSを見るとPyPyでもACがたくさんあったので高速化した。一番きいたのは無意味なgcdをなくしたところ。gcdのlogは軽いから関係ないかな～と書いていたが、オーダーレベルでの改善であれば効果があった。

コンテストへのリンク

コンテスト後のツイート

F 大きい素数pから順に、使っていないpの倍数たちをぐるぐるした。
G mの約数それぞれについて調べる。各gcd(m,k)について、A[i]はA[i-1]から何個大きくしなくてはいけないかが分かる。A[i]を変更したとき、変わるのは前後二ヶ所だけ。

— titia (@titia_til) July 1, 2025