
AGC018: C – Coins を離散凸解析(L 凸関数最小化)で解く
プログラミングコンテストで出題されたある問題を離散凸解析を使って解きます.解法を理解・実装するために必要な離散凸解析の知識も説明します.
プログラミングコンテストで出題されたある問題を離散凸解析を使って解きます.解法を理解・実装するために必要な離散凸解析の知識も説明します.
ペナルティ関数法,拡張ラグランジュ関数法,ADMM の 3 手法を「ラグランジュ関数」を用いて自然に導出します.
代数学の知識を仮定せずにバーンサイドの補題(コーシー・フロベニウスの補題)の解説と証明をします.例題もあります.
Mac で TopCoder を始めるのにとても苦労したので備忘録を書きます.
公式解説より良い計算量で解きます.二分探索と Floor Sum を組み合わせる所がなかなか面白いと思います.
レポートや論文を書く上で役立つパッケージを紹介します.英文・和文のどちらでも使えると思います.
maspy さんに教えてもらった方針で解きました.公式解説よりシンプルだと思います.
yosupo さんの Library Checker に投げてみたところ,それなりに速かったので,実装したアルゴリズムを紹介します.
自分が使っている形式的冪級数ライブラリを紹介します.AtCoder Library の modint
と convolution
をベースにしています.
競プロでも使うミニマックス定理 $\dis \red{\min_{x \in X} \max_{y\in Y} f(x,y) = \max_{y\in Y} \min_{x \in X} f(x,y)}$ の面白い証明を紹介します.
オンライン近接勾配法 $\dis x_t = \red{\argmin_{x\in \R^d} \Big\{ \inner{p_{t-1}}{x} + g(x) + \frac{\eta_t}{2}\|x - x_{t-1}\|^2 \Big\}} $ のリグレット上界を証明します.基礎から解説します.
考察に使える問題と,実装に使える問題の両方を集めています.一部の問題には簡単な解説もつけています.
ABC の F 問題の中でもかなり diff が高い問題です. 線形代数の知識 + ライブラリを使って解きます. 公式解説とは結構違う考え方をしています.
「遅延伝播セグメント木の使い方」の記事ではカバーしきれなかったポイントを,練習問題を 3 問解きながら解消します.
遅延じゃない普通のセグメント木も知らない…という方が,lazysegtree
をブラックボックスとして使えるようになることを目標にした解説記事です.
AtCoder のコンテストで出題予定の問題と被ったことで話題になった問題の別解です. 行列のクロネッカー和の固有値などを使います.
良問だと評判の競プロの問題 Dinner (夕食) の解説です. 想定解法が天才的だと話題になりましたが,非天才的な方法で解いてみました.
2020/08/14 の yukicoder コンテストで writer を担当した際の感想です. 今後 writer をする方にとって有益だったらいいなパート(?)とポエムパートに分かれています.
大学入試の難問を,大学の知識を使って機械的に解きます. 競プロっぽさのある問題です. ガウスの消去法や巡回行列の固有値が登場します.
「桁 DP,解法は分かるけど実装が破滅する...」という方に向けて,バグりにくい実装方針を例題とともに紹介します. AtCoder 水色〜青色程度の方を対象にしています.