結果

問題 No.2375 watasou and hibit's baseball
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:06:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,743 ms / 2,000 ms
コード長 2,532 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 275,028 KB
最終ジャッジ日時 2025-04-16 16:13:39
合計ジャッジ時間 9,316 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, A, B = map(int, sys.stdin.readline().split())
    balls = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    X = [x for x, y, k in balls]
    Y = [y for x, y, k in balls]
    K = [k for x, y, k in balls]
    
    # Precompute distance and K_diff matrices
    dist = [[0] * N for _ in range(N)]
    k_diff = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            dist[i][j] = abs(X[i] - X[j]) + abs(Y[i] - Y[j])
            k_diff[i][j] = abs(K[i] - K[j])
    
    dp = dict()
    max_len = 1
    queue = deque()
    
    # Initialize with each ball as the first in the sequence
    for i in range(N):
        mask = 1 << i
        state = (-1, i, mask)
        dp[state] = 1
        queue.append((state, 1))
    
    while queue:
        state, current_len = queue.popleft()
        if dp.get(state, 0) > current_len:
            continue  # Skip if a better state has already been processed
        prev_pp, prev_p, mask = state
        
        # Try adding each possible next ball
        for c in range(N):
            if (mask & (1 << c)) != 0:
                continue  # Skip if ball c is already used
            
            new_mask = mask | (1 << c)
            if prev_pp == -1:
                # Adding the second ball to the sequence
                a = prev_p
                b = c
                if dist[a][b] >= A or k_diff[a][b] >= B:
                    new_state = (a, b, new_mask)
                    new_len = current_len + 1
                    if new_len > dp.get(new_state, 0):
                        dp[new_state] = new_len
                        if new_len > max_len:
                            max_len = new_len
                        queue.append((new_state, new_len))
            else:
                # Adding the third or later ball
                a = prev_pp
                b = prev_p
                c_ball = c
                cond3 = (k_diff[b][c_ball] >= B)
                cond4 = (dist[b][c_ball] + dist[a][c_ball] >= A)
                if cond3 or cond4:
                    new_state = (b, c_ball, new_mask)
                    new_len = current_len + 1
                    if new_len > dp.get(new_state, 0):
                        dp[new_state] = new_len
                        if new_len > max_len:
                            max_len = new_len
                        queue.append((new_state, new_len))
    
    print(max_len)

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