G - Approximate Equalization メモ 差分だけが重要なので、各Aiについて Ai -= min(A)としていい すると任意の値が0以上の整数になる。 また、この操作において合計は不変であるため 最終的なすべての合計はsa := sigma(A)になる 最終的な数列としてあらわ…

G - Minimum Permutation メモ Li(v) := vが現れるインデックスの内最も左 Ri(v) := vが現れるインデックスの内最も右 とする 辞書順最小なので、次の数にできる物の内最小のものを貪欲に決めていきたい。 値vを先頭にできるかの判定を考える。 l = Li(v)と…

D - 1D Coulomb メモ 以後以下のように言葉を定義する S[i] := iの電荷(+か-) R(s) := sと逆の電荷, R(+) == -, R(-) == + cnt(i, s) := [0, i)にある符号sの数(つまりiより左にあるsの個数) まず各iがどちらに動くかを考える iが+の場合、i以外の合計は-1に…

C - Reversible Card Game メモ まずai = ai - min(ai, bi), bi = bi - min(ai, bi)と置き換えて、sigma(min(ai, bi))を最初から得点している問題と考える。 すると、すべてのカードは0と整数が書かれたものになる お互いに貪欲にやる事を考えてみると、表が…

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

G - Ban Permutation メモ 制約的に箱根駅伝dpを考える from(1~N)からto(1~N)の全単射について、fromからtoへ辺を貼っていく問題だと考えると 箱根dpの性質から、まだ行き先が決まってないfromと元が決まっていないtoの数が一致する。この決まってない数をn…

C - Even Sum Triplet 考えたこと 各操作についてその操作を打ち消すような逆の操作ができるため A, Bをそれぞれ操作して同じ列を作れるか判定する問題だと思っていい まず、ABをソートしても一致させられない場合はNo 1が2個か、0が3つの時に並び変えられる…

F - Figures メモ プリュファーコード問題 //下の式は(N-2 )!を掛けるのを忘れている //上の式は(N-2 )!を掛けるのを忘れている プリューファーコードより、各次数(ei)が決まっているときの木の場合の数は (N-2!) / *1というような形になる 上の式は、それに…

F - Anti-DDoS メモ 以下ではDDoS文字を数える まず判定問題を考えて問題を簡潔にしたい。 これは排反に数え上げる上でも役立つ。 ある文字列にDDoS文字が含まれていても、その文字列を複数回数えないようにしたい。 こういうものはよく、最初に現れる何かの…

A - +3 +5 +7 メモ 問題を言い換えると X, Y, Zが与えられて これらに0, 1, 2の順列を足してすべての合計を同じにする操作回数の最小化を求める問題になる 簡単のためにX<=Y<=Zとすると Z-X, Z-Y, 0 足していって差が上になるようなものを作れるか考える 以…

C - YY Square メモ グリッド上を通った経路について、スコアがあるものの^2で定まる時 そのスコアの合計を求めろという問題 スコアの計算がそのままでは複雑で、dpで漸化的に扱いにくい。 合計の合計という形にできれば、寄与について考えられる 解法1 n^2 …

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

Ex - Constrained Tree Degree メモ プリューファー列について調べた するとSi-1をN回組み合わせてN-2を作る問題になり、 出現回数について重複を除くようにすると 指数型母関数で解ける

G - Sort from 1 to 4 メモ a(1~4)に動かしたいb(1~4)について有効辺を貼って得られるグラフをGとすると この問題はＧに含まれる辺を最大個数の閉路に分ける問題になる。 このような考え方は典型で 各iについてこれをjに持っていきたいという問題設計の時に…

F - Shift Table メモ Nの約数M(N < M)について 青木君のシフトを周期Mで決めた時に、すべての日程でどちらかが居ないといけない。 そのような青木君のシフトを数え上げろという問題 複数の操作列(M, 長さMのシフト)について、同じシフトが重複してしまう事…

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であるよう…

D - Sum of SCC メモ トーナメントグラフを強連結成分分解して得られる縮約グラフはパスである。 それが本質だった。 また、強連結成分の数え上げに苦戦した。 こういう良く分からないものの数え上げは、何か別のものの数え上げに言い換えられればいいが、今…

G - Increasing K Times メモ 問題の形からT - Permutationを連想し dp[i][k] := i個置いたときに、前回置いた数よりも大きい数が何個残っているか として遷移しようとしたがうまくいかなかった。 O(N^3)になってしまった permutationの場合は、各iについて…