Eまで五完。
F - Greedy Takahashi
解説動画を見てAC。
コンテスト中はGの方が解かれていたため飛ばしてしまったが、発想が難しい問題ではなかった。
ただ、実装は結構しんどいね。
あまり綺麗な実装を思い付けず、添え字でもミスってしまった。他の方のコードを見てこういう実装も勉強すべきかなぁ。
→ ダブリング解法だと実装がある程度大変になるのは仕方なさそう。
G - Power Pair
解説AC。
解説の論理は理解でき、ACはした。が、しっくりきてないので解説動画を見たい。
→ 結構すっきりしました。
H - Nim Counting
すぬけさんの解説動画を見てAC。
ただ、アダマール変換については理解できていない……。
とりあえず、
・愚直なDPによる解法
・xor畳み込みにより高速化できる
・アダマール変換の線形性を利用すると、等比数列の積の公式などを利用して計算できる。（線形性の証明は分かってないけど、定義から成り立ちそうな気はした）
というあたりは分かった。
分かっていないのはアダマール変換の部分。
一桁の場合は解説動画通りなので分かるけれど、二桁・三桁に拡張していくというところがよく分からない。拡張するとどうしてこういう式になるんだろう……。
いまだにFFTもピンと来てないし、畳み込みを理解するためにどうにかしないといけないんだよね。私でも理解できるような資料はないものか。
0 件のコメント:
コメントを投稿