第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）

atcoder.jp

暫定: 40,333,000点、60位。

システムテスト: 1,602,640,025点、61位。

ソースコード。

github.com

スクショ。

動画。

おおまかな方針

一毛作（1個の区画に植えて収穫するのは1回だけ）なら、話は簡単。距離が近い順にDが小さいものを並べ、最初に全て植えれば良い。空間方向に領域を区切り、その個々の領域を時分割して、作物を植える。

全域木を作る。

この中から区画（図中の赤丸）を選び、そこを根とする部分木（図中のピンク丸）を1個の領域にする。

各領域ごとに期間をどのように区切るかを焼きなます。

詳細と時系列

とりあえず、答えをそのまま焼きなましてみる。答えの一部を変更して、全部シミュレーションして、スコアを出す。

2.6M点。満点は50M点。イテレーションも全然回らないので、まあ、こんなもんだろ。これでも100倍くらい時間を掛ければ、数十M点にはなっていた覚え。

これ以上どうして良いのか分からず。週末まで放置。

途中順位表だけ眺めていると、40M点で上位にいけるっぽい。40M点って思ったより低い。50M点が満点だから80%　全期間全区画に作物があると満点になる。ということは、区画のうち10%くらいは全く作物を植えなくても良いのか。

方針に書いたようなことをしてみる。ただし、焼きなましは無しで、期間の区切りは乱数は適当に。これで34M点。意外と点数取れるな。

区切りを焼きなまして38.3M点。

作物を区画に割り振るとき、点数の高い（収穫までの期間が長い）作物から順に、なるべくぴったりな区画に割り振っていくのが良さそう。でも、焼きなましで一部の領域の一部の期間を変えたときに全部計算し直すと重いので、更新したところに合う作物を選ぶようにしていた。定期的に全部作物を割り当て直すようにした。

39.0M点。あまり変わらんな。

部分木を決めるときに、根から順番に見ていき、部分木のサイズが閾値を下回ったらそこを領域として切り出すようにしていた。

部分木のサイズだけで判断するのは良くない。左も右も部分木のサイズは同じだとして、左は上下をそれぞれ別の領域にしたほうが良い。右は、この枝の先で領域に分割すると通路の分が無駄なので、根の部分で全体を1個の領域にしてしまったほうが良い。

領域の広さと、1区画あたりに得られたスコアを出してみるとこうなった。

けっこう上手く見積もれそう。この見積もりを使って木DPで、どこの部分木を1個の領域にするのか決めるようにした。

39.5M点。

この計算は軽いので、木を作るときに4方向をどの順番に見るのかを変えて、何度か作り直すようにした。適当に10ケースくらい動かしていても差は分からんが……まあ、やって損は無いだろ。

40M点を目指したい。あと何かできることあるかな……。で、通路に何も植えないのは無駄なことに気が付いた。通路の先に要がないタイミングでは植えられる。植えるようにした。

40.3M点。

40M点を超えたので満足。