yukicoder No.1122 Plane Tickets

コンテスト中の考察

線形計画問題を知っていますか？線形計画問題に見えたのでとりあえず線形計画っぽく書いてみます.

とすると,

\begin{aligned} maximize & T_{1} + T_{2} + T_{3} + T_{4} + T_{5} \\ (1) & subject to & T_{4} + T_{5} + T_{1} \leq a \\ (2) & T_{5} + T_{1} + T_{2} \leq b \\ (3) & T_{1} + T_{2} + T_{3} \leq c \\ (4) & T_{2} + T_{3} + T_{4} \leq d \\ (5) & T_{3} + T_{4} + T_{5} \leq e \\ (6) & T_{i} \geq 0 \end{aligned}

答えに単調性があって, 制約が

10^{15}

なので決め打ち二分探索をする.

つまり,

T_{1} + T_{2} + T_{3} + T_{4} + T_{5} = x

のとき,

(1), (2), (3), (4), (5), (6)

を同時に達成できるかどうかを判定する関数をつくる.

変数 3 つの和は大変なので, どうにかして 1 つにしたい.
ここで

(1) + (3)

をすると,

\begin{aligned} T_{1} + T_{2} + T_{3} + T_{4} + T_{5} + T_{1} & \leq a + c \\ x + T_{1} & \leq a + c \\ T_{1} & \leq a + c - x \end{aligned}

同様に,

\begin{array}{r} T_{1} \leq a + c - x \\ T_{2} \leq b + d - x \\ T_{3} \leq c + e - x \\ T_{4} \leq d + a - x \\ T_{5} \leq e + b - x \end{array}

T_{i}

は,

T_{1} + T_{2} + T_{3} + T_{4} + T_{5} > x

にならない限りできるだけ大きくした方が良く, 多すぎた分は減らせるので,

\begin{array}{r} T_{1} = a + c - x \\ T_{2} = b + d - x \\ T_{3} = c + e - x \\ T_{4} = d + a - x \\ T_{5} = e + b - x \end{array}

と仮定(ただし多すぎた分は減らす).

(6)

を思い出すと条件は,

{\begin{cases} 0 \leq T_{1} \\ 0 \leq T_{2} \\ 0 \leq T_{3} \\ 0 \leq T_{4} \\ 0 \leq T_{5} \\ x \leq T_{1} + T_{2} + T_{3} + T_{4} + T_{5} \end{cases}

となる.

条件が整理できたっぽいのでこの6つを条件として判定する → AC

\begin{aligned} 0 & \leq T_{1} \\ 0 & \leq a + c - x \\ x & \leq a + c \\ x & \leq T_{1} + T_{2} + T_{3} + T_{4} + T_{5} \\ x & \leq (a + c - x) + (b + d - x) + (c + e - x) + (d + a - x) + (e + b - x) \\ 6 x & \leq 2 (a + b + c + d + e) \\ x & \leq \frac{1}{3} (a + b + c + d + e) \end{aligned}

のように整理をして, 条件は

{\begin{cases} x \leq a + c \\ x \leq b + d \\ x \leq c + e \\ x \leq d + a \\ x \leq e + b \\ x \leq \frac{1}{3} (a + b + c + d + e) \end{cases}

つまり, 答えは

min (a + c, b + d, c + e, d + a, e + b, \frac{a + b + c + d + e}{3})

この考察怪しい.

ここで
$(1) + (3)$ をすると,

とか言っているが,

(1) + (3) \Rightarrow (1) \land (3)

はいえない.

線形計画の領域の角のうち

O (1)

で計算できるものを取り出しただけに見える.

しかし, ストレステストをしても落とせない.

どうやら, 条件の式の係数が全部 1 であるため, かなり領域の形がシンプルになって, 角がこれだけになると思われる.

ゆきこD、{a+c, b+d, c+e, d+a, e+b} を考えると各操作は｢5つの変数すべてから1を引く、その後要素を1つ選んでさらに1を引く｣なんですね、すごい
— てんぷら (@tempura_cpp) July 22, 2020