結果

問題 No.2003 Frog on Grid
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:55:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,111 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 79,192 KB
最終ジャッジ日時 2025-03-20 20:56:22
合計ジャッジ時間 8,741 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

MOD = 998244353

H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    line = input().strip()
    grid.append(list(line))

# Precompute diagonals and their prefix sums
diagonals = {}  # key is d, value is list of tuples (x, y)
valid_cells = []
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            d = (i+1) + (j+1)  # since i and j are 0-based, converting to 1-based
            if d not in diagonals:
                diagonals[d] = []
            diagonals[d].append((i+1, j+1))  # stored as 1-based

# Sort each diagonal's cells by x, and precompute prefix sums
prefix_sums = {}
sorted_diags = {}
for d in diagonals:
    cells = sorted(diagonals[d], key=lambda x: x[0])  # sort by x (1-based)
    sorted_diags[d] = cells
    ps = [0]
    current = 0
    for (x, y) in cells:
        current += 0  # will be filled later
        ps.append(current)
    prefix_sums[d] = ps  # placeholder, will update as we process

# Now, process each cell in increasing order of diagonal
max_d = H + W
dp = [[0] * (W + 2) for _ in range(H + 2)]  # 1-based
dp[1][1] = 1 if grid[0][0] == '.' else 0  # check if starting cell is valid

# Also, precompute the cells for each diagonal again, this time with their positions
processed_diagonals = sorted(sorted_diags.keys())

for d in sorted(processed_diagonals):
    cells = sorted_diags[d]
    for idx, (i, j) in enumerate(cells):
        if i == 1 and j == 1:
            # Already initialized
            current_dp = dp[i][j]
        else:
            # Compute the sum from diagonals [d-K, d-1]
            min_prev_d = d - K
            max_prev_d = d - 1
            total = 0
            for prev_d in range(max(2, min_prev_d), max_prev_d + 1):
                if prev_d not in sorted_diags:
                    continue
                prev_cells = sorted_diags[prev_d]
                if not prev_cells:
                    continue
                # For diagonal prev_d, find cells (x, y) where x <= i and y <= j
                # x + y = prev_d
                # x <= i, y <= j --> x >= prev_d - j, x <= i
                a = max(prev_d - j, 1)
                b = min(i, prev_d - 1)
                if a > b:
                    continue
                # Find the cells in prev_d with x in [a, b]
                left = bisect.bisect_left(prev_cells, (a, 0))  # find first x >= a
                right = bisect.bisect_right(prev_cells, (b, W+2)) -1  # find last x <= b
                if left > right:
                    continue
                ps = prefix_sums[prev_d]
                sum_prev = (ps[right + 1] - ps[left]) % MOD
                total = (total + sum_prev) % MOD
            current_dp = total % MOD
        
        # Update dp[i][j]
        if grid[i-1][j-1] == '#':
            dp[i][j] = 0
        else:
            dp[i][j] = current_dp
    
    # Update prefix sums for this diagonal d
    ps = [0]
    current = 0
    for (i, j) in cells:
        current = (current + dp[i][j]) % MOD
        ps.append(current)
    prefix_sums[d] = ps

# The answer is dp[H][W]
print(dp[H][W] % MOD)
0