85,651,452点で暫定200位。
暫定の表示上順位で景品くれませんかね?! だめですかそうですか。
(追記)最終順位は197位でした。微増。
(追追記)青パフォを死守し、レートも青に近づいてきました。
概要
今回はだいたいこんな感じでやってました。
推移
49766 (初提出)
初手(8, 8)に置いて放置。
7524306 (最大効率ではない貪欲)
とりあえず1台を、その時点で最大価値を持つ野菜に移動させるだけの嘘貪欲。
何が嘘かはほぼほぼ自明だと思いますが、今日消える99と明日消える100があったとき100を先に取ると99は取れなくなっちゃうというあれです。
22149879 (十字)
いよいよ複数台設置に取り組みます。どう置いていいか皆目検討もつきませんでしたが、設置した機械と隣接できる面が多いほうが得だろうと考えて、とりあえず十字に場所決め打ちで置くことにします。
その後、不具合を修正するなどして3千万点台に乗りました。
42834843 (十字をずらしていく)
場所決め打ちだけではあれなので、設置場所のx座標とy座標を独立してずらしていくことをしました。
45388468 (十字をずらしていく2)
さらにバリエーションを増やすため、縦に並べる方は横に並べる位置の上下で独立してx座標を決めるということをしました。わりと無駄なあがきっぽいです。
68590130 (移動位置の最適化)
固定設置位置のロジックはとりあえずそのままにして、配置位置を探索するロジックで点数をちゃんと計算するようにして、各盤面で最大スコアが出るものを選択するようにしました。(それまでは野菜単体の価値しか見ていなかった)
ちゃんと計算をするようになったので当然スコアは伸びたのですが、BFSで愚直にO(N4)かけたので計算量が不足するようになってしまいました。
ここから不具合を修正するなどして7千万点台に乗りました。
77433417 (Union-Findによる高速化)
さすがに毎回O(N4)かけて点数計算していたのでは時間がいくらあっても足りないため、Union-Findで連結状態を持っておいてその結果を使えるようにしました。
それでも、せいぜい200回前後しか回すことができず、どうすんだこれ?ってなってました。
ここからなんか不具合を修正したり、clock()を使ってできるだけギリギリまで攻められるようにして、なんとか8千万点台に乗せました。
ここまでやって、気づけば最終日に突入です。
85651452 (繋ぐことを最優先、ランダム要素)
ある程度スコアが出た時点で、そこからの山登りとか焼きなまし的なことをすることを想定していたのですが、とにかく時間計算量が足りないのでいかんともしがたい状況。
ここで改めて考え直して、配置位置を事前に決め打ってもいつ連結状態になるのかが運任せで効率が悪そうだと思い、初期に配置した位置から徐々に手足を伸ばすようなロジックに切り替えます。
伸ばしすぎてもだめなので、購入する機械の上限は40前後でランダムに決めて、購入できるスコアになったら買う買わないに多少のランダム要素をくわえつつ設置していくという方針にしました。
まとめ
なんかこう蛇のようにくねくねと動かしてあげたかったのですが、全然いい実装が思いつかず、場所固定からランダム配置という最悪な逃げ方をしてしまった気がします。
困った時のランダム頼みをやめないとだめですね・・・。
あと11日が休日出勤だったのがとても痛かったですが、これはまあ仕方なし。