2019-01-01から1年間の記事一覧
D - Chordsまず円を直線上に展開することに気付くと,区間を $N$ 個とる問題になって区間 $dp$ っぽいことができそうな気持ちになります.連結成分を適当に分けてそれぞれ独立に数え上げることができればよさそうなことから自然に $dp(l, r) :=$ 区間 $[l, r…
E - Modulo Pairingまず $mod\ M$ の制約を無視して考えると,数直線状で交差する二つのペアや独立したペアをとっても得することはないのでペアをすべて入れ子状にしたものが最適解の一つになります.元の問題でこれが成り立つのはいずれのペアも $x + y = m…
C - Differ by 1 Bit動く回数は必ず $2^N - 1$ 回なので $a$ と $b$ の立っている $bit$ の個数の偶奇は異なることが必要です.$0...$ から $1...$ などにはきれいに移動できるので自然に分割統治をしたくなります.頂点 $S$ と $T$ が今見ている部分の半分…