(o_o)

ブログ。

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

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

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

原案に関わったやつだけ

A*の問題，他にないのかね

問題概要
略

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

問題概要
略

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