問題解説 [Xmas Contest 2020] E – Eternal Dice
概要
問題文 → ■公式解説 → ■自分の提出 → ■ （$\Theta(N\log^2N)$ 時間）
解説で OEIS が引用されていた部分の補完など．
解法
$ \left(\frac{\sin \pi(\sqrt{1-x...
maspy
問題解説 Library Checker [Library Checker] Matrix Prooduct (Mod 2)
問題概要
問題文 → ■ 自分の提出 → ■ （212ms）
この問題は，実行時間に占める入出力の割合が比較的大きいです．
本記事内での私の提出では，入出力に 180 ms 程度を要しているようです．実行時間を比...
Library Checker [Library Checker] Point Set Tree Path Composite Sum
問題概要
問題文 → ■, ■自分の提出 → ■（根付き木, 169 ms），■ （全方位，332 ms）
Static Top Tree （以下 STT）と呼ばれるデータ構造を用いた解法の実装例について解説します．
S...
Library Checker [Library Checker] Rational Approximation
問題概要
問題文 → ■自分の提出 → ■ （35 ms）
一発書きで fastest （2024/08/27）になったのは意外でした．
解法
以下，有理数と言えば非負であることを仮定し，有理数 $a/b$ のよう...
問題解説 [ijpc2015] E – Верный
概要
問題文 → ■公式解説 → 見つからず自分の提出 → ■
問題文について
「'a'から'j'までのどれかの小文字のアルファベットが一つ書かれている」とありますが，正しいです．アルファベットが 10 種類であると仮定した...
問題解説 [nadafes2022] P – Turn it Over
概要
問題文 → ■公式解説 → ■自分の提出 → ■
大筋は公式解説と同じだと思います．使った計算のテクニックは少し違いました．
2024年に知られた手法を見たことのない感じの使い方をしました．
解法
長さ $M$ の区間を...
問題解説 [JOI] F – とてもたのしいたのしい家庭菜園（JOI 2024 春合宿）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
解法 （時間計算量 $\Theta(N\log N\log A)$）
二分探索します．次が $\Theta(N\log N)$ 時間で解ければよいです．
$(A_1...
問題解説 [JOI] B – 神経衰弱（JOI 2016 春合宿）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
解法
公式解説とたぶん違ったので書いておきます．
次の状態を保持するようにします．
答が分かっていないカードが $2n$ 枚あり，これらは Flip...
問題解説 [JOI] C – Mansion（JOI Open Contest 2012）
概要
問題文 → ■公式解説 → 存在するか分からず自分の提出 → ■
まず読解がちょっと難しかった．サンプル 1 はこんなのです．
解法
同じグラフがグリッド状に並んでいて最短路問題となっています．まずひとつのグラフ...
問題解説 [JOI] B – Jumps（JOI Open Contest 2012）
概要
問題文 → ■公式解説 → 存在するか分からず
提出したら IE になってしまった．2024年8月12日現在，正しくジャッジされていないと思います．
→ 2024年8月21日修正されました．解答例
解法
すべての点が同一...