ABC 401-500/ABC418B - You're a teapot - 競技プログラミング用 知識集積所【8/10更新】

---

問題

ABC418B
冒頭の文は、有名な英語のなぞなぞ。
「最初がT、最後もT、中もTでいっぱいなものな～んだ？」
答えはteapot（スペルの最初と最後がTで、中も紅茶=ティーでいっぱい）

必要知識

A問題レベルのものは省略

• 全探索※
• 二重ループ※

考え方

素直に二重ループ※による全探索※。
文字列の長さは3以上だけ確認すればいいので、開始位置iを0からn-1まで、終了位置jをi+2からn-1までで全探索※をかければよい。
さらに、該当文字がTじゃなかった場合はcontinueで飛ばしてしまってよい。

あとはループの中での充填率の計算をするだけで、これはA問題レベル。
ここでもforループが必要なので、全体としては三重ループになる。

解答例

解答例

注意点

最初と最後のTを取るのが最善とは限らない

例えばTAATTTAAATとかいう場合、最初と最後のTを取るよりも、TTT部分だけを取った方が充填率は高い。

別解