AHC020 - HackMD

これ電波の出力に勾配法使えるんじゃね使う頂点集合 $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時間 ![](https://hackmd.io/_uploads/H1lt-mHPn.png) ``` 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 ```

Read more

AHC 021

こどげ春2023

AHC019

AHC018