読者です 読者をやめる 読者になる 読者になる

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C:アメージングな文字列は、きみが作る!

やはり文字列操作は苦手なようです。

問題概要

文字列sが与えられる。K回の以下の操作が可能である。

  • ある文字を削除する
  • ある文字を置換する
  • 文字を1文字任意の位置に挿入する

K回の操作後に辞書順最小となる文字列は何か。

discovery2016-qual.contest.atcoder.jp

解説

取り敢えず置換と挿入は全てaで行います。

まず、s中にaが何文字あるか確認します。K回の操作でsを全てaにすることが出来る場合、a以外の文字を全て削除し、その後余った手数で文字列の文字数を出来る限り削れば答えが得られます。

K回の操作でsをaのみの文字列に出来ない時、文字列の初めをaの羅列にすることで辞書順最小になります。ただし、この時ただ文字を置換するだけでなく、挿入する方がいい場合があります。

その例がs="abc",k=1のパターンです。

まず、元々aの部分は置換する必要がないので、それを考慮した上で何文字目まで置換でaの羅列に出来るかを求めます。

i文字目までaにすることが出来るとすると、最後のi文字目を置換ではなく、文字列の最初にaを挿入することでもaの羅列の数は同じです。同様にaの羅列の数が変わらない範囲(=iから戻って行き、最初のaにぶつかるまで)ならaを同数文字列の初めに持っていけます。

そうしたら後はそれらの中での辞書順最小が分かれば正解が分かります。

接尾辞配列を用いて範囲内でrankが最小のものを探せば上手く行きます。

Submission #637830 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder

感想

接尾辞配列初めて使いました。ローリングハッシュでも通るらしいですが、これも使ったことないですね…