問題一覧 > 通常問題

No.2162 Copy and Paste 2

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : miscalcmiscalc / テスター : akakimidoriakakimidori 👑 ygussanyygussany
6 ProblemId : 6838 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-17 19:55:53

問題文

この問題の実行時間制限は 7 秒です。

miscalc くんは文字列 $T, U$ を持っています。これらははじめ空です。

miscalc くんの手元には、A キー、B キー、C キー、V キーの $4$ つのキーがあります。それぞれのキーを押すと、$T$ や $U$ が次のように変化します。

  • A キーを $1$ 回押すと、$T$ の末尾に a が追加される。
  • B キーを $1$ 回押すと、$T$ の末尾に b が追加される。
  • C キーを $1$ 回押すと、$U$ が $T$ で置き換わる。
  • V キーを $1$ 回押すと、$T$ の末尾に $U$ が追加される。

a および b からなる文字列 $S$ が与えられます。$T$ を $S$ に一致させるためには、最小で何回キーを押す必要がありますか？

入力

$S$

  • $S$ は a および b からなる文字列である
  • $1 \leq |S| \leq 2 \times 10^5$

出力

$T$ を $S$ に一致させるためにキーを押す回数の最小値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
babbababa
出力
7

以下の手順でキーを押すと、押す回数が最小になります。

  • B キーを押す。$T = $ b、$U = $ になる。
  • A キーを押す。$T = $ ba、$U = $ になる。
  • C キーを押す。$T = $ ba、$U = $ ba になる。
  • B キーを押す。$T = $ bab、$U = $ ba になる。
  • V キーを押す。$T = $ babba、$U = $ ba になる。
  • V キーを押す。$T = $ babbaba、$U = $ ba になる。
  • V キーを押す。$T = $ babbababa、$U = $ ba になる。

サンプル2
入力
aabbaabaabbaab
出力
8

以下の手順でキーを押すと、押す回数が最小になります。

  • A キーを押す。$T = $ a、$U = $ になる。
  • A キーを押す。$T = $ aa、$U = $ になる。
  • B キーを押す。$T = $ aab、$U = $ になる。
  • C キーを押す。$T = $ aab、$U = $ aab になる。
  • B キーを押す。$T = $ aabb、$U = $ aab になる。
  • V キーを押す。$T = $ aabbaab、$U = $ aab になる。
  • C キーを押す。$T = $ aabbaab、$U = $ aabbaab になる。
  • V キーを押す。$T = $ aabbaabaabbaab、$U = $ aabbaab になる。

サンプル3
入力
aaaaaaaaaaaaaaaa
出力
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。