問題解説 [KUPC2019] I – encode/decode 2019
概要
問題文 → ■公式解説 → 存在するか分からず自分の提出 → ■
個人的に，クエリ回数 $8000～15000$ 回くらいの解法ばかり思いついて大変でした．ものによってはある程度実装してみないとクエリ回数が見積もれないのも大変．
...
maspy
問題解説 Library Checker [Library Checker] Nim Product
問題概要
問題文 → ■ 自分の提出 → ■（89ms）
（非想定解などで）定数倍バトルになることを複数回経験したので，Library Checker 最速周辺の実装を勉強しました．過去に取り組んだときには最速実装が理解できな...
問題解説 [JAG2015 Summer Day3] A – Analyzing Bit (Yet Special) Strings
概要
問題文 → ■公式解説 → 存在するか分からず自分の提出 → ■
出典は Gennady Korotkevich Contest 1 (Petrozavodsk Summer 2013) だと思われますが，解説がどこかに存在するのか...
問題解説 [CODE FESTIVAL 2015 エキシビション] B – TRAX
概要
問題文 → ■公式解説 → 存在するか分からず自分の提出 → ■
色のない状態で非自明な図を書いたりして，全然解けそうにないと思っていたんですが，曲線に色がついていることがめちゃくちゃ重要だった．
部分点解法
す...
問題解説 [yukicoder] No.2876 Infection
概要
問題文 → ■公式解説 → ■自分の提出 → ■
素直に $O(N\log N)$ 時間になるので一応書きます．
$p=x/100$, $q=1-p$ とします．
$N$ 頂点の有向グラフを，各 $(i,j)$ について確率 $p$...
問題解説 [yukicoder] No.2810 Have Another Go (Hard)
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説より簡潔な気がする．
解法
すごろくの設定で説明します．状態数 $12NM$ の dp で解くことを考えます．
dp は，次のような状態 $(i,j,k)$...
問題解説 [jag2015autumn] G – Cube Dividing
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説の理解に失敗しましたが，たぶん別解法っぽいので一応書いておきます．
解法
$z$ 方向には座圧しておきます．$z$ での断面を考えます．
各断面は...
問題解説 [Xmas Contest 2020] E – Eternal Dice
概要
問題文 → ■公式解説 → ■自分の提出 → ■ （$\Theta(N\log^2N)$ 時間）
解説で OEIS が引用されていた部分の補完など．
解法
$ \left(\frac{\sin \pi(\sqrt{1-x...
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...