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ずつ増やすことで…

D - Mahjong メモ 以下の二つの操作を使って作れる、長さNで総和がMの数列Aは何通りあるか ・長さKの区間に1を足す ・あるAiの値をK足す この問題の難しさは、異なる操作によって同じ数列が作られる事があるという点にある これは、数えあげpdfのgreedyから…

C - Power Up メモ 1 ~ 2*10^5 の整数がN個ある時に xという整数を二つ消して、x+1を一つ作れる この時集合としてあり得るものの数え上げをしろという問題 dp[a][x] := aより前までについての繰り上がり処理を終えた際に、aに対する繰り上がりがxであるよう…