概要

各歌詞文字列に含まれる部分文字列 tanabata の出現回数（重なりも含む）を数え、最も回数が多い曲の番号（同率なら最小の番号）を求めます。

考察

• 求めたい「夏らしさスコア」は、文字列中に 部分文字列 tanabata が何回現れるかです。
• ここで重要なのは 出現が重なる場合も数える点です。
  例えば一般に、文字列 "aaaa" に "aa" は位置 0,1,2 から始まるので 3 回出現します。
  本問題でも同様に、見つけた位置の次（+1）から再検索する必要があります。
• 素朴に「全ての位置から長さ 8 を切り出して一致判定」しても、tanabata の長さは 8 で固定なので
  合計文字数が最大でも \(10^6\) なら十分間に合います（\(8 \times 10^6\) 程度）。
• 提示コードでは Python の str.find を使い、次のように数えています：
  • find(pat, start) で start 以降の最初の出現位置を得る
  • 見つかったら回数を増やし、start = pos + 1 として 1 文字だけ進めて再検索（重なり対応）

さらに、最大スコアの曲が複数あるときは番号最小を選ぶので、 - cnt > best_score のときのみ更新（>= にしない）
とすることで、同点なら先に見つかった（＝番号が小さい）曲が保持されます。

アルゴリズム

1. パターン pat = "tanabata" を用意する。
2. 各曲 \(i=1..N\) について以下を行う：
   1. cnt = 0, start = 0 とする。
   2. ループで pos = S_i.find(pat, start) を実行する。
      • pos == -1 なら見つからないので終了。
      • 見つかったら cnt += 1、次は重なりを許すため start = pos + 1 とする。
   3. cnt がこれまでの最大値より大きければ、最大値と答えの番号を更新する。
3. 最終的に保持している番号を出力する。

計算量

• 時間計算量: \(O\!\left(\sum_{i=1}^{N} |S_i|\right)\)（tanabata の長さが定数で、各文字列を実質的に線形に処理できるため）
• 空間計算量: \(O(1)\)（入力文字列以外に大きな追加領域を使わない）

実装のポイント

• 重なりを数えるため、次の探索開始位置を pos + len(pat) ではなく pos + 1 にする。

• 同点の場合は最小の番号にしたいので、更新条件は cnt > best_score にする（>= にしない）。

• 入力が大きいので sys.stdin.buffer.readline を使って高速に読み込む。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N_line = input()
    if not N_line:
        return
    N = int(N_line)
    pat = "tanabata"

    best_idx = 1
    best_score = -1

    for i in range(1, N + 1):
        s = input().decode().strip()
        cnt = 0
        start = 0
        while True:
            pos = s.find(pat, start)
            if pos == -1:
                break
            cnt += 1
            start = pos + 1  # allow overlap

        if cnt > best_score:
            best_score = cnt
            best_idx = i

    sys.stdout.write(str(best_idx))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。