# AHC003 まずは$H_{i, p},\ V_{j, p}$を求める $i$が揃う確率は$1/30$、$j$についても同様 →900回必要 無理では 同じ場所を何度も行き来すれば大体求まる M = 2のときは境界を二分探索できるが、とりあえずM = 1として重みを初期化したあとに重み付き線形和の推定で良いかも え，同じ頂点は一度しか通れないらしい 皆どうやってるんだ... 辺を長さ1として最短距離を出力→たぶん63,179,310,956 1位のスコア(97,266M)を取るには75回程度で探索を負えなければならない 同じ行/列にも更新をかけるか ensambleも良さそう →初めのほうは分散が高い辺を進めばいい 初期値はある程度ランダムのほうが良い？ 全く良くならなかったな ## 推定法 重み付き線形和を求めれば良い($x_i \in \{0, 1\}$) * 勾配法 * テキトーな勾配法もどきで86Gくらい * パラメータに依存しそうだけどいっても90Gかな * 90.8Gくらいだった * ターンじゃなくて含まれた回数で勾配をかける * 今までのを保存しておいてバッチ勾配法にする * 勾配法をしたあとに確率的勾配法をすると91.7G * 5回やると92.2G * Adamを使う * バグっててずっと$\alpha = 1$だった * 何故かこのほうが強い なんで？ * 最小二条誤差 ### パラメータ * 同じ行/列に更新をかける * パラメータを$H_{i, 1}C_{i, j}x_{i, j} + H_{i, 2}(1 - C_{i, j})x_{i, j} + \delta_{i, j}x_{i, j}$にする * $0 \le C_{i, 1}, C_{i, 2} \le 1$ * $-D \le \delta_i \le D$ * Cの初期値は期待値にする * $\frac{\partial}{\partial{H_1}}f = -2C_i(y - y_{pred})$ * 正規化しないとやばそ〜〜〜(やばいだろ) * ありえん発散すると思ったら正負逆で草 * 精度は良くなっているが，なかなかCが思った挙動にならない * なんでCの逆転が起こるんだ * 勾配の計算あっとる？ * パラメータテキトーで95.5G * 訪れてない点のCが更新されなくてしんどい * 近くのやつで補間する * これかなり本質に見えるな * 端っこが保管できなくて困っちゃうな * これやって探索を90ターンで打ち切ると95.7G * びぞーで草 * 130で95.84G * 0, 0, 0, 0, 0.25, 0.5みたいになってるときがあり，良くない * $H_1 \ge H_2$にしたいし初期値を5500, 4500にするのありかも * いやこれ関係ないな * $C_{i, j} \ge C_{i, j + 1}$にしたい * どうやんの * 端を常に1にしたらスコアは上がった逆転は起こるが 96.167G * 変更前が96.152Gだから，誤差じゃん * /15にしたら96Gに... * /10にしたら96.08Gに... * なんで学習率上げるとスコア上がるんだ * 局所解に嵌っているか過学習か * alphaを下げていくのはちゃんと効いていそう * Adamもう一度試す価値あり * 0.3Gくらいは効きそう * わんちゃん自由度増やしてもいいけど * $C_2$も追加したらめっちゃ上がってびっくり どうしてこんなことに... * え，良くなってなくて草 * /2400で96.38Gくらいにはなったけどあまり本質的じゃなさそ〜〜〜 * パラメータ調整したから伸びたのか自由度上げたから伸びたのかわからなくなってきた... * ちょっとパラメータ変えるだけで0.2Gくらい変わるな ## 探索 実は探索部分がかなり重要という話 これテキトーすぎるだろ なんとかしろ * 探索してない行/列を探索するようにしたい * 誤差で探索を終了させたい * これ難ししゅぎ ### dijkstraのコストにテキトーにペナを付ける (turn < 110 ? (double)get_weight_cnt_ref(h, w, i) * 1000 : 0.0) → 93.2G ## テスト(1000ケース) 改善前: 962578140.391 改善後(tune前): 962768111.64 改善後(tune後): 963628434.93 Trial 5 finished with value: -965097106.58 and parameters: {'start_alpha': 0.06292361519223809, 'end_alpha': 0.020740325416516235, 'epoch': 10}. Best is trial 5 with value: -965097106.58. [I 2021-05-30 22:43:39,478] Trial 105 finished with value: -967933996.32 and parameters: {'alpha_c': 3.59211526432875e-05, 'alpha_hv': 5.501070911212613, 'alpha_delta': 0.20900123772657023, 'start_alpha': 0.04765692232530199, 'end_alpha': 0.033552140511841674, 'penalty': 2.8306888757300017, 'turn_c': 6.294189419752, 'exploitation_turn': 69, 'beta': 17, 'epoch': 8}. Best is trial 105 with value: -967933996.32. 965165063.983