結果

問題 No.874 正規表現間距離
ユーザー lam6er
提出日時 2025-03-31 17:59:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,142 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 759,908 KB
最終ジャッジ日時 2025-03-31 18:00:25
合計ジャッジ時間 13,559 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other AC * 5 WA * 27 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def parse_regex(s):
    elements = []
    i = 0
    while i < len(s):
        if i + 1 < len(s) and s[i+1] in {'?', '*'}:
            elements.append((s[i], s[i+1]))
            i += 2
        else:
            elements.append((s[i], None))
            i += 1
    return elements

A = input().strip()
B = input().strip()

elements_a = parse_regex(A)
elements_b = parse_regex(B)

len_a = len(elements_a)
len_b = len(elements_b)

# Initialize DP: dp[i][a_r][j][b_r] (a_r and b_r are boolean)
INF = float('inf')
dp = [[[[INF] * 2 for _ in range(len_b + 1)] for __ in range(2)] for ___ in range(len_a + 1)]
heap = []

# Initial state: i=0 (first element), a_r=True, j=0, b_r=True with cost 0
heapq.heappush(heap, (0, 0, 1, 0, 1))
dp[0][1][0][1] = 0

found = False
while heap:
    cost, i, a_r_int, j, b_r_int = heapq.heappop(heap)
    a_r = a_r_int == 1
    b_r = b_r_int == 1

    if i == len_a and j == len_b and not a_r and not b_r:
        print(cost)
        found = True
        break

    if cost > dp[i][a_r_int][j][b_r_int]:
        continue

    for da in [0, 1]:
        for db in [0, 1]:
            ni_a = i
            nj_b = j
            new_a_r = a_r
            new_b_r = b_r
            allowed_a = False
            allowed_b = False
            char_a = None
            char_b = None

            if da == 0:
                if i < len_a and a_r and elements_a[i][1] in {'?', '*'}:
                    allowed_a = True
                    ni_a = i + 1
                    new_a_r = False
                elif i >= len_a:
                    allowed_a = True
                    ni_a = i
                    new_a_r = False
                else:
                    allowed_a = False
            elif da == 1:
                if i < len_a and a_r:
                    allowed_a = True
                    char_a = elements_a[i][0]
                    mod_a = elements_a[i][1]
                    if mod_a in {None, '?'}:
                        ni_a = i + 1
                        new_a_r = False
                    else:
                        ni_a = i
                        new_a_r = True

            if db == 0:
                if j < len_b and b_r and elements_b[j][1] in {'?', '*'}:
                    allowed_b = True
                    nj_b = j + 1
                    new_b_r = False
                elif j >= len_b:
                    allowed_b = True
                    nj_b = j
                    new_b_r = False
                else:
                    allowed_b = False
            elif db == 1:
                if j < len_b and b_r:
                    allowed_b = True
                    char_b = elements_b[j][0]
                    mod_b = elements_b[j][1]
                    if mod_b in {None, '?'}:
                        nj_b = j + 1
                        new_b_r = False
                    else:
                        nj_b = j
                        new_b_r = True

            if (da == 0 and not allowed_a) or (da == 1 and not allowed_a) or (db == 0 and not allowed_b) or (db == 1 and not allowed_b):
                continue

            if i < len_a and da == 1 and not allowed_a:
                continue
            if j < len_b and db == 1 and not allowed_b:
                continue

            delta = 0
            if da == 1 and db == 1:
                if char_a != char_b:
                    delta = 1
            elif da + db == 1:
                delta = 1

            new_cost = cost + delta

            if ni_a > len_a or nj_b > len_b:
                continue

            new_a_r_final = new_a_r
            new_b_r_final = new_b_r

            if ni_a == len_a:
                new_a_r_final = False
            if nj_b == len_b:
                new_b_r_final = False

            new_a_r_int = 1 if new_a_r_final else 0
            new_b_r_int = 1 if new_b_r_final else 0

            if new_cost < dp[ni_a][new_a_r_int][nj_b][new_b_r_int]:
                dp[ni_a][new_a_r_int][nj_b][new_b_r_int] = new_cost
                heapq.heappush(heap, (new_cost, ni_a, new_a_r_int, nj_b, new_b_r_int))

if not found:
    print(dp[len_a][0][len_b][0])
0