pretest 116位、得点は56719693。
序盤は貪欲をしました。終盤はある列に注目したときの横の長さを固定したときの縦の長さを最小化するようなDPを行いました。
1日目
長期AHCは緑パフォしか出したことなかったので出るつもりがなかったのだが、就活生枠の賞金が出るらしく、とりあえずやってみることに。
21:30くらいに問題を開いてビジュアライザの仕様以外をじっくり読む。全体の縦の長さと各列あたりの横の長さを固定。貪欲にLで埋めていく。
縦の長さtate, 横の長さyokoを乱択で決める。
i=0,1,2...,の順に以下を行う。
w[i]とh[i]のうち、yoko以下で大きい方を選択してLで積む。列の長さがtateを超えるなら次の列に移る。列の個数×yoko+tateが最小のものを出力。
23:30に提出、1位になる。最終150位相当くらい？
謎にフィボナッチ探索やってるのは無視してもらいたい。
2～3日目
上位狙えるならさすがにガチってもいいな？となり、入力の生成方法やビジュアライザの使い方を読んだ。なおビームサーチや焼きなましは成功した試しがないので引き続き貪欲方針を固めていく。
ジャッジそのもの(操作を与えたら全体の縦と横の長さを返す)を作れたらビジュアライザもアルゴリズムの幅も広がるから、ということで作った。
7日目～最終日
研究が忙しく、なにもせず。80位くらいに落ちていた。
DPをやることにした。初日同様、縦と横を固定。dp[i] := i個目まで埋めたときに縦の長さの最小値。おさまった分はUで埋めて、あふれた分は貪欲にLで埋めた(その後ここもDP化した)。
DPの遷移はk個先まで見るなら回転するかどうかの2k通りを探索する。または、ソートしてmaxになっているところを回転するのを貪欲にやっても同じ結果が得られることに気づき、これも加えた。ただし後者は多項式時間とはいってもO(N3)とかになっててあまりやりたくなかったし、実際そこまで精度の改善はなかった。
DPを取り入れることで現在の順位に至る。あとはパラメタ調整を適当にやって終わり。
感想
結局、逐次入力でもらう結果を使うことはあまりしなかったな…。ICPC引退後に時間できたらちゃんと勉強してやりたいね…。でも長期緑パフォしか出したことなかったので青上位パフォだせたのはだいぶ成長。あまり時間とれなかったわりには1400行以上書いてて、期間中バグらせることも一切なかったので、実装力の向上を感じた点で、出てよかったと思いました。ありがとうございました。
