こんにちは。競技プログラミングをしているssaattooと申します。第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）に参加して 44位でした。
反省、または誰かの為になることを期待して参加記録を残します。
問題概要
水路が通った正方形の圃場が与えられるので、土地の利用率が最大となるような栽培計画を立ててください。作物の植え付け時期は早めても良いが、収穫時期は固定です。植え付けと収穫には農機が必要です。農機は水路と作物を跨げません。
解法
大まかな解法は以下の通りです。
- 圃場全体に張り巡らされた道を作る。
- 道以外の部分をグループに分割する。各グループは必ず道に接するようにする。
- 入口から遠いグループから作物を植えていく。同じグループで栽培するのはdが同じ作物に限定する。
- その他の工夫（初ターンは全て植えきる。終盤はグループを無視する。道も植えられそうなら植える）
- 1-4を乱数でブラして時間いっぱい繰り返す。
これで82%程度の点を得られます。
1-3についてもう少し詳しく書きます。
道作成パート
まず、道は作物を栽培できる期間が短いため、道を大きくすることはスコアの減少を招きます。一方で道を大きくすると、2で作成するグループのサイズが小さくなるため道以外の利用効率が良くなります。
このトレードオフ関係のもとで、道から最も遠い点との距離がx(5-10)以下となるように道を作成しました。作成アルゴリズムは以下の通りです。
- 入口を道とする。
- 道から最も遠い道でない点をダイクストラで求める（bfsでなくダイクストラを用いているのは、乱数を加えたり曲がることにコストを与えたりしているから）。
- 距離がx以下なら終了。
- 最短経路の内、遠いほうからx個以外の点を道に追加する。
- 2-4を繰り返す。
グループ分けパート
道に接している道以外の点をそれぞれグループの代表とします。グループサイズが小さい順に、周囲のどのグループにも属していない点を取り込んでいきます。
このグループ割り当てのスコアをsum(グループサイズの２乗)としました。グループのサイズが均等な方が土地の利用効率が良くなると考えたからです。
作物決定パート
各ターン、入口から遠いグループから栽培する作物を決定していきます。
あるグループに栽培する作物は全て同じdであると制限しているので、dを決定したときの利用率は計算可能です。そこでターンtにあるdを置いたときの評価値をとして、最もよいdを植えました。
日記
メモなので絶対に見ないでください。
目標
rustを使う。橙パフォ。よい立ち回りをする。問題の性質をよく考える。安易に焼きなましに走らない。散歩、睡眠、お風呂などのぼーっとする時間を確保する。最初の２日で案をすべて実装する。スタートダッシュする。
コンテスト１日目
問題を読んだ。アスプローバだから固い複雑なものだと思っていたら面白そうな問題だ。得意そうでやる気がでる。
自分より小さいDか空マスを通って入口に到達可能なら合法。それを使うのが素直な貪欲かな。空マスが到達不可能になる置き方は必ずしも無駄ではないと思う。
ビームサーチについて。単純に考えると時間の軸があるので有効そう。
焼きなましについて。各作物をマスに割り当てたときの最もよいオンオフ（栽培するかしないか）や、合法な状態を保ったままの遷移が決定できれば焼きなましを実装できると思う。解空間をなめらかにする必要がある。
時間軸を気にするならばビームサーチが有効そうだけど、T=100なのでahc013のようにトップは焼きなましの方を採用しそう。
とりあえず乱択をする。1割ちょっと。とりあえず次はビームに直してみる。
幅1000のビムサを試してみたら、めっちゃ時間かかって乱択ほぼ変わらないくらい。
takumiさんが早い段階で上位にいる。rhooさんも。
lowlink試してみるか。lowlinkで2割くらい。
置くものをsが10ターン以内のもののみにしたら点数が倍くらいになり4割。隣接した置かれたもののdは近いほうがいいのだろうか。これはあまり関係なかった。
各ターンにおいて、dの降順においていったらかなり伸びて６割。
入口から遠い順に探していくとぎちぎちに詰められることを発見したけど、なんかバグっているのか空白が目立つ箇所がある。
コンテスト２日目
遠くから詰めていくのがバグったままなので、あとでやる。一気に増えたり、全く置かなかったりしてる。
乱択で詰めていくと、農道のようなほぼ栽培しないマスができてそれが80~100マスぐらい占める。他のところを完全に利用できても８割くらいしか取れない？スコアは土地の利用率と同じだよね？他のところは8割くらい。
ダイクストラで合法判定していたのをdials alogrithmに変更で微高速化。時間100倍にしても伸びないから高速化は意味ないけど、ビームか焼くならもっと高速な判定が必要っぽい。
そもそもダイクストラみたいに全体を見る必要がなく、置くものの周囲とその点が関節点であるかどうかだけで判定できることに気が付いた。10倍以上高速化した。たぶんlowlinkがボトルネック。
幅1000、置いたものの生スコアで評価するrhoo式ビームを実装。めっちゃ遅いけど66％まで伸びた。強いかもしれないけど、もう少し乱択でいい貪欲を探す必要がありそう。
致命的なバグがあったことを発見し修正。遠くから詰めていく貪欲で65%、幅100のビムサで７割乗った。普通のも7割。
lowlinkの差分計算がわからないので、ダイコネかundo機能つきunionfindを実装してみるか。
置くものをs==turnのもののみにしたら伸びて73%。遠い順に置くやつが決定的なので爆速で74%。距離に乱数を足すみたいのでブラして75.8%。
置くところは遠いところではなく、差が小さいところの方がいいのではないかとふと思う。その通りで 76.7%に伸びた。
提出。385で15位。手元では76.9%。サンプルが大きく偏っていることはないし、80%超えるまでは提出を控えよう。
明日は評価値が高いものを高確率で選ぶようなものにしてみる
コンテスト３日目
関節点を特定の条件で差分計算できるようにした。２倍くらい高速化された気がする。rustのパフォーマンスプロファイラの使い方がわからないからどこがボトルネックか調べられない。
あるターンに置くものを、貪欲を初期解とする置く個数を最大化させる焼きなましで変化させることはできないか。遷移はそのターンに置けるものを削除、置く、移動、swapなど。焼きなましやってみたけど微妙だった。
各ターンで何回か試して最も置ける置き方をするのも微妙。
cropをdの降順から調べていたのを、1000秒焼いてみる。ほんのわずかに伸びる。
d-sが小さいやつは近くに置いた方がいいよな。
今はs=turnのもののみを見てそのターンにおけるだけ置いているけど、数ターン後まで見て最大化したい。特に最初数ターンはすべて置ける空間があるので、dの大きさ順に並ぶようにしたい。
三圃式農業みたいにぐるぐるさせるやつ微妙だった。
コンテスト４日目
距離を空白マスでのbfsにしたら少し伸びた。これ初期値のみ乱数であとはそのままだけど、初ターンの置き方によってかなりムラがある。
最初数ターンはトヨタ決勝のように置くとよいのでは。小さいやつを手前に大きい奴を奥に置く。dがこれくらいのときに距離がこのくらいがいいという配列を用意しておいて、それをもとに各マスの評価をする。近すぎるとあとに置くのが大変なので、それより近いとペナルティは多めにする。
最初５ターンはすべて埋めきるような別の埋め方にする。これが効いて78.2%。５ターンのではなく一つでも失敗するまでにターンを変更する方がいいと思う。した。
最初のターン以外は１つのターンしか見ない貪欲だけど、数ターン先まで見て良いように置きたい。１ターン先まで読むやつ遅いけど78.5くらいまで行く。
コンテスト５日目
今までturn==sの時にしか置いていなかった。とりあえず最初のターンだけターン無視しておいたら78.8%。次ターンのものを考慮するようにしたら20倍くらい遅くなったけど微増。
トップは87%とっているけどどうやっているんだ。
自分のd以下のものを通って空白に到達可能なら合法としていたのを、同じdのみにしたらめっちゃ上がって79.7%。
最初の距離に乱数を加えたのを沢山試すことで時間を使っているけど、もっといい時間の使いかたはないものか。距離への乱数を山登りにするとか。
コンテスト６日目
木を作って葉に置くのを試してみたけど、たいして早くならなかった。
後ろのターンから考えることはできないか？後ろから考えると、置いた時点で点数が評価できるのでビーム向きか？
道以外のところが９割以上になっていて改善がむずいので、道の部分を５割くらいまで上げたい。
入力生成パラのdごとに調整？幅が大きいときは９割くらいでるのか
コンテスト７日目
とりあえず提出。39.95で46位。optunaでパラメータ調整してみたけどたいして意味なさそう。
上位との違いはいいドンよくを見逃しているか、時間の使い方が下手なのか。逐次改善はできないのか。
あるターンだけ評価を逆にする山登り。あるターンのあるマスに置かないようにする山登り。
道を作り、その他sとｄが同じブロックで詰め込めばいいのでは。
木を作るパート無駄が多いけどとりあえず動くものができた。幅が大きいやつでは70を切るくらいの大きさ。改善できる点としては、壁側を通ると有効活用できる範囲が狭くなるので、距離が同じなら中心側が良い。なんとかしてシュタイナー木に落とし込めないか。
グルーピングパートも作った。グループサイズ15みたいな大きすぎるやつがあるから、焼いたり乱択で何回か試した方が良さそう。
道作るやつ、適当な調整なのに79.5%くらい出ている。
rustでv.shuffle().iter()みたいなのほしい。
80%超えた。提出50位。
明日やるべきこと。
- 木の作り方をもう少し厳密にする。
- ブロックに詰め込むdの値の評価値を考える
コンテスト８日目
82%乗った。のこり時間でなにができるかな。
終わりに
良かった点
- 複数の案を素早く実装して試せた
- 貪欲で上位と同じくらいの順位をとれた
悪かった点
- 上位の点数から解法を読めなかった
最近貪欲にこだわっていたのもあって貪欲解法を高めることができました。焼きなましまでもっていきたかったけど、今回の問題は貪欲から焼きなましへの発展がつながっていなかったようなので仕方ないと割り切って、これからも貪欲を重視したいです。
焼きなましはあるものを決めると栽培計画が自動で決まるような同時に最適化できるタイプのものだったようで、かっこいいのでこれはぜひ習得したいです。
今回ahcで初めてrustを使用しました。コンパイルエラーと実行時エラーで苦しむ時間がほとんどなくなってすごい使いやすかったです。これはむしろ短期コンで役立つ性質ではないかと思いました。
いいかげん橙以上のパフォーマンスを出したいです。
