競プロ解説

競プロ解説

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

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

競プロ解説

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

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

2021/03/02
競プロ解説

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

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

2020/12/21
競プロ解説

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

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

2020/12/17
競プロ解説

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

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

2020/11/21
競プロ解説

TDPC: I – イウィ 解説

理解に時間がかかったので,既に多くの解説記事がありますが,自分が自然だと思う思考回路を書いておきます.

2021/03/03
競プロ解説

ABC155: F – Perils in Parallel 解説

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

2020/10/28
競プロ解説

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

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

2021/02/11
競プロ解説

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

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

2021/01/22
競プロ解説

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

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

2020/10/28
競プロ解説

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

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

2020/10/28
競プロ解説

桁 DP の簡潔な実装

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

2021/01/31
競プロ解説

接続行列を係数にもつ線形方程式 (PDF)

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

2021/02/20
競プロ解説

ABC163: F – path pass i 解説 (PDF)

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

2020/10/28
タイトルとURLをコピーしました