2019/11/02に行われたHACK TO THE FUTURE 2020予選に参加しました。 解法はダイクストラ(曲がり回数100ゴールからの距離を負のコスト+4近傍のブロックの個数の2乗-ゴールからのマンハッタン-5)からの不要矢印削除で、最終成績は07:32に提出した4,941,365点で143位(参加者は841人)でした。
問題概要
N*N
のグリット上に矢印をいくつか出して、ロボットをゴールさせ、ゴールしたロボット数と矢印の数に応じた点数を最大化する問題でした。
やったこと
00:05 48,047 print(0)
48,047点が得られます。正の点数を得ました。
00:33 4,374,029 幅優先探索
ビジュアライザを見てみるとゴールしていないロボットがいることが分かります。
ロボットのゴールに対する加点(1000点/ロボット)が矢印を置くペナルティ(-10点/矢印)よりも大きく、全てのマスに矢印を敷き詰めたとしても点数を改善できるため、実装します。
同じ矢印に囲まれている矢印は消しました。
ゴールから幅優先探索を行い、全てのロボットがゴールできるようにすると4,374,029点が得られます。
ゴール連結な全てのマスに矢印が置かれている状態になりました。
02:32 4,907,639 シミュレータの実装
シミュレータを実装しました。 テストケースを500ケースダウンロードしてきて、手元でまとめて回せるようにしました。
if [ -e summary.csv ] ; then mv summary.csv summary_old.csv fi echo "case,score,n_goaled,n_guide,n_visited" > summary.csv for i in $(seq 0 499); do python httf.py < testCase/testCase_${i}.txt > testCase/testCase_${i}.out cat testCase/testCase_${i}.txt testCase/testCase_${i}.out | python simulator.py summary.csv testCase_${i}.txt if [ $(expr $i % 20) = 0 ] ; then echo "finished processing testCase/testCase_${i}.txt" fi done csvstat summary.csv
csvstatを使うと各カラムの合計と分散が簡単に得られます。
1. "case" Type of data: Text Contains null values: False Unique values: 500 Longest value: 16 characters Most common values: testCase_0.txt (1x) testCase_1.txt (1x) testCase_2.txt (1x) testCase_3.txt (1x) testCase_4.txt (1x) 2. "score" Type of data: Number Contains null values: False Unique values: 276 Smallest value: 96,862 Largest value: 99,165 Sum: 49,385,296 Mean: 98,770.592 Median: 98,892.5 StDev: 374.902 Most common values: 98,886 (12x) 98,893 (6x) 98,919 (5x) 98,876 (5x) 98,909 (5x) 3. "n_goaled" Type of data: Number Contains null values: False Unique values: 3 Smallest value: 98 Largest value: 100 Sum: 49,930 Mean: 99.86 Median: 100 StDev: 0.375 Most common values: 100 (435x) 99 (60x) 98 (5x) 4. "n_guide" Type of data: Number Contains null values: False Unique values: 45 Smallest value: 130 Largest value: 179 Sum: 78,091 Mean: 156.182 Median: 156 StDev: 8.461 Most common values: 155 (32x) 159 (31x) 158 (26x) 160 (25x) 156 (25x) 5. "n_visited" Type of data: Number Contains null values: False Unique values: 111 Smallest value: 400 Largest value: 545 Sum: 236,206 Mean: 472.412 Median: 472 StDev: 24.536 Most common values: 459 (14x) 466 (13x) 465 (12x) 462 (11x) 489 (11x)
05:33 4,907,639 何をやっても点数が改善しません
- bfs -> dfs
- ドツボにはまるとパネルの消費が激しい
特定パターンの改善をしたい
→↓
○→ とか改善できないかなと思って実装をしていましたが、無理でした。
06:07 4,913,977 敷き詰めた後使わないマスを消す
ロボットに踏まれた回数を持っておいて、0回のものを削除しました。
07:19 4,938,045 bfs -> ダイクストラ
曲がり回数を最小化したい気持ちになったので、ダイクストラ法に切り替えました。
07:32 4,941,365 ダイクストラのパラメータを探す
ゴールの近くには矢印がたくさん置かれるので、遠くから真っ直ぐ向かってきてくれると嬉しい気持ちになったので、距離を負のコストに追加していました。 ブロックの多いゾーンは嫌な気持ちになったので、4近傍のブロック数をコストに追加しました。
この後は踏むマスの数を考えないといけないか……というところで時間切れです。
感想
これまでのマラソンマッチの中では、順位が良かったほうですが、探索が全くできず実行時間は2秒以上余らせてしまって、申し訳ない気持ちです。 本戦出場の皆さん頑張ってください。
解説放送を見て復習します。