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

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

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

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

詰め切るのが難しかった D - Pure Straight ------------------------------------------------------------ 問題 N項の整数列Aが与えれる、Aiは1...Kのいずれかである。 隣接する二項をswapする操作を何回でも行える時、ある区間が1...Kになるような最小の…

セグ木で差分を更新する方法が勉強になった。 F - Insertion Sort ---------------------------------------------------- 問題 長さNの順列Pが与えられる。 左からi番目の値はPiである。 以下の操作を使ってPiを昇順に並べたい。 ・i(1<=1<=N)を選ぶ。コス…