概要

正しく対応のとれた括弧列 \(S\) について、左から順に見たときの「同時に開いている括弧の最大数」を求めれば、それが入れ子の最大の深さになります。

考察

括弧列の「深さ」とは、ある位置で何個の ( がまだ閉じられていないか（何段階入れ子になっているか）で決まります。
例えば ((())) を左から見ると、

• 1文字目 (：深さ \(1\)
• 2文字目 (：深さ \(2\)
• 3文字目 (：深さ \(3\)（最大）
• その後 ) で深さが \(2,1,0\) と戻る

となり、最大深さは \(3\) です。

素朴に「各括弧がどの括弧に対応するか」を毎回探したり、部分文字列を作って解析したりすると、最悪で \(O(|S|^2)\) になり \(|S| \le 10^6\) では間に合いません。
しかしこの問題は対応関係そのものは不要で、「いま何段開いているか」だけ分かれば十分なので、1回の走査で解けます。

アルゴリズム

1. 変数 cur を「現在の深さ（開き括弧の未処理数）」として \(0\) で初期化する。
2. 変数 mx を「最大深さ」として \(0\) で初期化する。
3. 文字列を左から順に見て、
   • 文字が ( なら cur += 1（深くなる）し、mx = max(mx, cur) で最大を更新する。
   • 文字が ) なら cur -= 1（一段戻る）とする。
4. 最後に mx を出力する。

入力は正しい括弧列であることが保証されているため、途中で cur が負になることや、最後に \(0\) にならないことは起きません（ただし実装ではその保証を前提にしてOKです）。

計算量

• 時間計算量: \(O(|S|)\)（1回の走査）
• 空間計算量: \(O(1)\)（カウンタ2つだけ）

実装のポイント

• \(|S|\) が最大 \(10^6\) なので、Pythonでは sys.stdin.buffer.read() のように高速入力を使うと安心です。

• 最大深さは ( を読んだ直後の cur が候補になるので、そのタイミングで mx を更新します。

  ソースコード

import sys

def main():
    s = sys.stdin.buffer.read().strip().decode()
    cur = 0
    mx = 0
    for ch in s:
        if ch == '(':
            cur += 1
            if cur > mx:
                mx = cur
        else:
            cur -= 1
    print(mx)

if __name__ == "__main__":
    main()

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