結果

問題 No.2003 Frog on Grid
ユーザー gew1fw
提出日時 2025-06-12 20:07:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,797 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 101,716 KB
最終ジャッジ日時 2025-06-12 20:14:05
合計ジャッジ時間 6,087 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 2 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    H = int(input[idx]); idx += 1
    W = int(input[idx]); idx += 1
    K = int(input[idx]); idx += 1

    grid = []
    for _ in range(H):
        row = input[idx].strip()
        idx += 1
        grid.append(row)

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

    if grid[0][0] == '.':
        dp[1][1] = 1
        pre[1][1] = 1

    diag_sum = [0] * (H + W + 2)
    diag_sum[2] = dp[1][1]

    for d in range(3, H + W + 2):
        diag_sum[d] = 0

    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if i == 1 and j == 1:
                continue
            if grid[i-1][j-1] == '#':
                dp[i][j] = 0
                pre[i][j] = (pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]) % MOD
                continue

            current_d = i + j
            s = current_d - K

            if s <= 2:
                sum_low = 0
            else:
                sum_low = 0
                for d in range(2, s):
                    a = max(1, d - j)
                    b = min(i, d - 1)
                    if a > b:
                        continue
                    sum_low += diag_sum[d]
                    sum_low %= MOD

            pre_ij = (pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]) % MOD
            pre_ij = (pre_ij + dp[i][j]) % MOD
            sum_total = (pre_ij - sum_low) % MOD
            dp[i][j] = sum_total

            pre[i][j] = (pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + dp[i][j]) % MOD
            pre[i][j] %= MOD

            current_d_sum = diag_sum[current_d] + dp[i][j]
            diag_sum[current_d] = current_d_sum % MOD

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

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