これって空きが多めのケースだとコスト0が達成できてしまう？ そういう誰かがコスト0にしてるケースは自分がそうするのに失敗するとスコアほぼ0になってしまうから外せない。ここはしっかりやらないといけない
初日の壁構築コストが0なのをうまく使うべきのような気がする。
最初の解として、壁の移動は行わずに幅Wの部屋だけを作る方法をやってみた。 横に等間隔の線を引いて、その位置の移動で山登る。
サンプルに比べて4倍程度にしかなっていない。意外と悪いな。コスト0のケースは無し。そんな簡単じゃないか。
いや、初期解を等間隔にするのが全然だめで、i番目の部屋の平均広さに比例する広さにしたらだいぶ良くなった。 サンプルに比べてスコア20倍くらい。コスト0が1000ケース中5個ある。
逆に幅はW固定で壁を動かしまくる解法を考えてみると、面積コストは0にできるとして、壁コストの上界が D*(N-1)*W*2 くらいになるから上の部屋完全固定解よりはいいのか。
さらに使う部屋の順番を小さいものから固定とすると、前の日の情報が与えられればDPで1日分だけの最小コストは出せそう。 => ビームサーチへの発展もあり
あと幅をWじゃなくて縦にいくつかに割って複数カラムにするという発展もある。
使う部屋の順番は、Nが小さかったら固定にしなくてもビットDPで最適解を出せる。
i番目の部屋のD日にわたるmax のN個の和をとってみると、1000 * 1000以下なのは1000ケース中14個しかなかった。コスト0達成可能なのは少なかった。なるほど
DP/ビームサーチ的に決めていく場合、0日目をどうやって決めるのかという問題があって、
D日進めたあと逆向きにまたDP/ビームサーチするのを反復するといいかも。
逆に幅はW固定で壁を動かしまくる解法を考えてみると、面積コストは0にできるとして、
実際どれくらい0にできるのか？ 確かめてみる
部屋サイズをWの倍数に切り上げた和がD日全部 W * W 以下なのは、1000ケース中757個。なるほどそこまで多くはない。
250の倍数に切り上げると 936/1000, 100の倍数に切り上げると 993/1000
まずは一方向でDPするのを書いた。かなり望みがない部分の無駄な計算してそうだけどとりあえず雑に。
わりかし良くなって見れる程度のスコアになった。ただ空きが小さいケースでは、昨日書いた幅W固定で壁を動かしまくる解法のコスト上界 D*(N-1)*W*2 より10倍くらい悪くて要調査。
面積の制約がだいぶきついんかなあ？
あと簡単ケースでコスト1が達成できるケースで取れてない。別途それ用の解法を作るべきか？
現状
seed:0000 score:4988 pena_area:0 pena_wall:4987
seed:0001 score:3058701 pena_area:1624700 pena_wall:1434000
seed:0002 score:456701 pena_area:50700 pena_wall:406000
seed:0003 score:87224 pena_area:0 pena_wall:87223
seed:0004 score:437187 pena_area:248900 pena_wall:188286
seed:0005 score:93785 pena_area:20400 pena_wall:73384
seed:0006 score:26729 pena_area:300 pena_wall:26428
seed:0007 score:31059 pena_area:0 pena_wall:31058
seed:0008 score:176785 pena_area:0 pena_wall:176784
seed:0009 score:6928 pena_area:0 pena_wall:6927
D日進めたあと逆向きにまたDP/ビームサーチするのを反復するといいかも。
逆向きというより、中間の日は前後の状態両方を見て設定し直すのを繰り返すのがよさそう。実装は大変そうだが…
とりあえず最後に各部屋をサイズ順に割り当て直すのをやっておく。
1%くらいは意味あったけどこれ本体のアルゴリズムが甘いからだよねえ
seed:0000 score: 4287 pena_area: 0 pena_wall: 4286
seed:0001 score: 3058701 pena_area: 1624700 pena_wall: 1434000
seed:0002 score: 456701 pena_area: 50700 pena_wall: 406000
seed:0003 score: 87224 pena_area: 0 pena_wall: 87223
seed:0004 score: 421469 pena_area: 244500 pena_wall: 176968
seed:0005 score: 78385 pena_area: 5000 pena_wall: 73384
seed:0006 score: 26729 pena_area: 300 pena_wall: 26428
seed:0007 score: 28937 pena_area: 0 pena_wall: 28936
seed:0008 score: 176785 pena_area: 0 pena_wall: 176784
seed:0009 score: 6928 pena_area: 0 pena_wall: 6927
後ろ向きに反復するのすぐ書けそうだったので書いた。
seed:0000 score: 2975 pena_area: 0 pena_wall: 2974
seed:0001 score: 2492901 pena_area: 1070900 pena_wall: 1422000
seed:0002 score: 404001 pena_area: 0 pena_wall: 404000
seed:0003 score: 85167 pena_area: 0 pena_wall: 85166
seed:0004 score: 264917 pena_area: 86700 pena_wall: 178216
seed:0005 score: 88315 pena_area: 0 pena_wall: 88314
seed:0006 score: 16685 pena_area: 0 pena_wall: 16684
seed:0007 score: 30137 pena_area: 0 pena_wall: 30136
seed:0008 score: 179697 pena_area: 0 pena_wall: 179696
seed:0009 score: 4371 pena_area: 0 pena_wall: 4370
まあこんなもんかというところ。悪くなってるのもあるのは遅くなった分だろう。
完全解狙うのをとりあえず作っておく。
完全解じゃなく若干面積がはみ出る場合でも、壁動かさない解を初期解として作っておくのはありだろう。
＝> ありだろうと書いたが全然ありじゃなかった。壁固定は完全解用にしかならんわ
まあでも1000ケース中完全解が可能な14ケースで全部スコア1を達成できてるのでこれはこれでよかろう。
逆に壁の移動コストを無視して面積だけできるだけ合わせるようにした解を作ってみたら、空きが少ないケースでこれまでの解答よりもだいぶ良くなった。
壁を動かしまくる解法のコスト上界 D*(N-1)*W*2 の3~4割のスコアになっていそう。
偶然壁が重なって移動コストにならない分を考慮した厳密なスコア計算はしてないが…
こんな雑な解答でこれだけ出るのならまだまだ伸ばさないといけないということだよねえ
現状（スコアは正確でなく真のスコアよりpena_wallが若干悪い）
seed:0000 score: 2210 pena_area: 0 pena_wall: 2209
seed:0001 score: 472074 pena_area: 0 pena_wall: 472073
seed:0002 score: 263698 pena_area: 0 pena_wall: 263697
seed:0003 score: 92632 pena_area: 6400 pena_wall: 86231
seed:0004 score: 160450 pena_area: 0 pena_wall: 160449
seed:0005 score: 56586 pena_area: 0 pena_wall: 56585
seed:0006 score: 14452 pena_area: 0 pena_wall: 14451
seed:0007 score: 22592 pena_area: 0 pena_wall: 22591
seed:0008 score: 175285 pena_area: 300 pena_wall: 174984
seed:0009 score: 4364 pena_area: 0 pena_wall: 4363
完全にD日を独立にやるのではなく、縦の壁の位置は固定にするのも試してみた。 これだけでも、空きが多いところ以外で全体的に2割くらい良くなった。これだけで良くなるということはまだまだ伸ばす余地がたくさんあるということだ
seed:0000 score: 2211 pena_area: 0 pena_wall: 2210
seed:0001 score: 242974 pena_area: 0 pena_wall: 242973
seed:0002 score: 133339 pena_area: 0 pena_wall: 133338
seed:0003 score: 97026 pena_area: 0 pena_wall: 97025
seed:0004 score: 67431 pena_area: 0 pena_wall: 67430
seed:0005 score: 62871 pena_area: 0 pena_wall: 62870
seed:0006 score: 14452 pena_area: 0 pena_wall: 14451
seed:0007 score: 23009 pena_area: 0 pena_wall: 23008
seed:0008 score: 94079 pena_area: 0 pena_wall: 94078
seed:0009 score: 4371 pena_area: 0 pena_wall: 4370
いやーでもDPで作った解より強くなるのけっこう不思議かもしれない。 今のDP解は1つ目の部屋から順番に使っているのが相当厳しい制約になってるんかな。
これまでの、縦の壁は全日で統一して固定した解をベースに、各カラム間で割り当たってる要求を入れ替えてDPで前後の日の横の壁の位置を見つつ最適化する、をやる
縦の壁の位置をずらす遷移も加えていいかもしれない。
実装上は、壁の位置をずらすというよりは1つのカラムの幅を1減らして他の1つのカラムの幅を1増やす、となる
よくある手法として、計算時間を減らすために最初はW=1000ではなく4刻みとか10刻みにして荒くやっておくのはありか？
まあ高速化の話なのでやるとしても最後に
とりえあず縦の線をずらすのだけやった。無意味ではない程度には改善した。
横の線を動かして最適化していくやつをやる
カラム間で部屋の移動・交換はなしでとりあえず上から使う順序をランダムに並び替えてDPするやつ。
これだけでもまあまあ良くはなる。
seed:0000 score: 1601 pena_area: 0 pena_wall: 1600
seed:0001 score: 148229 pena_area: 200 pena_wall: 148028
seed:0002 score: 80840 pena_area: 100 pena_wall: 80739
seed:0003 score: 62826 pena_area: 6300 pena_wall: 56525
seed:0004 score: 44635 pena_area: 100 pena_wall: 44534
seed:0005 score: 45929 pena_area: 0 pena_wall: 45928
seed:0006 score: 10814 pena_area: 0 pena_wall: 10813
seed:0007 score: 19086 pena_area: 0 pena_wall: 19085
seed:0008 score: 61959 pena_area: 0 pena_wall: 61958
seed:0009 score: 3055 pena_area: 0 pena_wall: 3054
面積ペナルティ=0 に固執せずにスコアの最適化ができていそうでいい感じ。
提出した。 12,088,704,110 58位
まあサンプルとの比較だとそんなもんだよねえ
2カラム間で部屋の移動や交換をする遷移も入れたが5%くらいしか変わらん
時間2s->10sにすると1,2割程度は伸びるがその程度ではなあ
カラムの数の上限を増やしたら主にNが大きいところで良くなった。あとで細かく調整
seed:0000 score: 1026 pena_area: 0 pena_wall: 1025 col:3
seed:0001 score: 135787 pena_area: 0 pena_wall: 135786 col:8
seed:0002 score: 67655 pena_area: 0 pena_wall: 67654 col:5
seed:0003 score: 29859 pena_area: 0 pena_wall: 29858 col:13
seed:0004 score: 22647 pena_area: 500 pena_wall: 22146 col:12
seed:0005 score: 54946 pena_area: 0 pena_wall: 54945 col:5
seed:0006 score: 3318 pena_area: 0 pena_wall: 3317 col:16
seed:0007 score: 15668 pena_area: 0 pena_wall: 15667 col:6
seed:0008 score: 51818 pena_area: 0 pena_wall: 51817 col:6
seed:0009 score: 2853 pena_area: 0 pena_wall: 2852 col:4
初期解の詰め方を改善（今の高さが一番低いところ->今の部屋を置いた後に高さが一番低くなるところ）したら1割以上良くなった… これだけでそんな伸びしろあるのか
カラムのマージ・分割の遷移をやるべきか？ かなり重たい遷移になるが
DP解やめてカラム固定解のみでやってみたらそっちの方が良かったわ。だいぶ実装無駄になってしまった
面積ペナルティのみを考慮する解を1日ごとに逐次改善可能にするの、やるだけなのでやる
やった。空きが少ないところで6%くらいよくなった。全体の影響は1%くらい。まあはい
ここで一度提出 12,049,481,782-> 18,016,976,270 37位 ほぼローカル評価から想定できるくらい
1カラム分をDPで更新するところでDP表の中にvalidな値が入っている部分がかなり少ないから配列全部イテレートするのではなく値が入っている位置を持つことで高速化する
=> 倍くらいは速くなった？ スコアは5%くらい上昇。
うーんまだまだ実行時間伸ばすとめちゃくちゃ上がるなあ
このあたりでもう一度提出 20,673,634,961 28位 提出前のスコア取り忘れてたけど前回の提出時からほとんど変わってない
seed:0000 score: 708 pena_area: 0 pena_wall: 707 col:6
seed:0001 score: 111636 pena_area: 2500 pena_wall: 109135 col:9
seed:0002 score: 61071 pena_area: 0 pena_wall: 61070 col:5
seed:0003 score: 20741 pena_area: 0 pena_wall: 20740 col:14
seed:0004 score: 18329 pena_area: 0 pena_wall: 18328 col:13
seed:0005 score: 32040 pena_area: 0 pena_wall: 32039 col:11
seed:0006 score: 2504 pena_area: 0 pena_wall: 2503 col:18
seed:0007 score: 7630 pena_area: 0 pena_wall: 7629 col:13
seed:0008 score: 40584 pena_area: 0 pena_wall: 40583 col:7
seed:0009 score: 2264 pena_area: 0 pena_wall: 2263 col:6
遷移のうちかなりの割合が全然見込みない結果だから上手く絞りたいんよなあ
1日分の全カラムを細いビームサーチで改善する？
高さWまで使い切らない方が良いケースがそこそこはある。ちょっと難しいが対応してみる
一応1%くらいよくはなったが、若干スコアがテスターとずれるケースがあって不穏 まあ若干ずれてはいても数百ケースはACしてるしいいか…
遷移のスコア計算の前にちょっと枝刈りいれたらだいぶ速くなった。
ここで提出 20,131,375,927 -> 21,419,927,491 27位 ちょっと相性悪め 絶対スコア悪くなってるし
初期解を作るところでカラム数をベストの近辺だけ調べるようにしたら空きが多いところで5%以上良くなった
ここまだ掘る価値ありそう
seed:0000 score: 662 pena_area: 0 pena_wall: 661 col:7
seed:0001 score: 90814 pena_area: 100 pena_wall: 90713 col:10
seed:0002 score: 53957 pena_area: 0 pena_wall: 53956 col:5
seed:0003 score: 18403 pena_area: 300 pena_wall: 18102 col:13
seed:0004 score: 13976 pena_area: 0 pena_wall: 13975 col:14
seed:0005 score: 24595 pena_area: 0 pena_wall: 24594 col:11
seed:0006 score: 2166 pena_area: 0 pena_wall: 2165 col:19
seed:0007 score: 5389 pena_area: 0 pena_wall: 5388 col:14
seed:0008 score: 31889 pena_area: 0 pena_wall: 31888 col:7
seed:0009 score: 1972 pena_area: 0 pena_wall: 1971 col:7
提出 21,256,376,575 -> 21,808,587,682 26位 あんまり変わってない 空きが多いところは大幅に負けていそう
初期解作るときの評価に面積の余裕の多さも入れてみる
=> 悪化
空き少ないところでの面積ペナ最小化解もどうせカラムに分ける形にするのだから縦の線が前後の日と合っているかを考慮に入れる
=> 思った以上に上がった
提出 21,798,635,835 -> 21,718,228,506 26位 上がったように見えたのはインスタンスガチャかも？
たくさんログ出してるとわりと結果に影響する。気をつけないと
1日分の全カラムを細いビームサーチで改善する？
やろうとしたが、N個の部屋を複数カラムに渡って良い感じにちょうど使い切るのが難しくてものにならなかった
最後の詰めでパラメタ調整しようとしたが全然効かんかった…