概要

\(N\) 個の文字列（歌詞）の中から、特定の文字列 tanabata が部分文字列として最も多く出現するものを探す問題です。出現回数が同じ場合は、最もインデックス（曲の番号）が小さいものを回答します。

考察

この問題を解くためのポイントは以下の3点です。

1. 部分文字列のカウント（重なりあり）: 問題文には「部分文字列 tanabata の出現回数」とあります。競技プログラミングにおいて、特に指定がない場合でも「重なりを許容するかどうか」は重要な確認事項です。 例えば、tanabatanabata という文字列がある場合、1つ目の tanabata は 0文字目から 7文字目、2つ目は 6文字目から 13文字目に位置し、末尾の ta と先頭の ta が重なっています。このようなケースも漏らさずカウントする必要があります。

2. 最大値とインデックスの保持: 「スコアが最大のもの」かつ「同じスコアなら番号が最小のもの」を求める必要があります。これは、各曲を順番に見ていき、現在の最大スコアを厳密に更新したときだけ番号を書き換えることで、自然に「最小の番号」を保持できます。

3. 効率的な入力処理: 制約として \(\sum |S_i| \leq 10^6\) とあり、文字列の総計が非常に大きくなる可能性があります。Pythonで \(10^5\) 行を超える入力を input() で 1つずつ読み込むと時間がかかる場合があるため、sys.stdin.read().split() などで一括して読み込む工夫が有効です。

アルゴリズム

1. 最大スコアを保持する変数 max_score を \(-1\) で、その番号 best_index を \(1\) で初期化します。
2. 各曲の歌詞 \(S_i\) について、以下の処理を行います：
   • 文字列 \(S_i\) の中から tanabata を検索します。
   • 見つかったらスコアを \(+1\) し、見つかった位置の次の文字から再び検索を続行します（これにより重なりを許容してカウントできます）。
   • その曲の最終的なスコアが max_score よりも大きければ、max_score と best_index を更新します。
3. 最終的な best_index を出力します。

計算量

• 時間計算量: \(O(\sum |S_i|)\)
  • 各文字列を一度走査して tanabata を探します。パターンの長さ（8文字）は定数とみなせるため、全体の文字数に比例する時間で処理が完了します。
• 空間計算量: \(O(\sum |S_i|)\)
  • 全ての歌詞データをメモリ上に読み込むために、文字数の総和に比例したメモリを使用します。

実装のポイント

• 重なりの処理: Pythonの s.count('tanabata') は重なりをカウントしません（例：tanabatanabata は 1回と計算される可能性があります）。そのため、s.find() を使い、検索開始位置を pos + 1 とずらしながらループを回すことで、重なりを含む正確なカウントを行っています。

• タイブレーク: if score > max_score: と比較演算子を「より大きい」にすることで、スコアが同じ場合には best_index が更新されず、結果として最小の番号が残るようになっています。

• 高速な入出力: sys.stdin.read().split() を用いることで、大量の文字列データを効率よくリストに格納しています。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字（改行、スペースなど）で分割してトークン化します。
    # これにより、大量の入力データを高速に処理することが可能です。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 最初のエントリは曲の数 N です。
    try:
        n = int(input_data[0])
    except (ValueError, IndexError):
        return
    
    # 最大スコアと、そのスコアを持つ曲の番号（1-indexed）を保持する変数を初期化します。
    # max_score を -1 に設定することで、最初の曲（スコアが 0 であっても）が最初に選択されるようにします。
    max_score = -1
    best_index = 1
    
    # 各曲の歌詞 Si は input_data[1] から input_data[n] に格納されています。
    for i in range(1, n + 1):
        # インデックスがデータの範囲内にあるか確認します。
        if i >= len(input_data):
            break
        
        s = input_data[i]
        
        # 文字列 s に含まれる "tanabata" の出現回数をカウントします。
        # ここでは「部分文字列」の定義に基づき、重なり（overlapping）を含めてカウントします。
        # 例: "tanabatanabata" は 2 回とカウントされます。
        score = 0
        pos = s.find('tanabata')
        while pos != -1:
            score += 1
            # 次の検索は、現在のマッチ位置の 1 つ後ろから開始することで重なりを許容します。
            pos = s.find('tanabata', pos + 1)
        
        # 現在の曲のスコアがこれまでの最大スコアよりも大きい場合、最大スコアと曲番号を更新します。
        # 厳密に大きい場合のみ更新することで、最大スコアが同じ曲が複数ある場合に
        # 最も小さい番号の曲を保持することができます。
        if score > max_score:
            max_score = score
            best_index = i
            
    # 夏らしさスコアが最大の曲の番号を出力します。
    print(best_index)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。