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近傍のブロック数をコストに追加しました。
この後は踏むマスの数を考えないといけないか……というところで時間切れです。
感想
これまでのマラソンマッチの中では、順位が良かったほうですが、探索が全くできず実行時間は２秒以上余らせてしまって、申し訳ない気持ちです。 本戦出場の皆さん頑張ってください。
解説放送を見て復習します。
