Library Checker [Library Checker] Point Set Tree Path Composite Sum 問題概要 問題文 → ■, ■自分の提出 → ■(根付き木, 169 ms),■ (全方位,332 ms) Static Top Tree (以下 STT)と呼ばれるデータ構造を用いた解法の実装例について解説します. S... 2024.09.03 Library Checker
Library Checker [Library Checker] Rational Approximation 問題概要 問題文 → ■自分の提出 → ■ (35 ms) 一発書きで fastest (2024/08/27)になったのは意外でした. 解法 以下,有理数と言えば非負であることを仮定し,有理数 $a/b$ のよう... 2024.08.27 Library Checker
問題解説 [ijpc2015] E – Верный 概要 問題文 → ■公式解説 → 見つからず自分の提出 → ■ 問題文について 「'a'から'j'までのどれかの小文字のアルファベットが一つ書かれている」とありますが,正しいです.アルファベットが 10 種類であると仮定した... 2024.08.21 問題解説
問題解説 [nadafes2022] P – Turn it Over 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 大筋は公式解説と同じだと思います.使った計算のテクニックは少し違いました. 2024年に知られた手法を見たことのない感じの使い方をしました. 解法 長さ $M$ の区間を... 2024.08.19 問題解説
問題解説 [JOI] F – とてもたのしいたのしい家庭菜園(JOI 2024 春合宿) 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 (時間計算量 $\Theta(N\log N\log A)$) 二分探索します.次が $\Theta(N\log N)$ 時間で解ければよいです. $(A_1... 2024.08.16 問題解説
問題解説 [JOI] B – 神経衰弱(JOI 2016 春合宿) 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 公式解説とたぶん違ったので書いておきます. 次の状態を保持するようにします. 答が分かっていないカードが $2n$ 枚あり,これらは Flip... 2024.08.12 問題解説
問題解説 [JOI] C – Mansion(JOI Open Contest 2012) 概要 問題文 → ■公式解説 → 存在するか分からず自分の提出 → ■ まず読解がちょっと難しかった.サンプル 1 はこんなのです. 解法 同じグラフがグリッド状に並んでいて最短路問題となっています.まずひとつのグラフ... 2024.08.12 問題解説
問題解説 [JOI] B – Jumps(JOI Open Contest 2012) 概要 問題文 → ■公式解説 → 存在するか分からず 提出したら IE になってしまった.2024年8月12日現在,正しくジャッジされていないと思います. → 2024年8月21日修正されました.解答例 解法 すべての点が同一... 2024.08.12 問題解説
問題解説 [JOI] A – Code(JOI Open Contest 2012) 概要 問題文 → ■公式解説 → 存在するか分からず自分の提出 → ■ 解法 $s, t$ などと書くと経路を表すことにします.$\mathrm{prob}(s)$ などと書けばその経路の実現する確率とします.$\mathrm... 2024.08.12 問題解説
AtCoder [AtCoder] G – Dynamic Scheduling (ABC 363 G) 概要 問題文 → ■公式解説 → ■ 公式解説と同様に,最小費用流をセグメント木を用いて管理するという方針です.公式解説の解説は Hall の定理を経由するなど少しまわりくどいように感じられ,また辺の削除に対応していないため計算量が悪化し... 2024.07.21 AtCoder問題解説