AtCoder [AtCoder] Interesting Equation（Xmas Contest 2018 [I]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
お誕生日問題
$N$ 元集合 $\{1, 2, \ldots, N\}$ に値を持つ確率変数 $H$ を考える。この確率変数に従うサンプル $h_1, \ldot...
maspy
AtCoder AtCoder [AtCoder] Median of Medians（ABC 107[D])
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説の計算量 $O(N\log N\log A)$ よりも良い、$O(N\log N)$ 時間の解法について説明します。
解法（概要）
基本方針は公式解説と同...
アルゴリズム・数学 素数に関する上からの評価（初等的な証明）
概要
この記事では常に $p$ は素数を表すこととし、$i, k, n$ は整数、$x$ は実数を表すものとします。特に単に $\sum_{p\leq x}$ や $\prod_{p\leq x}$ などと書いて、素数にわたる和や積...
AtCoder [ハーフマラソン] Multiple Pieces（RCO 日本橋ハーフマラソン予選 [A]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■ （950768 点）
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。
本番時間内の順位表基...
AtCoder [ハーフマラソン] まわしてそろえる（第3回RCO本戦 [B]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■ （54153 点）
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。
本番時間内の順位表基準で、トッ...
問題解説 [JOI] simroad – シムロード（2010 年春合宿）
概要
問題文 → ■, ■公式解説 → なさそう？
JOI の output only の問題です。
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。また、...
AtCoder [AtCoder] Happy 2015（CODE FESTIVAL 2015 OKINAWA [H]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■
解説がなさそうだったので書きますシリーズ。
解法
適当に座圧しておき、座標はすべて $O(N)$ であるとします。
数え上げでは、重複・漏れなく数え...
AtCoder [TTPC] 何かグラフの問題（TTPC 2015 [N]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■
解説がなさそうだったので書きますシリーズ。
参考資料
アリ本 p.104 ～ p.105JOI 春合宿 2018 講義資料「双対性」：
解法
...
AtCoder [UTPC] L 番目の数字（UTPC 2011 [L]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■
解説がなさそうだったので書きますシリーズ。
解法
適当な根を固定して、根付き木として扱います。事前に各クエリに対する LCA を計算しておきます。
...
AtCoder [UTPC] 全域木（UTPC 2011 [F]）
概要
問題文 → ■公式解説 → なさそう？
ジャッジが壊れている問題です。2021 年 4 月現在、AC が不可能だと思います。
解説がなさそうだったので書きますシリーズ。
解法
上からの評価
$K > N/2...