AHC031 日記

注意

• ほとんどコンテスト中に書いたもの(一部修正)なので、文体などが終わっています
• いきなり関数名や変数名などが出てくるので、この日記を読むだけでは何を言っているかわからない場合があります
• 寝たかどうかで日付を変えたのでX日目はX日目~X+1日目の午前くらいまで含まれる場合があります(生活習慣？？？)

1日目(3/22)

うお～～～
インタラクティブではなさそう
時系列系(？)か～
外周が使えるのがややこしそう
仕切りを実際に置くわけではなく長方形の端点を出力するのか
前作った仕切りがそのまま使えたら嬉しそう
仕切りの移動は長さに比例してコストがかかるけど区画不足は不足分の面積に比例して(*100もされる)コストがかかるのでうまく仕切りを移動させたほうがよさそう
とりあえず仕切りを移動させるコストを無視して日にちごとに区画不足にならないようにするとこれはほぼAHC001か
AtCoder Heuristic Contest 001 (AHC001) 初心者向け解説 - TERRYのブログ
を読みながら雑に遷移を書いた
う～ん　衝突部分で全体的にずらすみたいなのがうまくいっていなさそう
隙間を埋めると得点アップさせたい
実は左右を結ぶ線とそれを結ぶ縦線だけでどうにかなるとか
意外とどうにかなった(びっくり)
|    |
|----|
|    |
|    |
|----|
|    |
|    |
みたいな感じで横線を最初に決め打てばいい感じになる？(スコアを真面目に計算したくない(カス))
というか初日にmax(A_i,j)をiごとにとっていい感じに配置すればタダで済むじゃん
スコア1が達成可能っぽいseedは3000ケースのうち23ケースあった(seed40←嘘すぎ　seed32だが？？？これを書いたのは誰ですか？？？　とか)　割とある
スコア計算は長方形の四辺を見ればよいのでO(W²+DNW)くらいでできるのか
使ったマスをxorすれば1を数えればよくなるのでbitsetでできそう
横線だけを重ねるの、かなり厳しそう
もしかして分割統治でうまくいく？
縦と横でDPする謎案が生えた　面白そうなので実装
DPしても多少収まらないseedがある　でも制約では収まるとは書いてないから仕方ないのか？
上から貪欲にやってるのは改善の余地がありそう
とりあえずDP+山登りを提出したら28位(絶対50489614点、相対9,321,825,027点)　絶対スコアがみるみる下がって楽しい
でも2~4時間くらいでもっと上位の人がいるので絶対もっといい方法があると思う
雑にmaxを取って動かさないようにしたら18/50ケースで最小値になっていてそんな…という感じに
やっぱり動かさないことが大事っぽい
う～ん　1行で最適な動かさない方法は区間DPでできる…？　無理かも

2日目(3/23)

横線が動くの、かなりコストがかかる感じがする
区間のmaxを取って固定する方針だと、N個の面積の値はD²通りあって区間DP的なことをしようとするとO(D⁴)かかる
いや区間のマージの中心は固定だからD³でできるか？どちらにせよO(D²W²N)のDPは厳しそう
最終的に、基本長方形は動かさずにそのまま使って困ったら長方形を増やしたり減らしたりして対応させたい

3日目(3/24)

昨日なんもせずに寝ちゃった(？) 縦線を最初に固定したら横線を移動する回数が少なくなる？ 縦線の挿入/削除/ずらしと長方形の左上の移動で焼ける？ 詰め込みはAHC025の貪欲(大きい方からやる)が使えそう
なんか今回総体制という感じで面白いな
分割、あんまり山登れん
std::set::merge、要素を移動するのか～～～い　初めて使う関数はよく確かめよう！(一敗)
うお～どうにかbitsetで実装して提出したら22位(絶対24012026点、相対13,450,273,779点)
そういうことなのか～～～　やっぱり動かさないって大事すぎる
昨日までに書いたコード、13/100しかmaxじゃないらしいです　そんな…
貪欲をDPにしたけどあんまり変わらなかった(多少上がった)　多分横を合わせるのは難しいということだと思う
次は幅をいじりたい
すみません、ビンパッキングの貪欲が間違っていました(え？)
とりあえずパッキング問題 | opt100に書いてあったBFDにした　まあまあよさそう(最初の貪欲は何だったんだ…？→これNFDかも)
悪化した　そんな…
このままビンパッキングを頑張ってもよいがそこまで大事ではなさそうなので保留
なんか思ったより時間余るな(解ができないやつもたまにあるが)　う～～～ん

5日目(3/26)

4日目、消滅…(？)
どうにか前作った長方形をできる限り壊したくない
縦の破壊とかも考えたけどその縦線から出る横線が壊れるから微妙か
スコアが「線が重なれば重なるほど良い」から焼きなましで横線の位置をずらすのはスコアがすぐ変わって微妙？
横線の近さをスコアにすればよい？
でも近さ1と近さ0では雲泥の差だからなあ～
あと単純に遷移がわからん　a:bにしている横線をランダムに持ってきてa:bで挿入する？
作った盤面とAを最大マッチング(問題の面積コストを最小化)しないといけない
多分B - 展覧会 (Exhibition)の価値が0、大きさが負？のバージョンなので
JOI 本選 2019 B - 展覧会 (AOJ 0659, 難易度 7) - けんちょんの競プロ精進記録を信じて昇順ソートして近いほうから貪欲でいいはず…
雑山登りを出したらまあまあ上がった　40位(絶対23346119点、相対10,199,430,378点)
自分が昔書いた謎DPの中身を思い出せなくなっていた　危ない…(1日毎に二つに分けてDPして積んでいる)
前の日をコピーする遷移とかはどうだろうか
前後をコピー、かなりいいかもしれん(まだわからないが、seed0で1001点を出していて素晴らしい)
いやこれやっぱり形の維持が重要だわ　とりあえず高速化します
あと幅いじるのも後で入れてみよう
実行時間10倍で焼きなましするとseed1で100000点くらいまで行くらしい　ホント？？？
さすがに嘘でした　スコア計算がバグってた…
というか急にスコアが大きく変わるのであんまり焼きなましに向いてないなこれ　スコアをいじるか？
結構頑張って高速化したけどまだ山登れるやつもあるらしい　そんな(多少嬉しくはある)
！！！　提出したら21位(絶対21773976点、相対15,699,031,060点)！！！　うおおおおおおおおお
謎DPから横線の山登りに繋げられるなら繋げてみたが微妙　時間管理がうまくいってない？
乱数をいじったりしたけどやっぱり普通にスコア計算が遅そう
+-1させる遷移から前後の日の横線に合わせる遷移に変えたら16位(絶対21403191点、相対17,552,957,603点)　よしよしよしよしよし
震えが止まらん　やべ～～～～～　でもあと5日あるんだよな…
う～むこの方針だと頑張っても20G~25G止まりでは…？
あ～なんか真面目に集合を持っておけばどうにかなるかも　線の移動はその線の階層だけ見ればいいし

6日目(3/27)

定数倍があるにしてももう少し回ってもよくない？
あとおさまりきらないやつも山登りさせてみたい
今一回の更新にO(NlogN)くらいかかってるけどseed1はN=36なのに3秒近く回しても8e5回くらいしか回ってないのはなんでだ～～～
ラムダ式のほうが関数より速そう
C++の関数オブジェクトが関数よりどれだけ速いか - でも今日はSRMあるからに関数オブジェクトのほうが速いって書いてあるけどこれは再帰だから？
なんか思ったよりD日全部で固定可能な長方形があるらしい　へ～　実装してみるか…
やりたいこと：

• 無理やり全日で固定できるやつを固定する(実装が大変なことになりそうなのでWとNとAを書き換えてごまかす)→ダメだった　そもそも入りきるかわからないし入りきったとしてもよくなるとは限らない(幅が大きくなってしまうので)
• わざと小さい幅にして山登りに託す

7日目(3/28)

同じ幅の中で並び替えるという近傍を思いついたのでやってみる
かなり良かった　17位(絶対11692752点、相対19,398,314,154点)に浮上…
でもこれを頑張っても25Gくらいにしかならないのでは？という気持ちがある
メモ:最終提出ではassertは切る、rand_int()のsource_locationも切る
変えても絶対改善しない日は改善しないようにしたい
改善する確率が低そうな遷移をなくしたら相対スコア下がった　多分スコアが小さいところで負けてるんだと思う
改善しない日は避けるようにしたら多少上がった
vector<vector<int>>とvector<rectangle>の比較はvector<rectangle>の方が速いらしい　へ～
適当に破壊して貪欲に埋めるみたいな遷移が必要かもしれん
なんかsortからinsertに遷移を直したのが消滅しとる　まあいいか…
あ～　本当は焼きなましをしたいが…
横線の移動、線が消える+線が増えるの二つの差ができていて微妙　本当は線を増やす→線を消すみたいなことをしたいがどうやってスコア計算すればいいのかわからん
風呂、考察がはかどる(風呂で考察したみたいなのを読んだ気がする)
まず縦を焼いてから横にいくといいかも
あとfake_score_diffはたぶん差分計算がもっとできる(変えた横線だけ見ればよい)

8日目(3/29)

cout << hoge << '\n';の後にassertを書いたのでcoutされないというバグをやった
ずっと困ってたバグ、枝刈りでreturnし忘れていた　アホ
なんかmodify_aとmodify_bだけのほうがcとdを追加するよりいいが？なんだこれ
ミスってSolver2の方いじってREしちゃった
Solver2、最後に時間があったらいじりたい
うお～縦の山登りを入れたら12位(相対22,678,161,357点)
しかもこれミスってwidthの大きさが1で済むやつをbreakし損ねているのでもうちょっと上がる
あと縦の遷移は雑だし評価関数ももう少しいいやつがありそう
本当は縦と横を同時に焼きたいが…
改善ポイント：

• 縦の遷移
  
• 埋めるときの貪欲
  

本当は途中で縦線を外すみたいなことがしたいが…(さすがにそれで改善するケースはたいしてないか？)
バグを直して11位(絶対11438329点、相対24,318,699,958点)
幅を列として持ってると思ってたけどこれ集合として持ってたわ　？
多少真面目な貪欲にしたら6位(絶対11128720点、相対28,654,208,754点)　すげ～
今の方針だと多分40G越えられん(涙)
でもこれで20G前後からいきなり30Gくらいまで行った人が何してるか分かった(同じ方針かは分からないが…)
縦でくっつける遷移も増やしたけど(たぶん)参加者のhighestを更新したが相対スコアは落ちるというどうすればいいのかわからない結果に
これ順位表のsnap大事かもしれん　今は6位、絶対11114353点、相対28,692,093,009点
highestを更新しているということはこの方針でも闘えるということなのかな…
上位の人が投げてくれたおかげでちょっと相対スコア上がってる　ありがとうございます

9日目(3/30)

ぐわ～　さすがに横棒をいじるところで縦棒を動かしても伸びない(縦棒を動かすだけではスコアは改善しないので当然)
破壊再構築を書けということか…　こんなことならちゃんとAを参照で受け取るコードにしておけばよかったぜ
いや～でも全ての日で再構築するのは厳しそう　日ごとに再構築…？
でもそうするとスコア計算がめんどくせ～～～
いやさすがに色んなものを壊しすぎなので改善しない気がする　保留で…
さらに何本か横線を端から端まで引けば固定できる場所が増えて嬉しい？
いやでもwidthの数が増えるだけか？でも固定できる幅が大きくなるのは嬉しいかも…？
いやでもその分幅は大きくなるか　う～ん

10日目(3/31)

寝て起きたら順位上がってた　精神状態に良い(？)
適当に山登りをやめるのを100回解を更新しなかったらにしたけどこれがかなりいい値だったっぽい(多少伸びてびっくりした)
微妙な遷移をなくして+1/-1する遷移を+p/-pにしたら6位(絶対10980137点、相対29,575,755,727点)に再浮上
手元の評価、logの総和でいいのかよくわからん
横棒の山登りを焼きなましにしたら5位(絶対10935035点、相対32,002,220,213点)になった　いいね
焼きなましの温度が壊れていたので修正したら4位(絶対10946529点、相対32,535,663,873点) OK
温度いじっただけで結構伸びるな　もうちょっと頑張れるかも
start_temp=50→絶対10935035点、相対32,535,663,873点
start_temp=60→絶対10931413点、相対32,191,780,353点
start_temp=40→絶対10925410点、相対32,573,956,492点
start_temp=30→絶対10925410点、相対32,133,430,262点
もうネタ切れだ～となりながらなんだかんだで3Gくらい上げていて我ながらえらい
start_temp=45→絶対10931709点、相対31,018,474,409点(上位陣が提出したので相対スコアが変わってしまい困った)
とりあえずstart_tempは40にしておこう
ここにきて順位表がめっちゃ動く　ひえ～～～
ハイパラ調整をします　optuna頼んだ！

11日目(4/1)

optunaで調整したやつを投げたら下がった　悲しい(log評価が良くなかったのでは…)
山登りの評価関数だけ戻して出したら上がった　optunaありがとう…(調整するハイパラをミスった感がある)
順位表動きすぎだろ　勘弁してくれ～～～
Solver2に書き足すかSolverをコピペして書き直すかどっちがいいんだ　Solver2に書き足すほうが楽か…
え？？？？？　push_widthであるべきところがpush_width_aになってた　？？？？？
でもこのバグ直したら相対スコアは下がったな　そんな
ちょっと山登りをいじって6位(絶対10626353点、相対32,410,153,617点)　ひ～～～
Solver2を直したけど0.3Gくらいしか上がらなかった　悲しい
よく見たら山登りの遷移がバグってる　おいおい
バグ直したら相対スコア下がった　はい
上位陣の提出により1Gくらい削られた　許してくれ～
コードを見直したらハイパラが間違ってた　怖
メモ：最終提出は絶対スコアが6804134のやつを出す

結果

暫定8位、最終9位で初赤perf&入黄　やった～～～