2018 TCO MM : Round 1
間髪入れずに Round 1
問題ページはここ
---考察メモ---
TCO MM Round 1 : RoadsAndJunctions
題意：道とジャンクションでシティをコネクト
方針１：
中央(0)と各象限の中心(1,2,3,4)にジャンクション
city は最も近いジャンクションと結ぶ
ジャンクションは 0-(1,2,3,4) を結ぶ
ジャンクションは保険に各地点で 3 つくらい建てとこうぜ
→意外と 3 つとも失敗するケースがある めんどくさい
めんどくさい処理を書いて投げる
とりあえずマップは一次元で管理
指定された点から最も近い空き地点を返す関数 nearestVacantPoint を作る
---
Submission 1
Example scores:
0) 318.94017832845134
1) 19392.70939304412
2) 4256.044350233556
3) 10569.160907479281
4) 2343.676724093129
5) 1409.202049384987
6) 10224.63779700245
7) 2070.805523608351
8) 5455.242073644647
9) 5400.310195639513
Overall score: 158918.92
---
草
方針２：
最小全域木という天啓が降ってきた 典型だけに（うるせ～死ね）
団子ゾーンは最小全域木貼っただけと予想
またグラフかよつれ～という気持ち
maxNC <= 100 つまり V <= 100 なので
単純な集合探索と隣接行列を用いた Prim 法 O(V^2) が一番いいんじゃない
Prim 法の実装に二億時間かかる やめちまえよ人生
---
Submission 2
Example scores:
0) 211.79872859294758
1) 7076.411152439785
2) 2650.3204035796784
3) 3860.759253134664
4) 1145.1735421831447
5) 602.4759453014154
6) 4615.963226471943
7) 1029.2698623641697
8) 2075.8039519401555
9) 2705.9369648535194
Overall score: 125744.68 → 581063.83(27)
---
はいはい
1 つのジャンクションを試しに S^2 の全通り配置したところ，ぼちぼちコストが下がるポイントが存在する
雰囲気的に勾配を持っている気がする
OpenCV でヒートマップをつくってみる
seed 2 のやつ 殆どの場所でスコアが上がる(red)けど稀にスコアが下がる(blue)場所が存在するっぽい
なだらかな勾配になっているようなので，雑に探索して青領域に入ったら勾配を下っていけばよさそう
ただ問題は青領域にジャンクションを作ったとき盤面がどう変化するか
劇的に変わるかそうでないかで打てる方針が変わってくる
全域木も描くことでなんとなく置くべき場所がわかるな (seed 3)
遊べるようにした (seed 10)
色がキモい？仕様です
青領域は鋭角に生えることがめでたく分かった
鋭角を見つけてその二等分線上あたりから探索を開始すればいけそうな気がする
調べる候補もマップ全体の S^2 から頂点数 V まで落ちてホクホクですわ
あとジャンクションを置いても盤面全体がごっちゃになることはない
実装がめんどいのでとりあえず乱択を投げた
---
Submission 3
Example scores:
0) 205.59759906570218
1) 7067.507627897858
2) 2633.8367376866463
3) 3846.8465605546735
4) 1132.570419954085
5) 602.0237783932668
6) 4571.11578218184
7) 1029.2698623641697
8) 2072.7870913733095
9) 2654.202745364103
Overall score: 982985.13(45) → 989618.98(35)
---
まあそんなもん
// -------8<--------------------------------------------------8<-------
バイト疲れとアルコールで何もかんがえられないので乱択を繰り返すクソ解を投げます
---
Submission 4
Example scores:
0) 203.94156997718954
1) 7067.507627897858
2) 2622.030628918046
3) 3833.9898073636828
4) 1125.7941620562603
5) 601.731966144611
6) 4571.11578218184
7) 1029.2698623641697
8) 2071.67993135772
9) 2650.444756447559
Overall Score: 989310.38(53) → 991147.73(44)
---
あと自明な点数向上は失敗も加味して複数のジャンクションを近傍につくるやつ
ジャンクション建設依頼コスト c，建設失敗確率 p とする．
ある地点にジャンクションを設置すると最小全域木のコストが d だけ減少するとき，
その地点および近傍に建設依頼を出すべきジャンクションの数 n は
n = (log(d+1)+loglog(1/p)-log(c+1-p))/log(1/p)
となる．（期待値をガチャガチャやると生えてくる）
これで方針がだいぶ固まってきた
・最小全域木マップでコストが減少するいい感じの建設予定地を探す
・乱択あるいは鋭角っぽい頂点の付近を探索すると見つかりそう
・建設依頼上限数 (NC * 2) に注意しながら建設予定地に割り振る依頼の数を調整する
なかなか良い線行ってる気がするけどどうだろう
---
submission 5
Example scores:
0) 203.85256066396357
1) 7065.001783169469
2) 2623.267569948215
3) 3830.021017720238
4) 1122.915495570179
5) 601.731966144611
6) 4567.495046058705
7) 1029.2698623641697
8) 2071.182408163213
9) 2643.408657548243
Overall score: 990982.69(54) → 991765.41(51)
---
あんま変わらず
990k 出てるからどれかのケースでバグってるとかはなさそう（でも終了条件とか雑に設定してるので気をつけたほうが良い）
期待値微分から最適な n を求めるにしても n が離散なのでどっち？という問題がある
微分しないで min 取ったほうが楽だしバグもなさそう
・乱択で設置箇所の列を求めてるのを設置箇所一つ一つ求めるようにする
・鋭角探索をそろそろ
期待値をちゃんと最大化した ローカル 100 テストでは微妙に伸びたが…
---
Submission 6
Example scores:
0) 203.85256066396357
1) 7076.411152439785
2) 2621.327051831707
3) 3836.366220401473
4) 1123.8013076330988
5) 602.4759453014154
6) 4595.876213072313
7) 1029.2698623641697
8) 2075.8039519401555
9) 2638.9036271561763
Overall Score: 991757.24(59) → 992148.57(55)
---
ちゃんとやれば Example 悪そうに見えてもちゃんと伸びるんだな～すげ～
// -------8<--------------------------------------------------8<-------
ンヌグムを見ましょう
// -------8<--------------------------------------------------8<-------
ローカル環境を改善した
・並列にテスターを走らせて時間を 1/3 に短縮
・ローカル順位表を作る
鋭角探索だが鋭角以外にも青領域が生えることがわかりやめる
盤面をまんべんなく調べるのが楽だし確実かなあという気持ち
盤面がでかい場合は全ピクセル調べると TLE するので適度に荒く探索する
スコアが下がるような点が見つかったらさらに勾配を下って極小点を求める
・雰囲気
d = S / 100
bestScore = 最小全域木のコスト
while( !timeup ) {
score = bestScore
update = false
REP(i, 100) REP(j, 100) {
y = d * i
x = d * j
if( 点 (y, x) に junction 設置でスコアが下がる ) {
update = true
点 (y, x) から勾配を下って極小となる点 (ny, nx) を見つける
newScore = 点 (ny, nx) に junction を設置した場合のスコア
score = min(score, newScore)
}
}
if(update) {
bestScore = score
}
else {
break
}
}
---
Submission 7
991673.92(103) → 995840.84(36)
---
二ページ目に追いやられた時はどうなるかと思ったけどこれで一安心
// -------8<--------------------------------------------------8<-------
消す順序によっても得点が変わるような気がした
貪欲である程度マシな点が出ているのでここはビームサーチが良いだろう
ただ時間管理とか詰めきれる気がしなかったので楽と噂の chokudai search に賭けてみることに
残り 10 時間切ったところで chokudai search の実装を始める
Zobrist Hash なども調べて重複した状態を格納しないようにした
残り 6 時間でコードが書き上がる
ビーム幅などを微調整して最終的にローカル順位表で 20 点ほど伸びたので Submit
---
Submission 8
995911.32(53) → 996173.04(45)
---
ありがとう chokudai 神
そのまま正のポイントも貰えますようにと願掛けして就寝
