結果

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

ソースコード

diff #
raw source code 

MOD = 998244353

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

dp = [[0] * (W + 1) for _ in range(H + 1)]

if grid[0][0] == '.':
    dp[1][1] = 1
else:
    print(0)
    exit()

from collections import defaultdict
diagonals = defaultdict(list)
prefix = defaultdict(list)

# Preprocess the diagonals and their prefix sums
for i in range(1, H + 1):
    for j in range(1, W + 1):
        s = i + j
        if grid[i-1][j-1] == '#':
            continue
        diagonals[s].append((i, j))

for s in diagonals:
    # Sort the cells in diagonal s by their row i
    cells = sorted(diagonals[s], key=lambda x: x[0])
    pr = []
    current_sum = 0
    for (i, j) in cells:
        # The value is 0 for now; will be updated after computing dp[i][j]
        pr.append((i, current_sum))
    prefix[s] = pr

# Process each cell in order of increasing i + j
for s in sorted(prefix.keys()):
    cells_in_s = sorted(diagonals[s], key=lambda x: x[0])
    for idx, (i, j) in enumerate(cells_in_s):
        if i == 1 and j == 1:
            continue  # already initialized
        if grid[i-1][j-1] == '#':
            dp[i][j] = 0
            continue
        
        current_s = i + j
        min_s = max(2, current_s - K)
        max_s = current_s - 1
        total = 0
        
        for t in range(min_s, max_s + 1):
            if t not in prefix or len(prefix[t]) == 0:
                continue
            
            # Determine the valid x range for diagonal t
            max_x = i  # x <= i
            min_x = max(1, t - j)  # y = t - x <= j => x >= t - j
            if min_x > max_x:
                continue
            
            # Find the range in prefix[t]
            low, high = 0, len(prefix[t]) - 1
            left = -1
            while low <= high:
                mid = (low + high) // 2
                if prefix[t][mid][0] >= min_x:
                    left = mid
                    high = mid - 1
                else:
                    low = mid + 1
            if left == -1:
                continue
            
            right = -1
            low, high = left, len(prefix[t]) - 1
            while low <= high:
                mid = (low + high) // 2
                if prefix[t][mid][0] <= max_x:
                    right = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if right == -1:
                continue
            
            # Sum from left to right
            sum_val = (prefix[t][right][1] - (prefix[t][left-1][1] if left > 0 else 0)) % MOD
            total = (total + sum_val) % MOD
        
        dp[i][j] = total % MOD
    
    # Update the prefix sums for this diagonal s after processing all cells
    pr = []
    current_sum = 0
    for idx, (i, j) in enumerate(cells_in_s):
        current_sum = (current_sum + dp[i][j]) % MOD
        if idx == 0:
            pr.append((i, current_sum))
        else:
            pr.append((i, (pr[-1][1] + dp[i][j]) % MOD))
    prefix[s] = pr

print(dp[H][W] % MOD)
0