結果

問題 No.1864 Shortest Paths Counting
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:01:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,577 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 125,124 KB
最終ジャッジ日時 2025-04-09 21:02:03
合計ジャッジ時間 7,201 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 998244353

def main():
    N = int(sys.stdin.readline())
    points = []
    for _ in range(N):
        x, y = map(int, sys.stdin.readline().split())
        points.append((x, y))
    
    x1, y1 = points[0]
    xN, yN = points[-1]
    dx = abs(x1 - xN)
    dy = abs(y1 - yN)
    d = max(dx, dy)
    
    valid = []
    for i in range(N):
        x, y = points[i]
        a = max(abs(x - x1), abs(y - y1))
        b = max(abs(x - xN), abs(y - yN))
        if a + b == d:
            valid.append((a, x, y, i))
    
    valid.sort(key=lambda t: t[0])
    
    groups = defaultdict(list)
    for a, x, y, idx in valid:
        groups[a].append((x, y, idx))
    
    dp = defaultdict(int)
    node_map = {}
    for a, x, y, idx in valid:
        node_map[(x, y)] = idx
        if idx == 0:
            dp[(x, y)] = 1
    
    for current_a, x, y, idx in valid:
        if idx == 0:
            continue
        total = 0
        delta_possible = []
        for a_prev in groups:
            if a_prev < current_a:
                delta = current_a - a_prev
                delta_possible.append((a_prev, delta))
        
        for a_prev, delta in delta_possible:
            x_list = groups[a_prev]
            for xv, yv, _ in x_list:
                if max(abs(xv - x), abs(yv - y)) == delta:
                    total += dp.get((xv, yv), 0)
                    total %= MOD
        
        dp[(x, y)] = total % MOD
    
    xN, yN = points[-1]
    print(dp.get((xN, yN), 0) % MOD)

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