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

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

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

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

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

解けなかったので、こういう流れで解きたかったという妄想を書きます C - K Derangement 分かりやすさのために、以降i=0~N-1で0~N-1の順列を並び替える問題として考えます 解説 問題文で問われているのは辞書順最小なので、先頭からなるべく小さい数を入れて…