結果

問題 No.611 Day of the Mountain
ユーザー gew1fw
提出日時 2025-06-12 15:20:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,198 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 93,692 KB
最終ジャッジ日時 2025-06-12 15:20:24
合計ジャッジ時間 6,749 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 201712111

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = []
    original = []  # To keep the original grid for checking '?'
    for _ in range(H):
        line = sys.stdin.readline().strip()
        original.append(line)
        row = []
        for c in line:
            if c == '?':
                row.append(1)
            else:
                row.append(int(c))
        grid.append(row)
    
    # Compute minimal path sum T
    # Using BFS since all weights are positive
    INF = float('inf')
    dist = [[INF for _ in range(W)] for __ in range(H)]
    dist[0][0] = grid[0][0]
    q = deque()
    q.append((0,0))
    dirs = [(0,1), (1,0)]
    
    while q:
        i,j = q.popleft()
        current = dist[i][j]
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if dist[ni][nj] > current + grid[ni][nj]:
                    dist[ni][nj] = current + grid[ni][nj]
                    q.append((ni, nj))
    
    T = dist[H-1][W-1]
    
    # Now find all minimal paths
    # Collect the minimal paths as sets of (i,j) positions
    # For each cell, compute the number of ways to reach it with minimal distance
    ways = [[0 for _ in range(W)] for __ in range(H)]
    ways[0][0] = 1
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            total = 0
            if i > 0 and dist[i][j] == dist[i-1][j] + grid[i][j]:
                total += ways[i-1][j]
            if j > 0 and dist[i][j] == dist[i][j-1] + grid[i][j]:
                total += ways[i][j-1]
            ways[i][j] = total
    
    # Now, collect all minimal paths using backtracking
    paths = []
    path = []
    
    def backtrack(i, j):
        if i == 0 and j == 0:
            paths.append(path[::-1])
            return
        if i > 0 and dist[i][j] == dist[i-1][j] + grid[i][j]:
            path.append((i-1, j))
            backtrack(i-1, j)
            path.pop()
        if j > 0 and dist[i][j] == dist[i][j-1] + grid[i][j]:
            path.append((i, j-1))
            backtrack(i, j-1)
            path.pop()
    
    backtrack(H-1, W-1)
    
    # Now, for each path, collect the set of '?' cells
    q_cells = set()
    for i in range(H):
        for j in range(W):
            if original[i][j] == '?':
                q_cells.add((i,j))
    total_q = len(q_cells)
    
    # Extract for each path the set of '?' cells
    path_q_sets = []
    for path in paths:
        s = set()
        for (i,j) in path:
            if original[i][j] == '?':
                s.add( (i,j) )
        path_q_sets.append(s)
    
    # Now, we need to compute the inclusion-exclusion
    # For all non-empty subsets of paths, compute the union of their q cells
    # And accumulate the contributions
    # Since the number of paths can be large, we need to manage this efficiently
    
    # To optimize, we can precompute the list of unique q sets
    unique_q_sets = []
    seen = set()
    for s in path_q_sets:
        frozen = frozenset(s)
        if frozen not in seen:
            seen.add(frozen)
            unique_q_sets.append(s)
    
    K = len(unique_q_sets)
    if K == 0:
        print(T)
        print(0)
        return
    
    # Now, iterate over all non-empty subsets of unique_q_sets
    # For each subset, compute the union of their q sets
    # Then compute 9^(total_q - size_of_union)
    # Multiply by (-1)^(|subset| + 1) and add to X
    
    X = 0
    for mask in range(1, 1 << K):
        bits = bin(mask).count('1')
        # Get the subset
        subset = []
        for i in range(K):
            if mask & (1 << i):
                subset.append(unique_q_sets[i])
        # Compute the union
        union = set()
        for s in subset:
            union.update(s)
        k = len(union)
        m = total_q - k
        term = pow(9, m, MOD)
        if bits % 2 == 1:
            X = (X + term) % MOD
        else:
            X = (X - term) % MOD
        X = (X + MOD) % MOD  # Ensure non-negative
    
    print(T)
    print(X % MOD)

if __name__ == '__main__':
    main()
0