問題 D - Equals 1~N の順列 p の中で (x,y) 番目のものを swap 出来るとき、最大でいくつの数をもとの位置に戻せるか、という問題。 解法 順列内の数を頂点、swap 出来る関係を辺として図を書いてみると、連結な部分は連結の範囲の中の任意の場所に移動可能…
問題 C - K-th Substring 文字列 s の部分文字列の重複を除いたうち、K 番目に小さいものを答える問題。 解法 全ての部分文字列を列挙していては O(|s|^3) となり間に合わないので、工夫する。s の各文字から長さ 1~K のものが答えの候補となるので、O(|s|) …
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。