競プロ解説

AGC018: C – Coins を離散凸解析(L 凸関数最小化)で解く

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

2021/06/18
数理工学

制約付き最適化の 3 手法を統一的に導出する ラグランジュ関数の視点から

ペナルティ関数法,拡張ラグランジュ関数法,ADMM の 3 手法を「ラグランジュ関数」を用いて自然に導出します.

2021/05/25
競プロ解説

バーンサイドの補題(コーシー・フロベニウスの補題)の解説と証明

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

2021/04/24
未分類

TopCoder の始め方 (macOS)

Mac で TopCoder を始めるのにとても苦労したので備忘録を書きます.

2021/05/02
競プロ解説

ABC193: E – Oversleeping を二分探索と Floor Sum で高速に解く

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

2021/05/23
未分類

LaTeX おすすめパッケージ集 with 使い方

レポートや論文を書く上で役立つパッケージを紹介します.英文・和文のどちらでも使えると思います.

2021/03/20
競プロ解説

ABC050 / ARC066: D – Xor Sum メモ化再帰による解法

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

2021/03/24
競プロ解説

形式的冪級数(FPS)の inv,log,exp,pow の定数倍の軽いアルゴリズム

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

2021/03/24
競プロ解説

形式的冪級数(FPS)ライブラリの実装例(C++)

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

2021/03/20
数理工学

ミニマックス定理の意味と初等的証明

競プロでも使うミニマックス定理 $\dis \red{\min_{x \in X} \max_{y\in Y} f(x,y) = \max_{y\in Y} \min_{x \in X} f(x,y)}$ の面白い証明を紹介します.

2021/03/24
数理工学

オンライン最適化とは? オンライン近接勾配法のリグレット上界

オンライン近接勾配法 $\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\}} $ のリグレット上界を証明します.基礎から解説します.

2021/03/20
競プロ解説

形式的冪級数(FPS)が使える AtCoder の問題リスト(随時更新)

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

2021/03/20
競プロ解説

ABC155: F – Perils in Parallel 解説

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

2021/03/20
競プロ解説

遅延セグ木に慣れる AtCoder の練習問題 3 問

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

2021/03/20
競プロ解説

遅延伝播セグメント木の使い方,ACLPC: K – Range Affine Range Sum の解説

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

2021/05/18
競プロ解説

Eternal Tours(yukicoder No.1241)を線形代数で殴る

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

2020/10/28
競プロ解説

AOJ2642: Dinner(夕食)の非天才解法

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

2020/10/28
競プロ感想

初めての競プロ作問(yukicoder)

2020/08/14 の yukicoder コンテストで writer を担当した際の感想です. 今後 writer をする方にとって有益だったらいいなパート(?)とポエムパートに分かれています.

2021/03/20
数学

2016年京大理学部特色入試第3問(コインの問題)を線形代数で機械的に解く

大学入試の難問を,大学の知識を使って機械的に解きます. 競プロっぽさのある問題です. ガウスの消去法巡回行列の固有値が登場します.

2020/10/28
競プロ解説

桁 DP の簡潔な実装

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

2021/04/03
タイトルとURLをコピーしました