問題一覧 > 通常問題

No.2162 Copy and Paste 2

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 : miscalc / テスター : akakimidori 👑 ygussany
7 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≤|S|≤2×105

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。