競プロ解説

プログラミングコンテストで出題されたある問題を離散凸解析を使って解きます．解法を理解・実装するために必要な離散凸解析の知識も説明します．

代数学の知識を仮定せずにバーンサイドの補題（コーシー・フロベニウスの補題）の解説と証明をします．例題もあります．

公式解説より良い計算量で解きます．二分探索と Floor Sum を組み合わせる所がなかなか面白いと思います．

maspy さんに教えてもらった方針で解きました．公式解説よりシンプルだと思います．

yosupo さんの Library Checker に投げてみたところ，それなりに速かったので，実装したアルゴリズムを紹介します．

自分が使っている形式的冪級数ライブラリを紹介します．AtCoder Library の modint と convolution をベースにしています．

考察に使える問題と，実装に使える問題の両方を集めています．一部の問題には簡単な解説もつけています．

ABC の F 問題の中でもかなり diff が高い問題です． 線形代数の知識 + ライブラリを使って解きます． 公式解説とは結構違う考え方をしています．

「遅延伝播セグメント木の使い方」の記事ではカバーしきれなかったポイントを，練習問題を 3 問解きながら解消します．

遅延じゃない普通のセグメント木も知らない…という方が，lazysegtree をブラックボックスとして使えるようになることを目標にした解説記事です．

AtCoder のコンテストで出題予定の問題と被ったことで話題になった問題の別解です． 行列のクロネッカー和の固有値などを使います．

良問だと評判の競プロの問題 Dinner (夕食) の解説です． 想定解法が天才的だと話題になりましたが，非天才的な方法で解いてみました．

「桁 DP，解法は分かるけど実装が破滅する...」という方に向けて，バグりにくい実装方針を例題とともに紹介します． AtCoder 水色〜青色程度の方を対象にしています．

グラフに関連した線形方程式を解くアルゴリズムの解説です． これをライブラリ化しておけば，いくつかの問題がほぼコピペで解けるようになります．

ABC163: F - path pass i の解説です． 「自然な発想」にこだわり，AtCoder 水色程度以上の方が理解できるように丁寧に書きました．