結果
問題 | No.2478 Disjoint-Sparse-Table Optimization |
ユーザー |
👑 |
提出日時 | 2024-10-14 01:37:47 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,713 ms / 2,000 ms |
コード長 | 11,802 bytes |
コンパイル時間 | 111 ms |
コンパイル使用メモリ | 13,824 KB |
実行使用メモリ | 95,676 KB |
最終ジャッジ日時 | 2024-10-14 01:38:10 |
合計ジャッジ時間 | 6,546 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
外部呼び出し有り |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
# https://github.com/hitonanode/linprog-modeler/blob/main/lpmodeler/model.pyfrom enum import Enumfrom typing import SupportsFloatfrom scipy.optimize import linprog # type: ignoreclass LPVarType(Enum):CONTINUOUS = 0INTEGER = 1SEMICONTINUOUS = 2 # 0 or lb <= x <= ubSEMIINTEGER = 3 # 0 or lb <= x <= ub, integerclass LPStatus(Enum):OPTIMAL = 0ITERATION_LIMIT = 1INFEASIBLE = 2UNBOUNDED = 3NUMERICAL_ERROR = 4class LPSense(Enum):MINIMIZE = 0MAXIMIZE = 1class _LPBase:def __add__(self, other: "LPExpressionLike") -> "LPExpression":return LPExpression.build(self) + otherdef __radd__(self, other: "LPExpressionLike") -> "LPExpression":return other + LPExpression.build(self)def __sub__(self, other: "LPExpressionLike") -> "LPExpression":return LPExpression.build(self) - otherdef __rsub__(self, other: "LPExpressionLike") -> "LPExpression":return other - LPExpression.build(self)def __mul__(self, other: SupportsFloat) -> "LPExpression":return LPExpression.build(self) * otherdef __rmul__(self, other: SupportsFloat) -> "LPExpression":return LPExpression.build(self) * otherdef __truediv__(self, other: SupportsFloat) -> "LPExpression":return LPExpression.build(self) / otherdef __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: ignoreself,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 = nameself.lower_bound: float | None = lower_boundself.upper_bound: float | None = upper_boundself.variable_type: LPVarType = variable_typeself._value: float | None = Nonedef __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 sdef __repr__(self) -> str:return str(self)def value(self) -> float | None:return self._valueclass LPInequalityType(Enum):LESSEQ = 1 # lhs <= rhsEQUAL = 2 # lhs == rhsclass _LPTerm(_LPBase):"""A term of the form coefficient * variable."""def __init__(self, coefficient: float, variable: LPVar) -> None:self.coefficient: float = coefficientself.variable: LPVar = variableclass LPExpression:def __init__(self,const: SupportsFloat,terms: list[_LPTerm],) -> None:self.const = float(const)self.terms = terms.copy()self._value: float | None = None@classmethoddef 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 + otherdef __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 * otherdef __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: ignoreself,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._valueLPExpressionLike = LPExpression | _LPTerm | LPVar | SupportsFloatclass 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_typedef __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, sense: LPSense = LPSense.MINIMIZE) -> None:self.sense = senseself.has_impossible_constraints = Falseself.constraints: list[LPInequality] = []self.objective: LPExpression = LPExpression(0, [])self.status: LPStatus | None = Nonedef add_constraint(self, constraint: LPInequality | bool) -> None:if isinstance(constraint, bool):if not constraint:self.has_impossible_constraints = Trueelse: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)# Reset statusself.objective._value = Noneself.status = Nonefor var in var_dict.values():var._value = None# Obviously infeasibleif self.has_impossible_constraints:self.status = LPStatus.INFEASIBLEreturn# Obviously optimalif not var_dict:self.status = LPStatus.OPTIMALself.objective._value = self.objective.constreturnid_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.constfor term in constraint.lhs.terms:lhs[id_to_idx[id(term.variable)]] += term.coefficientif 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 = [v.variable_type.value for v in var_dict.values()]c: list[float] = [0.0] * len(var_dict)func_weight = 1 if self.sense == LPSense.MINIMIZE else -1for term in self.objective.terms:c[id_to_idx[id(term.variable)]] += term.coefficient * func_weightres = 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 sum(integrality) else None,)if res.status == 0:self.status = LPStatus.OPTIMALfor i, variable in enumerate(var_dict.values()):variable._value = res.x[i]self.objective._value = res.fun * func_weight + self.objective.constelif res.status == 1:self.status = LPStatus.ITERATION_LIMITelif res.status == 2:self.status = LPStatus.INFEASIBLEelif res.status == 3:self.status = LPStatus.UNBOUNDEDelif res.status == 4:self.status = LPStatus.NUMERICAL_ERRORelse:raise ValueError("Invalid status code")Q = int(input())LR = [list(map(int, input().split())) for _ in range(Q)]A = list(map(int, input().split()))cum = [0]for a in A:cum.append(cum[-1] + a)edges = []ans = 0for i in range(Q):l1, r1 = LR[i]ans += cum[r1 - 1] - cum[l1 - 1]for j in range(Q):l2, r2 = LR[j]if l1 < l2 and l2 < r1 and r1 < r2:edges.append((i, j, cum[r1 - 1] - cum[l2 - 1]))model = LPModel(LPSense.MAXIMIZE)edge_vars = [LPVar(f"edge_{i}", 0, 1, LPVarType.INTEGER) for i in range(len(edges))]E = [[] for _ in range(Q)]for i, (u, v, _) in enumerate(edges):E[u].append(edge_vars[i])E[v].append(edge_vars[i])for i in range(Q):model.add_constraint(sum(E[i]) <= 1)model.set_objective(sum(w * e for (_, _, w), e in zip(edges, edge_vars)))model.solve()assert model.status == LPStatus.OPTIMALans -= round(model.objective.value())print(ans)