結果

問題 No.506 限られたジャパリまん
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:47:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,927 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 76,916 KB
最終ジャッジ日時 2025-06-12 14:50:43
合計ジャッジ時間 2,706 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

MOD = 10**9 + 7

def main():
    H, W, K, P = map(int, sys.stdin.readline().split())
    friends = []
    grid = dict()  # Maps (x,y) to friend index

    for idx in range(K):
        x, y, name = sys.stdin.readline().split()
        x = int(x)
        y = int(y)
        friends.append((x, y, name, idx))
        grid[(x, y)] = idx

    max_paths = -1
    best_subset = None

    # Iterate through all possible subsets of size P
    for subset in combinations(range(K), P):
        dp = [[0] * (W + 1) for _ in range(H + 1)]
        dp[0][0] = 1  # Starting point

        for i in range(H + 1):
            for j in range(W + 1):
                if i == 0 and j == 0:
                    continue  # Already initialized

                total = 0
                if i > 0:
                    total += dp[i-1][j]
                if j > 0:
                    total += dp[i][j-1]

                # Check if current cell is a friend's position
                if (i, j) in grid:
                    friend_idx = grid[(i, j)]
                    if friend_idx not in subset:
                        # Blocked, so no path through here
                        dp[i][j] = 0
                    else:
                        dp[i][j] = total % MOD
                else:
                    dp[i][j] = total % MOD

        current_paths = dp[H][W]
        if current_paths > max_paths:
            max_paths = current_paths
            best_subset = subset

    if max_paths == 0 or max_paths == -1:
        print(0)
    else:
        print(max_paths % MOD)
        if best_subset is not None:
            # Output the names in the order of their appearance in the input
            sorted_subset = sorted(best_subset)
            for idx in sorted_subset:
                print(friends[idx][2])
            print()  # Ensure a newline at the end

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