結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー Takaya Yoshida
提出日時 2026-05-24 13:49:44
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
RE  
実行時間 -
コード長 2,058 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 920 ms
コンパイル使用メモリ 20,832 KB
実行使用メモリ 20,588 KB
スコア 0
最終ジャッジ日時 2026-05-24 13:50:05
合計ジャッジ時間 17,934 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from ortools.sat.python import cp_model
import sys

def main():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    V = N * N
    weights = [A[i][j] for i in range(N) for j in range(N)]

    # 隣接する有向ペア
    adjacent_pairs = []
    for i in range(N):
        for j in range(N):
            u = i * N + j
            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < N and 0 <= nj < N:
                    v = ni * N + nj
                    adjacent_pairs.append((u, v))

    model = cp_model.CpModel()

    # p[k] = k番目に訪れるマス
    p = [model.NewIntVar(0, V - 1, f"p[{k}]") for k in range(T)]

    # 同じマスを二度訪れない
    model.AddAllDifferent(p)

    # 連続するマスは隣接
    for k in range(T - 1):
        model.AddAllowedAssignments([p[k], p[k + 1]], adjacent_pairs)

    # 各ステップの得点
    max_a = max(weights)
    score_vars = []
    for k in range(T):
        s = model.NewIntVar(0, max_a, f"score[{k}]")
        model.AddElement(p[k], weights, s)
        score_vars.append(s)

    model.Maximize(sum(score_vars))

    # 初期解ヒント: ジグザグパス
    hint_path = []
    for i in range(N):
        if i % 2 == 0:
            for j in range(N):
                hint_path.append(i * N + j)
        else:
            for j in range(N - 1, -1, -1):
                hint_path.append(i * N + j)

    for k in range(T):
        model.AddHint(p[k], hint_path[k])

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 1.8
    solver.parameters.num_search_workers = 8

    status = solver.Solve(model)

    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        # フォールバック: ジグザグ
        path = hint_path[:T]
    else:
        path = [solver.Value(p[k]) for k in range(T)]

    print(len(path))
    for u in path:
        print(u // N, u % N)

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