ABC313 E - Takahashi Quest

方針

モンスターから最も近い場所にある、同じタイプポーションをとって戦う

その証明

この方法よりも最適な戦略があったとする。

「最適な」：「各時刻において持ち合わせているポーションの数の、時刻にわたる最大数が最小である」

全ての戦略を最小性の表現しやすい形態に置き換える

code:example.txt

P---P--P-------E-----E---> t

| | | |

| +-------+ |

+----------------+

Eを起点として時刻の負方向に使用するのポーションへ伸ばすという形態になる。

この設定の方法が「戦略」と呼んでいたもの

この表現形態だと、最小性を評価しやすい

各時刻に対して持ってるポーションの数は「重なっている区間の数」と等しい

最小性の評価

code:example.txt

P---P--P-------E-----E---> t

| | | | | <--- このEの部分は固定されている。

| | +-------+ |

+- -+----------------+

<-- 他の戦略を作り出そうとしても、こっち方向に伸ばすしかない

よって、各時刻におけるポーション保有数は貪欲法による戦略より、等しいかより大きくしかならない。

したがって、その最大数も等しいかより大きくしかならない。

貪欲法が最良である。

実装

敵から時刻負方向へ依存関係がある。

後ろ側からカウントしていくのがより効率が良い。

前側からだと評価しづらい。