1,509,391点で 163位/549人 でした。
今回の問題は個人的に、
- まず始点を全部巡ってそのあと終点のTSP解くのが楽だけど、とはいえ上手いこと入り混じりながら進みたい
- 1,000注文からどう50注文を選ぶ？
- 4時間でどこまでやれる？
あたりが悩みどころでしたね。
最終提出コードがこちらで、 Submission #27260292 - Kyocera Programming Contest（AtCoder Heuristic Contest 006）
入力例0000のビジュアライズ結果が下図な感じでした。
ざっくりと解法と感想について書いていきます。
最終提出の内容
- AtCoderオフィスを中心とする一辺450の正方形を用意し、選択対象注文を、その範囲に始点終点が収まる注文に絞る
- 先に始点を巡り切ってから、終点を巡り始める。ただし、始点巡り中に無理なく踏めそうな終点だけは踏む。
- 移動対象の二点を頂点とする長方形内に、消化可能な終点が含まれている場合は踏む*1。
- ただ、ビジュアライザを見た感じだとあんまヒットしてませんでした。
- 移動対象の二点を頂点とする長方形内に、消化可能な終点が含まれている場合は踏む*1。
- 始点の巡回路は、「
最後に訪れた点-注文の始点間の距離の短さ」と、「注文の始点-終点間の距離の短さ」を考慮して決める(「最後に訪れた点」と「注文の始点」間の距離) + (注文の始点-終点間の距離) / n- 整数
nは、[2, 6]の５パターンを試して、一番良かった結果を採用しました。
- 整数
- 終点の巡回路は、TSPを2-opt山登りで計算して決める
ということをしました。
大まかな方向性は、４時間で問題無く実装できるもので、ある程度安定して成果が見込めそうな内容*2をやるって感じでした。 良い具合に時間が余ったら、そこで得られた結果を元により良い解法を〜、みたいなお気持ちでいたのですが、 大枠の内容が終わった時点で３時間強が経過していたので、残りの時間はパラメータ調整やパラメータ複数パターン試行、みたいなところに割いて終えました。
時間があればやりたかったこと
焼きなまし方面の試行錯誤をやりたかったな、をとても思いました。 色々と考えられましたよね。注文の選び方だったり並べ順だったり。貪欲でなくそっちの試行に主に時間を割くべきだったかなってコンテスト途中から結構思ってましたね。
コンテスト後半に大枠の方針ミスってそうだなって思った時は、どうするのがいいんでしょうね？ 方針ミスってるなりに頑張るのか、ムリくり方針変えにいくべきなのか。 レートシステムを考えたら、変えに行くべきって気はしますが*3。
所感
個人的には凄く好きな問題でしたね。 巡回路問題に良い感じに制約を足して、さあどうするの？って感じが色々と考えようがあって面白かったです(小並)。長期で出されてもいい感じにハマれそうな気がしましたね。
実際、TL見てると結構いろんな方針の解法がありそうな気配で、復習するのが楽しみです。どっかで時間割かねば。
