C - Permutation Addition メモ 不変量について考えたい。 こういう時（何かを足していってそれぞれの値を合わせる時とか）は 全体の合計に注目するといいことが多い気がする。 どういう操作をしても不変なものを考えると どう足しても一回で増える和は同じ…

C - Tree and LCS メモ まず、単純な場合を考える パスの上では与えられた順列を反転することで類似度を1にできることが分かる 同様に木の場合で考えると、ある頂点を根としたときに その根から分けられる部分木たちSについて そのS達の各頂点を根を中心とし…

C - Keep Graph Connected メモ 連結グラフについて、何か性質を満たすものを考えろという問題の時に 全域木を取って、それについて考えるのは頻出 感覚的には、連結グラフにおいて、辺が多くあることが何かしら問題において選択肢を増やすことにつながって…

D - Halftree メモ 木を生成できるような操作列を求めろ。 ここで操作とはu-vに辺を貼ったときに(u+K)%N, (v+K)%Nに辺が貼られるようなものである Nが奇数の時だけ考える k==1の時にパスを作りたくなる また、g=gcd(N, K)でg==1なら、0-KとKずつ増やすことで…

atcoder.jp 問題 H行W列のマス目について 各マスに0~K-1の整数を書き込もうとしている。 ここで以下の条件を満たす必要がある。 1<=i<=Hで、i行目のマスの整数の合計をKで割った余りはA[i]であり 1<=i<=Wで、i列目のマスの整数の合計をKで割った余りはB[i]で…