結果

問題 No.457 (^^*)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:27:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 50 ms / 2,000 ms
コード長 2,363 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 65,484 KB
最終ジャッジ日時 2025-03-20 20:28:52
合計ジャッジ時間 1,831 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# Precompute next_hat (^) and next_star (*) for each position
next_hat = [-1] * (n + 1)  # next occurrence of ^ from position i
next_star = [-1] * (n + 1)  # next occurrence of * from position i

last_hat = -1
last_star = -1
for i in range(n-1, -1, -1):
    if S[i] == '^':
        last_hat = i
    next_hat[i] = last_hat
    if S[i] == '*':
        last_star = i
    next_star[i] = last_star

# Precompute suffix_close: number of ')' from position i to end
suffix_close = [0] * (n + 2)
for i in range(n-1, -1, -1):
    suffix_close[i] = suffix_close[i+1] + (1 if S[i] == ')' else 0)

left_count = 0
right_count = 0

for a in range(n):
    if S[a] != '(':
        continue
    
    # Check left pattern: ^^*
    # Find earliest triplet starting after a
    # b is the first ^ after a+1
    start_b = a + 1
    if start_b >= n:
        b = -1
    else:
        b = next_hat[start_b]
    
    if b == -1:
        contrib_left = 0
    else:
        # Find c, next ^ after b+1
        start_c = b + 1
        if start_c >= n:
            c = -1
        else:
            c = next_hat[start_c]
        
        if c == -1:
            contrib_left = 0
        else:
            # Find d, next * after c+1
            start_d = c + 1
            if start_d >= n:
                d = -1
            else:
                d = next_star[start_d]
            
            if d == -1 or d >= n:
                contrib_left = 0
            else:
                contrib_left = suffix_close[d + 1]
    
    left_count += contrib_left
    
    # Check right pattern: *^^
    start_b = a + 1
    if start_b >= n:
        b = -1
    else:
        b = next_star[start_b]
    
    if b == -1:
        contrib_right = 0
    else:
        # Find c, next ^ after b+1
        start_c = b + 1
        if start_c >= n:
            c = -1
        else:
            c = next_hat[start_c]
        
        if c == -1:
            contrib_right = 0
        else:
            # Find d, next ^ after c+1
            start_d = c + 1
            if start_d >= n:
                d = -1
            else:
                d = next_hat[start_d]
            
            if d == -1 or d >= n:
                contrib_right = 0
            else:
                contrib_right = suffix_close[d + 1]
    
    right_count += contrib_right

print(left_count, right_count)
0