yukicoder contest 517 A - Happy End
- サイト
- yukicoder
- コンテスト
- yukicoder contest 517
- 問題
- A - Happy End
英大文字からなる長さ の文字列 があります()。文字列 が「良い」とは、 の末尾 5 文字が HAPPY で、それ以外の場所に HAPPY が部分文字列として現れないことをいいます。
の 1 文字を別の文字に書き換える操作を繰り返して を良い文字列にするとき、操作回数の最小値を求めてください。
末尾 5 文字を HAPPY にする
Section titled “末尾 5 文字を HAPPY にする”末尾 5 文字は必ず HAPPY にしなければならないので、HAPPY と異なる文字の個数だけ書き換えが必要です。
残りの HAPPY を壊す
Section titled “残りの HAPPY を壊す”次に、末尾以外に現れる HAPPY をすべて壊します。ここで大事なのは、HAPPY 同士は重なって現れないことです。HAPPY の中で H は先頭にしかないので、HAPPY の途中から別の HAPPY が始まることはありません。
そのため、末尾以外に現れる HAPPY は、末尾の HAPPY とも互いにも重なりません。重ならない HAPPY を 1 つ壊すには少なくとも 1 文字書き換える必要があり、1 回の書き換えで 2 つ同時に壊すこともできません。よって、末尾以外に現れる HAPPY の個数が、この段階で必要な操作回数の下限になります。
この下限は達成できます。各 HAPPY の 1 文字を、HAPPY に含まれない文字(たとえば Z)に書き換えればよいです。HAPPY に含まれない文字を含む位置からは新しい HAPPY が生まれないので、書き換えによって別の場所に HAPPY ができることはありません。
答えは 2 つの段階の操作回数の和で、計算量は です。
Python
N = int(input())S = list(input())ans = 0for i in range(1, 6): if S[-i] != "HAPPY"[-i]: S[-i] = "HAPPY"[-i] ans += 1for i in range(N - 5): if S[i : i + 5] == list("HAPPY"): S[i + 4] = "Z" ans += 1print(ans)前半のループで末尾 5 文字を HAPPY にそろえ、後半のループで末尾以外の HAPPY を見つけるたびに最後の Y を Z に書き換えています。