第3回RCO日本橋ハーフマラソン予選 参加記
問題
A. ツーリストXの旅行計画
N個の都市を1度だけずつ順番に巡って最初の年に戻ってくるようなルートを考える。
都市間の移動距離をの分散ができるだけ小さくなるようなルートを見つけよ。
N = 200
0 <= x_i, y_i <= 500
B. ファーマーXの収穫計画
N*Nの区画の庭があり、i行j列目の区画にA_ijの品質の野菜がある。
各区画からは1度だけ野菜を収穫できる。
次の操作をX回実行できるとき、収穫する野菜の品質の合計値をできるだけ大きくなるように操作の計画を立てよ。
- 手入れ：選んだ区画の品質を1増やす。収穫済みなら何もしない
- 収穫：選んだ区画とその周辺の条件を満たす野菜を収穫する
- 選んだ区画の野菜が品質Kのとき、まだ収穫されていない隣接する品質がKの野菜をまとめて収穫できる
- ただし、まとめて収穫する野菜の数がK個以上でないと収穫できない。K個未満なら何もしない
N = 50
M = 2500
1 <= A_ij <= 9
最終的に提出したアプローチ
最終提出の解(input_1.txt)
- A問題
- 点swapの焼きなまし
- B問題
- 収穫を目指す品質をxとして、品質y ( < x )のものをxまで育てることを考える
- 上記をやったとして、できるだけ多く収穫できるものからgreedyに取る
- xを9から1まで、yはいくつか探索して、最終的に良いスコアのものを返す
時系列での振り返り
進め方の方針
- A問題1時間、B問題1時間を使う
- 残り2時間はA,Bの進捗具合で決める
開始～1時間
- 問題を読む
- 焼きなましが有効そうなのは見てわかるが、TLEが2秒で十分探索できるか不安
- とりあえず組んでみてどの程度スコア行くか見てみる
- 近傍はとりあえず2点swap、細かい高速化はあとで
- そんなに悪くなさそう？
- 一旦提出
1時間～2時間
2時間～3時間
- Bの進捗がまずいのでBにいったん1時間使うことにする
- とりあえず適当に組む
- 品質9で収穫するのに7以上を育てたほうがいいのか、6以上を育てたほうがいいのかなど、細かく考えるとうまい実装を考えないといけなそう
- とはいえ、適当にやってもそんなに悪くない解にいけそうなので、いったん収穫したい品質ごとに独立に計算するように実装
- 一旦提出
3時間～3時間半
- 提出してみると全然時間を使っていない
- 上記のパラメータをいろいろ調べてみるのはありかも
- 実装を変えようと思ったけど、時間が厳しいので、途中でやめて簡単にできるところだけにしようと方針転換
- 下限だけいくつか変えてみるのを試してみるとちょっと良くなりそう
- B再提出
3時間半～終了
- Aの1位のスコアがヤバいことになってる
- 逆算してみると平均分散が10を切っているよう
- 近傍？チューニング？バグ？そもそも別方針？などテンパりつつどうするか考える
- 近傍をいじるのはやや大変だと思うので、とりあえず時間を延ばして実行して温度調整で様子を見る
- あんまり上位を狙えるものではない
- 近傍は2点swapだと4辺変化してしまうので、普通に2辺swapにするだけでやや良くなるだろうけど、どんなもんか
- 別方針としては、あんまり大きくない辺のみを使って計算することで無駄な辺を考えなくて済むようになる？
- 辺を禁止する方はすぐできそうだしやってみる
- うまくいかなった
- 残り10分で2辺swapに書き換えられるか
- あー間に合わないー
- 終了
反省
- 焼きなましは近傍が大切というのは何度も経験してたはずなのに適当に組んでしまったのはいけなかった
- 結局2optにして分散をO(1)計算にするだけで330万点ぐらいがでてしまった
- 提出スコアは47万点
- そもそも2optの実装がうまい方法を自力で出せなかったので時間内に実装できても140万点ぐらいだった模様
- 近傍は小さいのを最初から選択すべき
- 今回だと3optみたいなやや重でもよい近傍を選べるなら有効だったよう
- また、今回みたいなのは、辺スワップはreverse操作があって重いので、undo操作ではなく、スコア計算を先にしてundoしないとわかってからreverse操作をするような実装にすべき
- Bの方は他の人を見てもそんなに大筋は外していない方針だったのでよかった
- 「コスパが悪いものを取らない」はすぐに入れられた要素だったのに入れられてなかったのは悪かった
