TwitterでAHC012について調べている限りだと適当にグリッドの初期解を決めて焼きなましている人が多い印象を見受けられましたが、自分はDPだけで解いたのでその概要を示したいと思います。
seed0の出力
最初の提出の方針
まず、イチゴをX座標の大きさでソートして適当なサイズ M (一番最初は M=15 で行った)に分けます。そのあと、イチゴをY座標の大きさでソート(Y座標が等しいならX座標の大きさ)して、このイチゴを分割することを考えます。
ここで、切り口 i を Y座標の大きさがi番目以下のイチゴとi番目より大きいイチゴを分断する切り口とします。
この分割の際にDPを行います。このDPの状態の持ち方は以下の通りです。
- dp[i]...切り口iで切ったとき、その切り口よりY座標が小さい側だけを見たときの最善のスコアとその最善のスコアを達成する際の現在時点での配列$b$とこの切り口の一個前の切り口のindex
このdpの遷移は一個前の切り口のindexをjとすると、切り口iと切り口jの間に何個イチゴがのっているかを調べればいいです。
イメージとしては以下の図のようです。
イチゴの数は累積和を事前に求めておくことで $O(M)$で求めることができます。
jを全探索するとこのdpは全体で $O(N^2 M)$で求めることができます。
なお、スコア関数は問題のもののままではなく、(最終的には)以下のようになっています。
ll score(vector<int> &B){ if(B[0]>K) return ILL; ll ans=0; for(ll i=1;i<=10;i++){ if(A[i]<=B[i]) continue; ll tmp=(A[i]-B[i])*(A[i]-B[i]+1); tmp*=(ll)(INF); ans+=((i*4-1)*tmp)/A[i]; } return ans; }
$B[i]$ が1増えるごとにスコアが $(4i-1)\times \frac{A[i]-B[i]}{A[i]}$ 減るようになっています。
意図としては同じ個数イチゴがのったケーキが固まらないようにするため、特定の個数イチゴがのったケーキが極端に少なくなることがないようにするためです。
全体としての計算量は $O(N^2 M)$ であるため、TLEにならずに通ります。
本当の最初の実装はスコア関数があまり良くないもの((4i-1)の部分がないもの)でしたが、それでも90Mが出ました。
この方針の改善
直前の切り口を全探索していましたが、 $10M$ 個以上前の切り口を探索することはあまり効率が良くありません。 なぜなら、11個以上イチゴがのったケーキが発生してしまうからです。
よって、jの探索範囲を狭めることでdpの計算量が $O(NM^2)$ へと改善されます。 このことにより、 Mの値をいろいろな値で探索することができます。(最終的には 5~16 を全て調べました)
また、それでも実行時間に余裕があったため、最初のX座標で切り分ける際に等分にするのではなく、真ん中の部分に多めにイチゴがのるようにしたりなど様々な条件でdpをしました。
これらを全て実装したものを提出すると99.5Mが出ますが、コンテスト中の流れが以下のようだったので最終的な結果は99.3Mとなっています。
コンテスト中の流れ
~1:15
上記の方針を思いつき実装し提出する。(90M)
~1:30
M=15だけでなくM=10でも実行し、良い方を出力する。(92M)
~1:40
dpを高速化してMの値を色々変えて一番いいやつを出力する(93M)
~2:10
最初のX座標の分割の仕方を少し変えたものも試すようにする。(94.5M)
~3:00
スコア関数の$(4i-1)$の部分が今までなく、その部分を付け足すとスコアが劇的に良くなることに気がついたので、色々試してみる。(98.8M)
~3:50
X座標の分割方法のパターンを色々変えてみたりする(99M)
~4:00
dpが持つスコアを最後10%はなぜか真のスコアに変えていたので、それを5%にする(99.3M)
コンテスト後
dpが持つスコアを最後まで自作のスコアにする。また、スコア関数に余分な計算があって、正しく計算されていなかったので、それを修正する(99.5M)
感想
焼きなましとかできなくても問題によっては戦えるんだなと感じた。 もしできたとしてもこれは局所解になってるだろうから改善できないだろうけど。 あとMの値の候補を減らしてビームサーチみたいにたくさん状態を持ってdpをしたらスコアが改善されるのかなぁと感じている。
