けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

操作:挿入

AtCoder ABC 171 F - Strivore (600 点)

実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という!!! 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…

CODE FESTIVAL 2017 qual C C - Inserting 'x' (400 点)

少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…

AtCoder AGC 032 D - Rotation Sort (1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

AtCoder ABC 006 D - トランプ挿入ソート

順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…

AtCoder AGC 032 A - Limited Insertion (400 点)

好き!!!!!でも A 問題としてはかなり難しいね。 問題へのリンク 問題概要 数列 が空の状態から出発して以下の操作を 回行った結果が数列 と一致するようにできるかどうか判定せよ。 回目の操作においては 以上 以下の整数 を一つ選んで、数列の 番目に …