AtCoder AGC027 B Garbage Collector

　さて。土曜から月曜まで世間では三連休だったらしく、市バスの定期を活用して本を読みながら京都市内をのりまわしていると、どっかから京都まで観光に来たらしいカップルがうきうきと京都にいたころの昔話をしていたりしていたが、自分は本を読む一方で、土曜の夜やりそこねた AGC027 B をネチネチやっていた。本→AGC027B→本→AGC027Bという具合。人によっては30分くらいで解いてるものにそんなに時間をかけていいものだろうか。いいのだ。人類の再生産に失敗して中年のおっさんになった個体の人生なんか無意味なので好きに使わせてもらう。

　AGC027 Bの構造であるが、こうなっている。

数直線上にゴミがN個落ちているので回収する。ゴミ箱は原点にある。出てくる数字は全部整数。
距離1進むのに手ぶらで1、ゴミM個持つと (M+1)² エネルギーがいる
拾ったり捨てたりするのにエネルギーXかかる

　ゴミを回収するのに持てば持つほど二乗でエネルギーいるので間違いなく遠い方から順番に拾っていった方がいい。ただ一回づつ行く方がいいのかまとめていった方がいいのかはゴミを取るときのエネルギーと距離のバランスということになるんだろう。

　とりあえずゴミの距離をLとして式をつくってみると

ゴミ1個一往復で
- X + L1 + X + (1+1)² L1
- → 2X + 5L1
ゴミ2個一往復で
- X + L1 + X + (1+1)² (L1-L2) + X + (2+1)² L2
- → 3X + 5L1 + 5L2
ゴミ3個一往復で
- X + L1 + X + (1+1)² (L1-L2) + X + (2+1)² (L2 - L3) + X + (3+1)² L3
- → 4X + 5L1 + 5L2 + 7L3
ということでi個まとめて持つと
- (i + 1)X + 5L1 + 5L2 +...+ (2i+1)Li

　土曜の夜にCの無向グラフを検索して遊んでたりしなければもうすこし考察できていたのだろうが、まぁこれくらいしかできなかった。実はこれだけわかっていてばもう答の出し方は出たようなものだがそのときは全然気付かなかった。そのときわかったことはこうだ。

一個づつ運ぶよりは二個づつ運ぶ方がコストが低い

　ただし時間がなかったので、一気に全部運ぶ式をつくってサンプルを計算してみれば半分合っていたのでとりあえずそれで提出してみたところ一つしかACできなかった。翌日はこの「二個づつ運ぶ方がコストが低い」ことと「後ろから順番に拾う」ことに囚われてしまい、遠い方から二個づつ選び、三つめを運んだらエネルギーが低いか高いかという判定をつけるというような面倒なやりかたをひねりだしてとりあえずサンプルは通したので提出してみたところ、半分はACできなかった。やはり二個づつ運ぶ時と全部一気に運ぶ時の間にもエネルギーが低くなるバランスの時があるようだ。わからん。

　そこで解説をみたが、初めてみる記号(天開記号)とかあったがそれはともかく、分割して総当たりみたいなことが書いてある。K回分割するとゴミ拾捨エネルギーXは(N+K)X になるので別に考えればよいと。なるほど。で、そんな感じのものを書いてみたが通らない。それもそのはずで、うしろから順番にやっていったのでできるわけないのだ。ここでググったり人の解答みてどうするのかやっとわかった。ということで式にもどると

(i + 1)X + 5L1 + 5L2 +...+ (2i+1)Li

　これが基本になる。この係数 2i + 1 が増えれば増えるほど重石になるので、なるべく距離の小さい方、原点に近い方に寄せたい。となると以下の図のようになるわけだ。

f:id:inudaisho:20180917231742p:plain

　左側に原点があるとして遠い方から第一項となるように振りわけていけばよいということになる。この一集団の幅がKになり、最後の一番係数の多い集団の幅はK以下になる。ゴミ取捨コストXが無茶苦茶でかいと、Xを減らすためにKが1まで下がる。その場合全部一気に拾うことになる。計算で楽をするために累積和の配列を使う。よくよくこの図をみると全集団合計 * 5 + 第三集団以下合計 * 2 + 第四集団以下合計 * 2 +... と分けれるのでそうすると計算が楽になる。あと1個往復よりも2個往復の方が確実にエネルギーが低いことも使うとループが半分くらいですむ。他にも枝刈りの方法はあるんだろうがこれだけやったらTLEは回避できるようだ。(Kの幅をXまで狭めてからナメてもできた。)こんなの時間内に解答できるやつはほんとすごいなぁ。

　AtCoder は Python3 でやってるがかなりよい。ループを重ねすぎるとすぐ時間超過するのでロジックをどうやって組むかに真剣にならざるをえない。C++ は速すぎてループをグルグルまわしてもなんとかなってしまう。40代の腐れたおっさんが競技者になれるわけがないのでこれでいいのだ。