ABC 117 C - Streamlineのメモ
過去問周回でなんとなく選んだ問題です。
考えたこと
自力で解けませんでしたが、とりあえず考えたことを書いておきます。
まず、コマの初期位置は訪れる必要がある地点のどこかでよさそうです。そうすれば移動距離ゼロでその地点については訪れたことになります。なので、NがM以上なら0が答えになります。
（なお、同じ場所に複数のコマを置いていいとのことですが、それは特にメリットはなさそうです）
ではそうではない場合はどうなるか。
Xはサンプルを見る限りバラバラな順番で来ますが、面倒なのでソートして考えます。（以降、Xはソート済とします）
それで、仮にコマが1つしかないとすれば、Xの末尾の値から先頭の値を引いた値が移動距離になります。ではコマが2つ以上あればどうなるか。
コマの移動区間がかぶると無駄なので最短になりません。なのでかぶらないようにそれぞれのコマをバラバラに最適な位置に配置してそれぞれを動かして地点を訪問させればいいです。そのように各コマの担当区間が決まれば、あとはそれぞれの右端の値から左端の値を引いた値をそれぞれ求めて、それを全部足せば答えになります。
そこまではわかったのですが、それぞれの最適な初期位置はどうやって求めればいいのでしょうか？ここで詰まりました。
なんか1つ解法らしきものを思いついた気がするのですが、ダメっぽくて即切り捨てたのでどんなことだったのか覚えてません。ただ、なんか愚直に移動をシミュレーションするような方法だったと思います。今の私の脳はそのような方法しか思いつかないので。ばかげている、なんか計算で求めないとダメそうだな、と思ったことは覚えています。
何にせよ、どのような計算をすればいいのかわからなかったのでここでギブアップして解説を見ました。
解説を見て
結論としては「Xの範囲全体の長さから、通らない区間の長さを引いて求める。引くのは、区間が長いほうからN - 1個分」ということになります。通る区間の合計を足して求めるのではなく、通らない区間の合計を引いて求めればよかったのですね…
提出したコードはこちら。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val x = readLine()!!.split(" ").map { it.toInt() }.sorted()
val diffList = (1 until m).map {
x[it] - x[it - 1]
}
.sortedDescending()
.take(n - 1)
println(x[m - 1] - x.first() - diffList.sum())
}
通らない区間の大きいほうを求めるには、まず区間の長さリストが必要です。それがdiffListです。Xはソート済なので、ある地点の値から前の地点の値を引いたリストを作ればいいです。1つ前を参照するので1から始めます。
そのうち大きい方を取得したいので降順ソートします。引くべき区間の数はN - 1個になりますので、降順ソートした結果の先頭のN - 1個だけのリストにします。
あとはそれの合計値をXの範囲全体の長さから引けばいいです。
Xの範囲全体の長さは、Xの末尾の値から先頭の値を引けば求められます。
感想
解説動画がわかりやすくて、理解したと思った後すぐにコードを書いて提出したら通りました。なのでその瞬間は理解したと思ったのですが、時間が経ってこの記事を書いていたらなんだか本当に理解したのかよくわからなくなってきました。期間が空いて忘れてからまた解こうとしたら解けないような気がします。
結局何をやっても、毎回「根本的に数学力が足りない」という感想を抱きます。数学の勉強は始めていて少しずつ進めているので、まあ時間をかけて力をつけていけばそのうちなんとかなると思うしかないですかねぇ。
この問題から汲み取れる教訓としては、足してダメなら引いてみなってところでしょうか。それぐらい普通すぐにわかるのかもしれませんが、私は残念ながら思いつかなかったので、思考パターンの一つとして記憶しておこうと思います。
Discussion