概要

与えられた正しい括弧列に対して、その入れ子構造が最も深くなる部分の深さを求める問題です。

考察

括弧の深さを計算するためには、「現在、閉じられていない括弧がいくつあるか」を管理する必要があります。

具体的には、文字列を左から順番に見ていったとき、以下のような挙動になります： - (（開き括弧）が現れる：新しい入れ子の層が始まるため、現在の深さが \(1\) 増える。 - )（閉じ括弧）が現れる：現在の入れ子の層が終わるため、現在の深さが \(1\) 減る。

例えば、(()()) という文字列の場合、深さは以下のように変化します： 1. ( が来る：深さ \(1\) 2. ( が来る：深さ \(2\) 3. ) が来る：深さ \(1\) 4. ( が来る：深さ \(2\) 5. ) が来る：深さ \(1\) 6. ) が来る：深さ \(0\)

この変化の中で、深さが最大になった瞬間の値（この例では \(2\)）が、求める「最大の深さ」となります。

アルゴリズム

1. 最大の深さを記録する変数 max_depth と、現在の深さを表す変数 current_depth を \(0\) で初期化します。
2. 文字列 \(S\) の各文字を先頭から \(1\) 文字ずつ確認します。
   • 文字が ( の場合：current_depth を \(1\) 増やします。
   • その後、current_depth が max_depth より大きければ、max_depth を更新します。
   • 文字が ) の場合：current_depth を \(1\) 減らします。
3. 文字列の最後まで確認し終えたら、max_depth を出力します。

計算量

• 時間計算量: \(O(|S|)\)
  • 文字列の長さ \(|S|\) に対して \(1\) 回のループで走査するため、線形時間で処理が完了します。
• 空間計算量: \(O(|S|)\)
  • 入力文字列を保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: 制約として文字列の長さが \(|S| \leq 10^6\) と大きいため、Pythonの場合は input() よりも sys.stdin.readline() を使用することで実行時間を短縮できます。

• 逐次更新: max_depth の更新は ( が現れた直後に行うだけで十分です。なぜなら、深さが増えるのは ( のタイミングのみだからです。

  ソースコード

import sys

def solve():
    # 入力を標準入力から読み込む
    s = sys.stdin.readline().strip()
    
    max_depth = 0
    current_depth = 0
    
    # 文字列を1文字ずつ走査
    for char in s:
        if char == '(':
            # 開き括弧が来たら深さを増やす
            current_depth += 1
            # 最大深さを更新
            if current_depth > max_depth:
                max_depth = current_depth
        else:
            # 閉じ括弧が来たら深さを減らす
            current_depth -= 1
            
    # 結果を出力
    print(max_depth)

if __name__ == '__main__':
    solve()

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