結果

問題 No.2003 Frog on Grid
ユーザー lam6er
提出日時 2025-04-09 20:56:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,449 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 77,736 KB
最終ジャッジ日時 2025-04-09 20:56:24
合計ジャッジ時間 6,840 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

MOD = 998244353

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append(line)
    
    # DP table (1-based)
    dp = [[0]*(W+2) for _ in range(H+2)]
    # 2D prefix sum (1-based)
    prefix = [[0]*(W+2) for _ in range(H+2)]
    # Structure to hold diagonals and their prefix sums
    diagonals = dict()  # key: d = i + j, value: list of x's in sorted order
    diag_prefix = dict()  # key: d, value: list of prefix sums of the diagonal
    
    # Initialize starting cell (1,1)
    if grid[0][0] != '#':
        dp[1][1] = 1
        prefix[1][1] = 1
        d = 1 + 1
        if d not in diagonals:
            diagonals[d] = []
            diag_prefix[d] = []
        diagonals[d].append(1)
        diag_prefix[d].append(1)
    
    for i in range(1, H+1):
        for j in range(1, W+1):
            if i == 1 and j == 1:
                continue  # already initialized
            # Check if the current cell is a hole
            if grid[i-1][j-1] == '#':
                dp[i][j] = 0
            else:
                T = (i + j) - K
                sum_less_T = 0
                if T >= 2:
                    for d in range(2, T):
                        if d not in diag_prefix:
                            continue
                        # Determine x range: x >= d - j, x <= min(i, d-1)
                        x_min = max(1, d - j)
                        x_max = min(i, d-1)
                        if x_min > x_max:
                            continue
                        # Binary search in the sorted list of x's for the diagonal d
                        xs = diagonals[d]
                        # Find first x >= x_min
                        left = bisect.bisect_left(xs, x_min)
                        # Find last x <= x_max
                        right = bisect.bisect_right(xs, x_max) - 1
                        if left > right:
                            continue
                        # Get prefix sums
                        pf = diag_prefix[d]
                        sum_d = pf[right]
                        if left > 0:
                            sum_d -= pf[left-1]
                        sum_less_T = (sum_less_T + sum_d) % MOD
                # Compute valid sum using inclusion-exclusion with 2D prefix sum
                current_prefix = (prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]) % MOD
                valid_sum = (current_prefix - sum_less_T) % MOD
                dp[i][j] = valid_sum
            # Update 2D prefix sum
            prefix[i][j] = (prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + dp[i][j]) % MOD
            # Update diagonals
            d = i + j
            if d not in diagonals:
                diagonals[d] = []
                diag_prefix[d] = []
            xs = diagonals[d]
            pf = diag_prefix[d]
            # Insert i into the correct position (sorted)
            pos = bisect.bisect_right(xs, i)
            xs.insert(pos, i)
            if pos == 0:
                new_p = dp[i][j]
            else:
                new_p = (pf[pos-1] + dp[i][j]) % MOD
            pf.insert(pos, new_p)
            # Update remaining prefix sums after pos
            for k in range(pos+1, len(pf)):
                pf[k] = (pf[k-1] + dp[i][j]) % MOD
    
    print(dp[H][W] % MOD)

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