競プロ参戦記 第12回「地道な考察」 AGC 27 [AB]
競技プログラミングの大会 AtCoder Grand Contest に参加しました。ABC/ARC より難しい、世界レベルの大会らしいです。
私はA完でした。Bの部分点にかじりついていたんですが分からぬ……
AtCoder Grand Contest 027
問題リスト：
A - Candy Distribution Again
問題概要：人 i はちょうど a(i) 個のお菓子をもらうと喜ぶ。N人に合計X個のお菓子を配りきった。喜んだ人数の最大値を求めよ
解説：少ないお菓子で喜ぶ人を優先するのが最適です。a(i) について昇順にお菓子を可能な限り配ります。
注意点は、お菓子はすべて配らなければいけないことと、ちょうどでなければ人は喜ばないことです。過ぎたるは及ばざるがごとし。全員に配ってもお菓子が余ってしまうときは、残りを誰かに押しつけなければいけません。(これに気づかなくて、1回誤答を出してしまいました。)
提出：
B - Garbage Collector
問題概要：数直線上の位置 x(i) にゴミがあり、位置0にGCとゴミ箱がある。GCを使ってすべてのゴミをゴミ箱に移した。かかったコストの最小値を求めよ。GCの使いかたは以下の通り。
1. GCを移動させるとき、距離1あたり (k+1)^2 のコストがかかる。k はGCが抱えているゴミの個数。
2. GCと同じ位置のゴミを拾うのにコスト X かかる。
3. GCと同じ位置のゴミ箱にゴミを入れるのにコスト X かかる。(ゴミの個数によらない。)
ゴミの個数 N の制約は N ≤ 2・10^5 ですが、N ≤ 2000 のケースだけ解けば部分点 400 がもらえます。(注意：部分点400はARCの400点問題より難しいことが多い。)
部分点狙いで考察していましたが解けませんでした。
考察 (1) (正しい)：最初に気づくのは、移動のコストを減らすためにGCの移動が一定の規則を持つことです。GCは位置0を出発して、拾うべきゴミのうち最も遠いところに移動し、拾うべきゴミを拾いながら位置0に戻る。これの繰り返しです。行ったり来たりする必要はなく、行きしなで拾う必要もない。
つまりゴミの集合を「一周で拾うゴミの集合」の集合に分割するという問題と捉えられます。要素数 2000 の集合の分割は状態数が多すぎるので、もう少し絞りたい。
考察 (2) (完全に誤り)：おそらく「一周で拾うゴミの集合」は区間になるのでは？ という予想が立ちます。(誤りです。) つまりゴミ a, b, c がこの順で配置されているとき、 a, c を拾った後に b を拾うのではなく、 a, b を拾った後に c を拾うのが最適解になるのでは？ ということです。これならメモ化再帰で解けそうです。単純に書くと O(N^3) ですが区間幅は1のときと最大のときでコストが最大になるのでは？ という予想が立つので三分探索ができそう…… ダメでした。
追記：解説PDFを読んだら意味が分かったので、改めて自分なりに解説を書きます。
考察 (3)：簡単のため点列の順番を逆転させた関数を定義します。
// 遠いほうから i 番目の点の位置
y(i) = x(N + 1- i)すべてのゴミを一周で回収するときのコストを計算します。繰り返しになりますが、GCの移動コストを減らすため、位置0→y(1)→位置0と移動して戻る道中でゴミを拾います。
まず、位置 0 から位置 y(1) に移動して y(1) のコストがかかります。それから y(1)→y(2)→...→y(N) と、持っているゴミの個数を変化させながら移動します。
y(1)→y(2) ではゴミ数 k=1 なので 4・(y(1) - y(2))、
y(2)→y(3) ではゴミ数 k=2 なので 9・(y(2) - y(3))……
y(N-1)→y(N) ではゴミ数 k=N-1 なので N^2・(y(N-1) - y(N))
これらのコストの総和をとると、t = 1 を除く y(t) の係数は
(t+1)^2 - t^2 = 2t + 1
そして y(1) の係数は、行きにかかる 1 を加えて 1 + 2^2 = 5 です。つまり係数列は 5, 5, 7, 9, 11, ... となります。
さて、点列をいくつかに分割し、各列を一周で回収します。これは点に上記の係数を対応させていくということです。
例えばゴミが 1,2,3,4,5 にあるとき
1周なら：
係数列 (5, 5, 7, 9, 11)
点列 (5, 4, 3, 2, 1)
2周なら：
係数列 (5, 5, 7)
点列 (5, 4)
点列 (3, 2, 1)一周ですべてのゴミを拾うと、いくつかの点に大きい係数をかかります。複数回に分けてゴミを拾うと、小さい係数しかかからない代わりに、ゴミを投入するコスト X が増えます。うまい分割を探したい。
m 周すると決めたとすると、かけるべき係数列は簡単に決まります。小さい係数を多く発生させるために、点列の長さは均一にします。5,5,7,9, .. が m パターンずつ発生するわけです。これらを遠い順に点に割り当てていきます。
結果として、遠いほうから順に、2m 個の点には係数 5 がかかり、次に近い m 個には係数 7 がかかり、次に近い m 個には係数 9 がかかり、……という具合です。
これを問題設定に合わせていうと、残っているゴミの右端の2つ、その m 個前のゴミ、その m 個前のゴミ、という順で拾っていくことに対応します。
「m 個の点の間の距離」は累積和で高速に求まります。周回数 m は全列挙できて、全体としての計算量はおおよそ ΣN/m です。 Σ(1/m) ≒ ∫(1/m) dm ≒ log N なので O(N log N) になります。
提出：
この問題を解くには、
1. 単純なケースを分析する (一周ですべてのゴミを回収するときのコストの計算をする)
2. 変数を固定して単純になるか考える (周回数 m を固定してみる)
といった定石を地道に踏んでいけばよかったですね。
感想
難しかった。