(o_o)

ブログ。

AOJ2450 Do use segment tree

LCAと遅延伝播SegmentTreeと重軽分解のライブラリを貼った

続きを読む

AOJ2352 Divisor

異なる a, b について,a が b の倍数になるときに a から b に辺を張るような N 頂点のグラフを考える.このグラフは推移的グラフであるので,最大独立集合 = 最小パス被覆 である (Dilworth の定理).DAG の最小パス被覆は二部グラフの最大マッチングで解ける.

続きを読む

AOJ2674 異常検知

[l, r) 区間に a_l ... a_r-1 のソート列を持つ Segment Tree を持つ.
各クエリについて O(logN) 回二分探索をすればいい.O(Q log^2 N) くらい.

続きを読む

AOJ1164 Tighten Up!

問題概要

解法
DPっぽいやりかたで解いた.計算量が危うい気がしたけど何故か通った.幾何やからな

続きを読む

AOJ2588 Golf

問題概要

解法
N字以内で書けるものをvectorでもってDPする.のだが,10までやるとTLEする(MLEもしてそう).ここで,N<=8までやって,後は各ケース毎に半分全列挙っぽく二分探索なりしてやれば通る.

続きを読む