これ電波の出力に勾配法使えるんじゃね

使う頂点集合

$Z$ を焼きなまし

• $Z$ をターミナルとした最小(最小ではない)シュタイナー木
  $T$ を構成
• $T$ に含まれる頂点の出力を決める
  • $C(v):=T$ の中で
    $v$ が最も近い頂点となる家の数
    $(v\in T)$
  • $C(v)$ が大きい方から
    $2|T|/5$ 個までの頂点の集合を
    $V$ とする
  • 各家を
    $V$ の中で最も近い頂点に割り当てる
• $P=0$ の頂点を省いてシュタイナー木を求め直す
  • 使った辺を
    $B$ とする

貪欲

• K-means でクラスタの中心を決める
  • クラスタの数を決めるのがむずい？
• 中心に一番近い放送局を使う
• ↑はむずいので各家ごとに貪欲
• MST

使う放送局をSAで決めるのが一番丸い

• 経路はMST
  • これ差分計算したいねえ
  • 辺を直接焼き鈍す？
  • なんてったって速い！
    • やってません
• 家の割当は最短距離
  • ここ重そう
  • 前計算
  • 家が近いものはまとめる？
• $P^2$ の方が数倍でかい こっちを優先して減らす

1位

1ケースあたり平均: 1,676,559

1e9: 1487571.21
1e8: 1487571.21

loop

0: 1612192.43
5: 1587046.37
10: 1571564.68

pt

300: 1612141.46
500: 1612480.72
700: 1611177.45
1000: 1609367.48

1624648.16

2時間

1982 0 4519 0 3631 0 0 0 0 0 788 2775 1227 0 0 3993 0 0 0 2093 0 0 706 0 0 0 0 0 0 0 1071 0 0 0 0 0 0 0 0 2973 460 0 288 1436 0 0 1352 0 0 3064 0 0 0 4076 0 0 0 0 0 0 474 0 0 0 0 1670 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1442 0 1465 0 969 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 

100: 177955795
200: 175337828
300: 170205441
400: 165243441
500: 166782171
600: 173792451
700: 172360120
800: 171686600
900: 171349108
1000: 170133146
1100: 173333567
1200: 171145522
1300: 172143940
1400: 168544350
1500: 168802758
1600: 166120551
1700: 168341943
1800: 165802609
1900: 166659573
2000: 164127739
2100: 166321105
2200: 169214925
2300: 162714147
2400: 160464553
2500: 162176335
2600: 163630878
2700: 159737989
2800: 157364740
2900: 158812942
3000: 158168185
3100: 155238170
3200: 162402439
3300: 160165621
3400: 161522192
3500: 153186274
3600: 153834931
3700: 153834931
3800: 151975590
3900: 156251453
4000: 157961407
4100: 155608945
4200: 154559150
4300: 159213676
4400: 160419693
4500: 162796918
4600: 163707053
4700: 152280362
4800: 153069874
4900: 157013607
5000: 152849978
5100: 148559900
5200: 148080558
5300: 146571687
5400: 146270932
5500: 148598249
5600: 147031723
5700: 148061632
5800: 147639372
5900: 147019715
6000: 146433369
6100: 147113568
6200: 146529306
6300: 147837949
6400: 145576589
6500: 145483317
6600: 144550457
6700: 144623106
6800: 145013333
6900: 146278871
7000: 145540854
7100: 145034580
7200: 144880783
7300: 145202611
7400: 144379993
7500: 145210341
7600: 144381016
7700: 142833139
7800: 143188766
7900: 142604021
8000: 141823642
8100: 141823642
8200: 141697197
8300: 141957176
8400: 141552041
8500: 141514820
8600: 141697197
8700: 141697197
8800: 141277676
8900: 141277676
update/loop: 1286/8912
mst
1661925
116534390
24540209
Score = 1661925