第7回では, の部分集合系 が与えられたときに, が開集合系の定義を満たす（ が位相空間になる）かどうかの判定について書きます. 計算量は の要素数を , ワードサイズを として, 時間計算量 , 空間計算量 です. これが多項式時間になるという雰囲気が好きで…

第6回では, 一般化された包除原理について扱います. 包除原理は「条件を 個以上満たすものの個数」を数え上げるものです. これを一般化すると, 「条件を 個以上満たす」「条件をちょうど 個満たす」や「条件を 個満たすものは が答えに足される」などもふつ…

はじめに 正の整数 を固定します. として, を考えることはよくあります. ここで はを超えない最大の整数です. を自由に動かすとき, のとりうる値の種類の数は です.（A055086 - OEIS） これらの値をすべて列挙する方法で, かなり楽なものを見つけたので今回…

バグループ 聴いてください、バグループ バグってない平方分割を知らない バグってない平方分割が実装できない バグってない平方分割を知らない バグってない平方分割が実装できないよ 蟻本 pp169-170 を参考にして, 自分なりに平方分割を実装してみた. Libr…

第4回では, 先頭固定テクニックとぼくが言う, 主に定数個入力数え上げで平等性が高い状況のときに使えるDPについて書きます. 問題1 例題4-1 個の区別する玉を個の区別しない箱に入れる方法の数はいくつですか. ただし, 各箱には必ず個以上の玉を入れるものと…

第3回では, イベントソートと呼ばれる, 時刻・位置順にイベント（変化する点）をソートして, イベントを時刻・位置順に走査することで, 目的のクエリについて答えていくテクニックについて書きます. 問題1 例題3 ABC248 D - Range Count Query (Diff: 793) …

第2回は, 約数系包除を使うある問題について, 典型的な方法と, 包除原理を用いたもう1通りの解法を解説します. 次の問題を2通りで解いてみます. 例題2（想定Diff 1500） 自然数が与えられます. 集合の要素の数が以上である部分集合について, の最大公約数が…

連載 しょぼんコーダー では, 自分が考えているランダムな競プロテクニックについて解説します. 内容は自分のオリジナルだったりオリジナルじゃなかったりして, ためになるものとためにならないものがあります. 第1回は, 完結・非完結を状態としてとらえるこ…