AGC022 D - Shopping

この記事を書いている時点で、AGC-Dの中で配点が最も高い問題。私自身AGC-Dを全問通しましたが、ダントツで一番難しい問題だと感じました。解説ACをするのにも非常に苦労しました…

この回は解説放送のアーカイブがなくて、解説記事も全然書かれていないようなので、高難度問題の解説に挑戦する意味でも書いてみたいと思います。

解法

周期で余りを取る

電車の総移動距離は電車の往復距離 $2L$ に往復回数を掛けた値なので、往復回数の最小値を求めることを考えます。

まず、ユイが買い物をしている時間 $t_{i}$ を電車の周期である $2L$ で割って余りを取ります。ここで減る分の時間は買い物をしている間に電車が往復しているだけなので、固定で掛かる往復回数として別途計算しておきます。ここで減らした往復回数の合計を $C$ とします。

ただし $t_{i}$ がちょうど $2L$ で割り切れるときは、 $0$ とせずに $2L$ だけ残しておいたほうが後々やりやすいです。

愚直なルートを考える

余りを取る操作によって $t_{i}$ は $1 \le t_{i} \le 2L$ の範囲に収まりました。このとき、以下のような愚直なルートを考えることができます。赤線がユイの移動、青破線が電車だけが動いているところを示します。

f:id:betrue12:20190407184320p:plain

図では途中の駅が4つあり、全部で5往復しています。一般にこのルートでは駅の数 $N$ に対して $N+1$ 回の往復が必要です。

このルートから短縮できるとしたら、どのようなルートになるかを考えていきます。

「買い物の後、端で反射してきた電車に乗れるか？」を考える

先ほどのルートでは、ユイが各駅に滞在している間に必ず電車が1往復していました。しかし実際には、一方の端で折り返して戻ってきた電車に間に合うこともあります。この場合は進行方向が反転します。

f:id:betrue12:20190407192715p:plain

折り返してきた電車に間に合うための条件は、左から入った時（右で折り返す時）と右から入った時（左で折り返す時）で異なります。後の説明の都合から、折り返す方向で区別することにします。具体的には右で折り返す時に間に合う条件は $t_{i} \le 2(L-x_{i})$ であり、左で折り返す時に間に合う条件は $t_{i} \le 2x_{i}$ です。

これを利用してルートの短縮ができないか考えます。

ルート短縮方法を考える

ルート短縮方法は、大きく分けると2つあります。

まず1つ目として、一番右にある駅が「右で折り返す時に間に合う」駅だった場合に、以下のようなルートにすることで往復を1回減らすことができます。元のルートでは「ユイが電車に乗ったまま右端に到達する」ということが1回ありましたが、それが無くなることで無駄を省いています。

f:id:betrue12:20190407184332p:plain

次に2つ目として、「左で折り返す時に間に合う」駅と「右で折り返す時に間に合う」駅がこの順番で並んでいる時に、以下のようなルートにすることで往復回数を1回減らすことができます。

f:id:betrue12:20190407184347p:plain

このように「ユイを右端に到達させないことで往復回数を減らす」「左右で1回ずつ折り返しに間に合わせることで往復回数を減らす」の2つの短縮方法があり、これ以外にはありません。そのため元のルートを短縮するような全てのルートは、並び替えると上の2パターンのどちらかと同じになります。（本当はここの証明をちゃんとやらないといけないですね…）

なので元々の往復回数 $N+1$ から始めて、以下のように減らせる回数を考えればそれが最適解となります。