結果

問題 No.3467 Bracket Warp
コンテスト
ユーザー tyawanmusi
提出日時 2026-02-25 22:59:20
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,027 ms / 2,000 ms
コード長 3,630 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 273 ms
コンパイル使用メモリ 77,816 KB
実行使用メモリ 101,568 KB
最終ジャッジ日時 2026-02-28 13:11:53
合計ジャッジ時間 24,008 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

s = input().strip()
n = len(s)

# 括弧列を木構造に変換する
# 対応する括弧のペアを同じ頂点とみなし、括弧の深さ=頂点の深さ、括弧の内包関係=親子関係とみなす
# 仮想根を 0 として、頂点番号は 1 から始める
pair = n // 2
parent = [0] * (pair + 1)
deg = [0] * (pair + 1) # deg[i] = 頂点 i の子の数
idx = [0] * (pair + 1) # idx[i] = 頂点 i がその親の子の中で左から何番目か (1-indexed)
pair_id = [0] * (n + 1)

# 括弧列から木構造を構築
cur = 0
next = 1
for i in range(1, n + 1):
    if s[i - 1] == '(':
        node = next
        next += 1
        parent[node] = cur
        deg[cur] += 1
        idx[node] = deg[cur]
        pair_id[i] = node
        cur = node
    else:
        pair_id[i] = cur
        cur = parent[cur]

# 子から親へ移動する際のコストを計算
# 親-子1-子2-...-親のようなサイクルが存在するため、子から親へのコストは idx[i] と deg[p] - idx[i] + 1 の小さい方
to_p_cost = [0] * (pair + 1)
for i in range(1, pair + 1):
    p = parent[i]
    if p == 0:
        # 仮想根まわりはクエリ処理の際に別途考慮する
        to_p_cost[i] = 0
    else:
        to_p_cost[i] = min(idx[i], deg[p] - idx[i] + 1)
        
depth = [0] * (pair + 1) # depth[i] = 頂点 i の深さ
dist = [0] * (pair + 1) # dist[i] = 仮想根から頂点 i までの距離
for i in range(1, pair + 1):
    p = parent[i]
    depth[i] = depth[p] + 1
    dist[i] = dist[p] + to_p_cost[i]
    
# LCA
lca_num = pair.bit_length()
double = [[0] * (pair + 1) for _ in range(lca_num)]
for i in range(1, pair + 1):
    double[0][i] = parent[i]
for i in range(1, lca_num):
    for j in range(pair + 1):
        double[i][j] = double[i - 1][double[i - 1][j]]

def get_lca(u, v):
    if depth[u] < depth[v]:
        u, v = v, u
    diff = depth[u] - depth[v]
    for i in range(lca_num):
        if (diff >> i) & 1:
            u = double[i][u]
    if u == v:
        return u
    for i in range(lca_num - 1, -1, -1):
        if double[i][u] != double[i][v]:
            u = double[i][u]
            v = double[i][v]
    return double[0][u]

# u の祖先であり、a を親に持つ頂点を取得する関数 u - ... - ans - ancestor
def get_child_ancestor(u, a):
    diff = depth[u] - depth[a] - 1
    for i in range(lca_num):
        if (diff >> i) & 1:
            u = double[i][u]
    return u

# クエリ処理
for _ in range(int(input())):
    l, r = map(int, input().split())
    u = pair_id[l]
    v = pair_id[r]

    # u と v が同じ頂点に対応する場合
    if u == v:
        print(0)
        continue
    
    lca = get_lca(u, v)

    if u == lca:
        # v が u の子孫にある場合、そのまま距離の差が答え
        ans = dist[v] - dist[u]
    elif v == lca:
        # 同様
        ans = dist[u] - dist[v]
    else:
        # u と v が別々の枝にある場合、 lca を経由する場合と、 lca を含むサイクル上を横移動する場合を考慮する必要がある
        uu = get_child_ancestor(u, lca)
        vv = get_child_ancestor(v, lca)

        # lca の直下の子まで登るコスト
        ans = dist[u] - dist[uu]
        ans += dist[v] - dist[vv]
        
        # lca を含むサイクル上での横移動コスト
        diff = abs(idx[uu] - idx[vv])
        if lca == 0:
            # lca が仮想根の場合、サイクル上の横移動しか行えない
            ans += diff
        else:
            ans += min(diff, deg[lca] + 1 - diff)

    print(ans)
0