競技プログラミングの大会 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 を固定してみる)

といった定石を地道に踏んでいけばよかったですね。

感想

難しかった。