ABC117 C問題 反省会
Streamline
これです。簡単なはずなんだけど解けなかったので反省がてら図解します。
問題設定
上図のように、数直線上に M 個の座標があって、それらを N 個のコマですべて訪れたい。はじめにコマを置くのは手数に入れず、コマの移動（前後 ±1 に限る）を 1 手と数えた場合、最短何手ですべてのターゲットを訪れられるか。
実験
具体的な場合から考えてみます。まずコマを移動させる方向は左から右、または右から左のどちらか一方向に限ってよいでしょう。行ったり来たりしても移動が増えるだけだからです。
今回は左から右へのみ移動することにします。
N = M の場合
特殊かつ考えやすい場合から考えてみます。コマの数 M がターゲット座標数 N に等しい場合、0 回の移動で目的は達成されました。上の図ではコマを置いた座標を黒く塗りつぶしました。
N = M - 1 の場合
さきほどのケースから、コマを 1 つ減らしました。上図ではとりあえず右端のターゲット座標が最初に空いていることにしました。するとその左隣のターゲット座標に置いたコマを右端のターゲット座標に移動させればよいですね。
このとき必要な移動回数は、いま注目している 2 つのターゲット座標の間隔に等しいですね。
最適な区間を選ぶ
移動回数をできるだけ少なくしたいので、最も短い区間を 1 つだけ選びます。
上図では、左端の区間が最短なので、それを選びます。
コマをもっと減らす
さきほどはコマがターゲット座標に対して 1 個足りませんでしたが、さらにもう 1 個、合計 2 個足りない場合はどうすればよいでしょうか。
最短の区間はもう選んであるので、次に短い区間を 2 個めとして選べば、最小の移動回数ですべてのターゲットを訪れることができます。
一般化
ここまで来たら、もうコマをどんどん減らしても問題ありませんね。結局、コマの不足数である M - N 個だけ、ターゲット座標で区切られた区間を短い順に選ぶことで、最小の移動回数ですべてのターゲットを訪れることができます。
本当に？
選ぶ区間が連続していなくていいのだろうかとか、コマを 1 個ずつ減らしていったら選ぼうとした区間の右端や左端のコマがすでになくなっていたりするんじゃないかとか思うかもしれませんが、そのような心配は不要です。
ここでは、左から右に移動すると決めていました。すると
になります。この時点で「選んだ区間の右端のコマがもうなかった」という事態がありえないことがわかります。また選んだ区間が連続していなくても、その区間の左端にコマがあれば選んだ区間の右端を訪れることができます。そこにコマがない場合は、左に隣接する区間も既に選ばれたということであり、ここで数直線の最も左端にあるターゲット座標には必ずコマが置かれているので、左側からいずれコマがやってくることがわかります。
解答
お粗末さまでした。
