結果
| 問題 | No.2478 Disjoint-Sparse-Table Optimization |
| ユーザー |
👑  rin204
|
| 提出日時 | 2024-10-14 01:36:45 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,802 bytes |
| コンパイル時間 | 700 ms |
| コンパイル使用メモリ | 13,568 KB |
| 実行使用メモリ | 163,488 KB |
| 最終ジャッジ日時 | 2024-10-14 01:37:14 |
| 合計ジャッジ時間 | 25,109 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | AC | 1,286 ms
69,856 KB |
| testcase_02 | AC | 1,267 ms
68,356 KB |
| testcase_03 | AC | 1,576 ms
79,648 KB |
| testcase_04 | AC | 1,512 ms
79,212 KB |
| testcase_05 | AC | 1,354 ms
71,556 KB |
| testcase_06 | AC | 1,454 ms
75,396 KB |
| testcase_07 | AC | 1,493 ms
76,544 KB |
| testcase_08 | AC | 1,436 ms
76,200 KB |
| testcase_09 | AC | 1,528 ms
77,580 KB |
| testcase_10 | AC | 1,426 ms
77,856 KB |
| testcase_11 | AC | 1,628 ms
82,700 KB |
| testcase_12 | AC | 1,278 ms
67,908 KB |
| testcase_13 | AC | 1,776 ms
163,488 KB |
ソースコード
# https://github.com/hitonanode/linprog-modeler/blob/main/lpmodeler/model.py
from enum import Enum
from typing import SupportsFloat
from scipy.optimize import linprog # type: ignore
class LPVarType(Enum):
CONTINUOUS = 0
INTEGER = 1
SEMICONTINUOUS = 2 # 0 or lb <= x <= ub
SEMIINTEGER = 3 # 0 or lb <= x <= ub, integer
class LPStatus(Enum):
OPTIMAL = 0
ITERATION_LIMIT = 1
INFEASIBLE = 2
UNBOUNDED = 3
NUMERICAL_ERROR = 4
class LPSense(Enum):
MINIMIZE = 0
MAXIMIZE = 1
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, sense: LPSense = LPSense.MINIMIZE) -> None:
self.sense = sense
self.has_impossible_constraints = False
self.constraints: list[LPInequality] = []
self.objective: LPExpression = LPExpression(0, [])
self.status: LPStatus | None = None
def add_constraint(self, constraint: LPInequality | bool) -> None:
if isinstance(constraint, bool):
if not constraint:
self.has_impossible_constraints = True
else:
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 status
self.objective._value = None
self.status = None
for var in var_dict.values():
var._value = None
# Obviously infeasible
if self.has_impossible_constraints:
self.status = LPStatus.INFEASIBLE
return
# Obviously optimal
if not var_dict:
self.status = LPStatus.OPTIMAL
self.objective._value = self.objective.const
return
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 = [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 -1
for term in self.objective.terms:
c[id_to_idx[id(term.variable)]] += term.coefficient * func_weight
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 sum(integrality) else None,
)
if res.status == 0:
self.status = LPStatus.OPTIMAL
for i, variable in enumerate(var_dict.values()):
variable._value = res.x[i]
self.objective._value = res.fun * func_weight + self.objective.const
elif res.status == 1:
self.status = LPStatus.ITERATION_LIMIT
elif res.status == 2:
self.status = LPStatus.INFEASIBLE
elif res.status == 3:
self.status = LPStatus.UNBOUNDED
elif res.status == 4:
self.status = LPStatus.NUMERICAL_ERROR
else:
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 = 0
for 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.OPTIMAL
ans -= round(model.objective.value())
print(ans)