(o_o)

ブログ。

AOJ2352 Divisor

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

続きを読む

AOJ2588 Golf

問題概要

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

続きを読む