きろく

特筆すべき記録のまとめ

2018-06-08から1日間の記事一覧

AtCoder Regular Contest 097 : D - Equals

問題 D - Equals 1~N の順列 p の中で (x,y) 番目のものを swap 出来るとき、最大でいくつの数をもとの位置に戻せるか、という問題。 解法 順列内の数を頂点、swap 出来る関係を辺として図を書いてみると、連結な部分は連結の範囲の中の任意の場所に移動可能…

ARC097 : C - K-th Substring

問題 C - K-th Substring 文字列 s の部分文字列の重複を除いたうち、K 番目に小さいものを答える問題。 解法 全ての部分文字列を列挙していては O(|s|^3) となり間に合わないので、工夫する。s の各文字から長さ 1~K のものが答えの候補となるので、O(|s|) …