
ABC193: E – Oversleeping を二分探索と Floor Sum で高速に解く
公式解説より良い計算量で解きます.二分探索と Floor Sum を組み合わせる所がなかなか面白いと思います.
公式解説より良い計算量で解きます.二分探索と Floor Sum を組み合わせる所がなかなか面白いと思います.
レポートや論文を書く上で役立つパッケージを紹介します.英文・和文のどちらでも使えると思います.
maspy さんに教えてもらった方針で解きました.公式解説よりシンプルだと思います.
yosupo さんの Library Checker に投げてみたところ,それなりに速かったので,実装したアルゴリズムを紹介します.
自分が使っている形式的冪級数ライブラリを紹介します.AtCoder Library の modint
と convolution
をベースにしています.
AtCoder の AGC 級コンテストの問題について,考察・解法のポイントをまとめます.ほぼ自分用メモです.随時更新します.
競プロでも使うミニマックス定理 $\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\}} $ のリグレット上界を証明します.基礎から解説します.
AtCoder の ARC 級コンテストの問題について,考察・解法のポイントをまとめます.ほぼ自分用メモです.随時更新します.
考察に使える問題と,実装に使える問題の両方を集めています.一部の問題には簡単な解説もつけています.
理解に時間がかかったので,既に多くの解説記事がありますが,自分が自然だと思う思考回路を書いておきます.
ABC の F 問題の中でもかなり diff が高い問題です. 線形代数の知識 + ライブラリを使って解きます. 公式解説とは結構違う考え方をしています.
「遅延伝播セグメント木の使い方」の記事ではカバーしきれなかったポイントを,練習問題を 3 問解きながら解消します.
遅延じゃない普通のセグメント木も知らない…という方が,lazysegtree
をブラックボックスとして使えるようになることを目標にした解説記事です.
AtCoder のコンテストで出題予定の問題と被ったことで話題になった問題の別解です. 行列のクロネッカー和の固有値などを使います.
良問だと評判の競プロの問題 Dinner (夕食) の解説です. 想定解法が天才的だと話題になりましたが,非天才的な方法で解いてみました.
2020/08/14 の yukicoder コンテストで writer を担当した際の感想です. 今後 writer をする方にとって有益だったらいいなパート(?)とポエムパートに分かれています.
大学入試の難問を,大学の知識を使って機械的に解きます. 競プロっぽさのある問題です. ガウスの消去法や巡回行列の固有値が登場します.
「桁 DP,解法は分かるけど実装が破滅する...」という方に向けて,バグりにくい実装方針を例題とともに紹介します. AtCoder 水色〜青色程度の方を対象にしています.
グラフに関連した線形方程式を解くアルゴリズムの解説です. これをライブラリ化しておけば,いくつかの問題がほぼコピペで解けるようになります.