結果

問題 No.2003 Frog on Grid
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:58:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,050 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 77,568 KB
最終ジャッジ日時 2025-06-12 15:00:04
合計ジャッジ時間 9,336 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    H = int(data[idx])
    idx += 1
    W = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    grid = []
    for _ in range(H):
        row = data[idx]
        idx += 1
        grid.append(row)
    
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    if grid[0][0] == '.':
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    
    x_list = {}
    prefix_sum = {}
    for d in range(2, H + W + 1):
        x_list[d] = []
        prefix_sum[d] = [0]
    
    x_list[2] = [1]
    prefix_sum[2] = [0, dp[1][1]]
    
    for d in range(3, H + W + 1):
        for i in range(max(1, d - W), min(H, d - 1) + 1):
            j = d - i
            if j < 1 or j > W:
                continue
            if grid[i-1][j-1] == '#':
                dp[i][j] = 0
            else:
                s_total = 0
                for s in range(1, K+1):
                    d_prime = d - s
                    if d_prime < 2:
                        continue
                    x_start = max(1, d_prime - j)
                    x_end = min(i, d_prime - 1)
                    if x_start > x_end:
                        continue
                    lst = x_list.get(d_prime, [])
                    if not lst:
                        continue
                    left = bisect.bisect_left(lst, x_start)
                    if left >= len(lst):
                        continue
                    right = bisect.bisect_right(lst, x_end) - 1
                    if right < 0 or right < left:
                        continue
                    ps = prefix_sum[d_prime]
                    sum_val = ps[right + 1] - ps[left]
                    s_total += sum_val
                s_total %= MOD
                dp[i][j] = s_total
            x_list[d].append(i)
            new_sum = prefix_sum[d][-1] + dp[i][j]
            prefix_sum[d].append(new_sum)
    
    print(dp[H][W] % MOD)

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