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。それほど難しい考え方ではないはずなのだが、理解に苦労した。

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

AtCoder Beginner Contest 212

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

F - Greedy Takahashi

　解説動画を見てAC。

　コンテスト中はGの方が解かれていたため飛ばしてしまったが、発想が難しい問題ではなかった。

　ただ、実装は結構しんどいね。

　あまり綺麗な実装を思い付けず、添え字でもミスってしまった。他の方のコードを見てこういう実装も勉強すべきかなぁ。

　→　ダブリング解法だと実装がある程度大変になるのは仕方なさそう。

　

G - Power Pair

　解説AC。

　解説の論理は理解でき、ACはした。が、しっくりきてないので解説動画を見たい。

　→　結構すっきりしました。

H - Nim Counting

　すぬけさんの解説動画を見てAC。

　ただ、アダマール変換については理解できていない……。

　とりあえず、

・愚直なDPによる解法

・xor畳み込みにより高速化できる

・アダマール変換の線形性を利用すると、等比数列の積の公式などを利用して計算できる。（線形性の証明は分かってないけど、定義から成り立ちそうな気はした）

　というあたりは分かった。

　分かっていないのはアダマール変換の部分。

　一桁の場合は解説動画通りなので分かるけれど、二桁・三桁に拡張していくというところがよく分からない。拡張するとどうしてこういう式になるんだろう……。

　いまだにFFTもピンと来てないし、畳み込みを理解するためにどうにかしないといけないんだよね。私でも理解できるような資料はないものか。