No.2162 Copy and Paste 2
レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 :
miscalc
/ テスター :
akakimidori
👑 
ygussany
タグ : / 解いたユーザー数 28
作問者 :
miscalc
/ テスター :
akakimidori
👑 ygussany
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。