#960344 (Python3) No.2675 KUMA

提出ソース

結果

問題	No.2675 KUMA
ユーザー	hitonanode
提出日時	2024-03-15 22:10:59
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	RE
実行時間	-
コード長	10,714 bytes
コンパイル時間	421 ms
コンパイル使用メモリ	13,440 KB
実行使用メモリ	135,652 KB
最終ジャッジ日時	2024-09-30 01:30:59
合計ジャッジ時間	77,253 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,691 ms 69,796 KB
testcase_01	AC	1,453 ms 68,236 KB
testcase_02	AC	1,436 ms 69,408 KB
testcase_03	AC	1,455 ms 69,800 KB
testcase_04	AC	1,453 ms 69,284 KB
testcase_05	AC	1,488 ms 69,408 KB
testcase_06	AC	1,461 ms 69,540 KB
testcase_07	AC	1,456 ms 69,544 KB
testcase_08	AC	1,464 ms 69,536 KB
testcase_09	RE	-
testcase_10	AC	1,488 ms 69,664 KB
testcase_11	AC	1,477 ms 69,820 KB
testcase_12	AC	1,492 ms 70,056 KB
testcase_13	AC	1,474 ms 69,660 KB
testcase_14	AC	1,512 ms 69,156 KB
testcase_15	AC	1,474 ms 69,160 KB
testcase_16	AC	1,491 ms 69,424 KB
testcase_17	AC	1,472 ms 69,316 KB
testcase_18	AC	1,453 ms 69,544 KB
testcase_19	AC	1,468 ms 69,668 KB
testcase_20	AC	1,452 ms 69,544 KB
testcase_21	AC	1,461 ms 69,916 KB
testcase_22	AC	1,461 ms 69,544 KB
testcase_23	AC	1,471 ms 69,148 KB
testcase_24	AC	1,458 ms 69,664 KB
testcase_25	AC	1,451 ms 69,920 KB
testcase_26	AC	1,442 ms 69,160 KB
testcase_27	AC	1,446 ms 69,544 KB
testcase_28	AC	1,443 ms 69,796 KB
testcase_29	AC	1,450 ms 69,400 KB
testcase_30	AC	1,463 ms 69,920 KB
testcase_31	AC	1,449 ms 69,912 KB
testcase_32	AC	1,453 ms 69,920 KB
testcase_33	AC	1,467 ms 69,544 KB
testcase_34	AC	1,445 ms 69,396 KB
testcase_35	AC	1,473 ms 69,660 KB
testcase_36	AC	1,474 ms 69,532 KB
testcase_37	AC	1,542 ms 69,280 KB
testcase_38	AC	1,465 ms 69,928 KB
testcase_39	AC	1,457 ms 69,788 KB
testcase_40	AC	1,454 ms 69,676 KB
testcase_41	AC	1,456 ms 69,792 KB
testcase_42	AC	1,437 ms 69,668 KB
testcase_43	AC	1,446 ms 69,412 KB
testcase_44	AC	1,466 ms 69,404 KB
testcase_45	AC	1,465 ms 69,556 KB
testcase_46	AC	1,457 ms 69,968 KB
testcase_47	AC	1,451 ms 69,536 KB
testcase_48	AC	1,463 ms 135,652 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

from enum import Enum
from typing import SupportsFloat

from scipy.optimize import linprog  # type: ignore


class LPVarType(Enum):
    CONTINUOUS = 1
    INTEGER = 2


class _LPBase:
    def __add__(self, other: "LPExpressionLike") -> "LPExpression":
        return LPExpression.build(self) + other

    def __radd__(self, other: "LPExpressionLike") -> "LPExpression":
        return other + LPExpression.build(self)

    def __sub__(self, other: "LPExpressionLike") -> "LPExpression":
        return LPExpression.build(self) - other

    def __rsub__(self, other: "LPExpressionLike") -> "LPExpression":
        return other - LPExpression.build(self)

    def __mul__(self, other: SupportsFloat) -> "LPExpression":
        return LPExpression.build(self) * other

    def __rmul__(self, other: SupportsFloat) -> "LPExpression":
        return LPExpression.build(self) * other

    def __truediv__(self, other: SupportsFloat) -> "LPExpression":
        return LPExpression.build(self) / other

    def __neg__(self) -> "LPExpression":
        return -LPExpression.build(self)

    def __le__(
        self,
        other: "LPExpressionLike",
    ) -> "LPInequality":
        return LPInequality(
            lhs=LPExpression.build(self),
            rhs=other,
            inequality_type=LPInequalityType.LESSEQ,
        )

    def __ge__(
        self,
        other: "LPExpressionLike",
    ) -> "LPInequality":
        return LPInequality(
            lhs=other,
            rhs=LPExpression.build(self),
            inequality_type=LPInequalityType.LESSEQ,
        )

    def __eq__(  # type: ignore
        self,
        other: "LPExpressionLike",
    ) -> "LPInequality":
        return LPInequality(
            lhs=LPExpression.build(self),
            rhs=other,
            inequality_type=LPInequalityType.EQUAL,
        )


class LPVar(_LPBase):
    def __init__(
        self,
        name: str,
        lower_bound: float | None = None,
        upper_bound: float | None = None,
        variable_type: LPVarType = LPVarType.CONTINUOUS,
    ) -> None:
        self.name = name
        self.lower_bound: float | None = lower_bound
        self.upper_bound: float | None = upper_bound
        self.variable_type: LPVarType = variable_type
        self._value: float | None = None

    def __str__(self) -> str:
        s = "{}(lb={}, ub={}, type={})".format(
            self.name,
            self.lower_bound,
            self.upper_bound,
            self.variable_type.name,
        )
        if self._value is not None:
            s += ": {}".format(self._value)
        return s

    def __repr__(self) -> str:
        return str(self)

    def value(self) -> float | None:
        return self._value


class LPInequalityType(Enum):
    LESSEQ = 1  # lhs <= rhs
    EQUAL = 2  # lhs == rhs


class _LPTerm(_LPBase):
    """
    A term of the form coefficient * variable.
    """

    def __init__(self, coefficient: float, variable: LPVar) -> None:
        self.coefficient: float = coefficient
        self.variable: LPVar = variable


class LPExpression:
    def __init__(
        self,
        const: SupportsFloat,
        terms: list[_LPTerm],
    ) -> None:
        self.const = float(const)
        self.terms = terms.copy()
        self._value: float | None = None

    @classmethod
    def build(self, x: "LPExpressionLike | _LPBase") -> "LPExpression":
        if isinstance(x, LPExpression):
            return LPExpression(x.const, x.terms)
        elif isinstance(x, _LPTerm):
            return LPExpression(0, [x])
        elif isinstance(x, LPVar):
            return LPExpression(0, [_LPTerm(1.0, x)])
        elif isinstance(x, SupportsFloat):
            return LPExpression(x, [])
        else:
            raise TypeError("Invalid type for LPExpression")

    def __add__(self, other: "LPExpressionLike") -> "LPExpression":
        rhs = LPExpression.build(other)
        return LPExpression(
            self.const + rhs.const,
            self.terms + rhs.terms,
        )

    def __radd__(self, other: "LPExpressionLike") -> "LPExpression":
        return self + other

    def __sub__(self, other: "LPExpressionLike") -> "LPExpression":
        rhs = LPExpression.build(other)
        return self + (-rhs)

    def __rsub__(self, other: "LPExpressionLike") -> "LPExpression":
        return LPExpression.build(other) + (-self)

    def __mul__(self, other: SupportsFloat) -> "LPExpression":
        return LPExpression(
            self.const * float(other),
            [
                _LPTerm(
                    t.coefficient * float(other),
                    t.variable,
                )
                for t in self.terms
            ],
        )

    def __rmul__(self, other: SupportsFloat) -> "LPExpression":
        return self * other

    def __truediv__(self, other: SupportsFloat) -> "LPExpression":
        return LPExpression(
            self.const / float(other),
            [
                _LPTerm(
                    t.coefficient / float(other),
                    t.variable,
                )
                for t in self.terms
            ],
        )

    def __neg__(self) -> "LPExpression":
        return LPExpression(
            -self.const,
            [_LPTerm(-t.coefficient, t.variable) for t in self.terms],
        )

    def __le__(
        self,
        other: "LPExpressionLike",
    ) -> "LPInequality":
        return LPInequality(self, other, LPInequalityType.LESSEQ)

    def __ge__(
        self,
        other: "LPExpressionLike",
    ) -> "LPInequality":
        return LPInequality(other, self, LPInequalityType.LESSEQ)

    def __eq__(  # type: ignore
        self,
        other: "LPExpressionLike",
    ) -> "LPInequality":
        return LPInequality(self, other, LPInequalityType.EQUAL)

    def __str__(self) -> str:
        ret = ["{}".format(self.const)]

        for t in self.terms:
            sgn = "+" if t.coefficient >= 0 else ""
            ret.append("{}{}{}".format(sgn, t.coefficient, t.variable.name))

        return " ".join(ret)

    def value(self) -> float | None:
        return self._value


LPExpressionLike = LPExpression | _LPTerm | LPVar | SupportsFloat


class LPInequality:
    def __init__(
        self,
        lhs: LPExpressionLike,
        rhs: LPExpressionLike,
        inequality_type: LPInequalityType,
    ) -> None:
        """
        lhs <= rhs
        -> terms + const (<= or ==) 0
        """

        self.lhs = LPExpression.build(lhs) - LPExpression.build(rhs)
        self.inequality_type = inequality_type

    def __str__(self) -> str:
        if self.inequality_type == LPInequalityType.LESSEQ:
            return "{} <= 0".format(self.lhs)
        elif self.inequality_type == LPInequalityType.EQUAL:
            return "{} == 0".format(self.lhs)
        else:
            raise ValueError("Invalid inequality type")

    def __repr__(self) -> str:
        return str(self)


class LPModel:
    def __init__(self) -> None:
        self.constraints: list[LPInequality] = []
        self.objective: LPExpression = LPExpression(0, [])

    def add_constraint(self, constraint: LPInequality) -> None:
        self.constraints.append(constraint)

    def set_objective(self, objective: LPExpressionLike) -> None:
        self.objective = LPExpression.build(objective)

    def solve(self) -> None:
        var_dict: dict[int, LPVar] = {}
        for constraint in self.constraints:
            for term in constraint.lhs.terms:
                var_dict.setdefault(id(term.variable), term.variable)

        for term in self.objective.terms:
            var_dict.setdefault(id(term.variable), term.variable)

        id_to_idx = {id(v): i for i, v in enumerate(var_dict.values())}

        A_ub: list[list[float]] = []
        b_ub: list[float] = []
        A_eq: list[list[float]] = []
        b_eq: list[float] = []

        for constraint in self.constraints:
            lhs: list[float] = [0.0] * len(var_dict)
            rhs = -constraint.lhs.const

            for term in constraint.lhs.terms:
                lhs[id_to_idx[id(term.variable)]] += term.coefficient

            if constraint.inequality_type == LPInequalityType.LESSEQ:
                A_ub.append(lhs)
                b_ub.append(rhs)
            elif constraint.inequality_type == LPInequalityType.EQUAL:
                A_eq.append(lhs)
                b_eq.append(rhs)
            else:
                raise ValueError("Invalid inequality type")

        bounds = [(v.lower_bound, v.upper_bound) for v in var_dict.values()]

        integrality = [
            int(variable.variable_type == LPVarType.INTEGER)
            for variable in var_dict.values()
        ]

        c: list[float] = [0.0] * len(var_dict)
        for term in self.objective.terms:
            c[id_to_idx[id(term.variable)]] += term.coefficient

        res = linprog(
            c,
            A_ub=A_ub or None,
            b_ub=b_ub or None,
            A_eq=A_eq or None,
            b_eq=b_eq or None,
            bounds=bounds,
            integrality=integrality,
        )

        if res.status == 0:
            for i, variable in enumerate(var_dict.values()):
                variable._value = res.x[i]

            self.objective._value = res.fun + self.objective.const


from itertools import product

N = int(input())
xys = [tuple(map(int, input().split())) for _ in range(N)]

keimas = [
    (2, -1),
    (2, 1),
    (-2, -1),
    (-2, 1),
    (1, 2),
    (1, -2),
    (-1, 2),
    (-1, -2),
]

targets = []

for x, y in xys:
    for a, b in keimas:
        targets.append((x + a, y + b))

targets = [x for x in sorted(set(targets)) if x not in xys]

# print(targets)

lp = LPModel()

dirs = [
    [(2, -1), (2, 1)],
    [(-2, -1), (-2, 1)],
    [(-1, -2), (1, -2)],
    [(-1, 2), (1, 2)],
]

sgns = [LPVar(f'{i}{j}', lower_bound=0, upper_bound=1, variable_type=LPVarType.INTEGER) for i, j in product(range(len(targets)), range(len(dirs)))]

for j in range(N):
    vs = []
    for i, (x, y) in enumerate(targets):
        for d, dir in enumerate(dirs):
            match = False
            for dx, dy in dir:
                if (x + dx, y + dy) == xys[j]:
                    match = True
                    break
            
            if match:
                vs.append(sgns[i * len(dirs) + d])

    # print(xys[j], vs)
    if vs:
        lp.add_constraint(sum(vs) >= 1)
    else:
        print(-1)
        exit()

for i in range(len(targets)):
    lp.add_constraint(sum([sgns[i * len(dirs) + d] for d in range(len(dirs))]) <= 1)

lp.set_objective(sum(sgns))  # 最小化する目的関数

try:
    lp.solve()
except:
    print(-1)
    exit()

print(int(lp.objective.value() + 0.1))

yukicoder

結果

テストケース

ソースコード