結果

問題 No.2958 Placing Many L-s
コンテスト
ユーザー rin204
提出日時 2024-11-08 22:46:52
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,319 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 65,408 KB
最終ジャッジ日時 2024-11-08 22:47:07
合計ジャッジ時間 6,948 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import pulp


def f(n, m):
    if n * m % 4 != 0:
        print("No")
        return

    model = pulp.LpProblem("L", pulp.LpMaximize)
    vars = []
    Ls = [
        [(0, 0), (1, 0), (1, 1), (1, 2)],
        [(0, 2), (1, 0), (1, 1), (1, 2)],
        [(0, 0), (0, 1), (0, 2), (1, 2)],
        [(0, 0), (0, 1), (0, 2), (1, 0)],
        [(0, 0), (1, 0), (2, 0), (2, 1)],
        [(0, 0), (1, 0), (2, 0), (0, 1)],
        [(0, 1), (1, 1), (2, 1), (2, 0)],
        [(0, 1), (1, 1), (2, 1), (0, 0)],
    ]

    for i in range(n):
        for j in range(m):
            for t, dl in enumerate(Ls):
                if all(0 <= i + di < n and 0 <= j + dj < m for di, dj in dl):
                    vars.append(
                        (
                            pulp.LpVariable(f"var_{i}_{j}_{t}", 0, 1, pulp.LpInteger),
                            [(i + di, j + dj) for di, dj in dl],
                        )
                    )

    for v1, l1 in vars:
        for v2, l2 in vars:
            if id(v1) == id(v2):
                continue
            tmp = l1 + l2
            if len(set(tmp)) != len(tmp):
                model += v1 + v2 <= 1

    model += pulp.lpSum(v for v, _ in vars) == n * m // 4
    model.solve(pulp.PULP_CBC_CMD(msg=0))
    if model.status != 1:
        print("No")
        return


f(6, 6)
0