AtCoder 42 （KyurideKagamizProgrammingContest [G]）
概要
問題文 → ■公式解説 → なさそう？（）自分の提出 → ■
G だけ解説がなさそうなので、書きます。
解法
基本方針
問われているものは、各項が整数で $A_i\leq X_i\le...
AtCoder AtCoder [JAG] トーナメント（jag2014summer-day4 [H]）
概要
問題文 → ■公式解説 → なさそう？（ここ の PDF にアクセスできず。）自分の提出 → ■
解法
$O(n2^n)$ 時間解法
まずは、順位表が連長圧縮されていない場合の解法を考えます。
この場...
AtCoder Interesting Equation（Xmas Contest 2018 [I]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
お誕生日問題
$N$ 元集合 $\{1, 2, \ldots, N\}$ に値を持つ確率変数 $H$ を考える。この確率変数に従うサンプル $h_1, \ldot...
AtCoder [ABC] Median of Medians（ABC 107[D])
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説の計算量 $O(N\log N\log A)$ よりも良い、$O(N\log N)$ 時間の解法について説明します。
解法（概要）
基本方針は公式解説と同...
AtCoder [ハーフマラソン] Multiple Pieces（RCO 日本橋ハーフマラソン予選 [A]）
概要
問題文 → ■公式解説 → なさそう？自分の提出 → ■ （950768 点）
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。
本番時間内の順位表基...
AtCoder [ハーフマラソン] まわしてそろえる（第3回RCO本戦 [B]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■ （54153 点）
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。
本番時間内の順位表基準で、トッ...
AtCoder [JOI] simroad – シムロード（2010 年春合宿）
概要
問題文 → ■, ■公式解説 → なさそう？
JOI の output only の問題です。
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。また、...
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]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
解説がなさそうだったので書きますシリーズ。
ありましたが、別方針だったので残しておきます。
解法
適当な根を固定して、根付き木として扱います。事前に各クエリに対す...