https://atcoder.jp/contests/ahc004/submissions/23742353
6408108055 点 29 位
1 点更新愚直焼きなまし (ただし 1% の確率で s[i] をそのまま書き込む遷移をする) + ひたすら高速化
- 13:10 点数のグラフは 1e8 点までは線形に伸び、そこからは 2e8 点までわりと線形に伸びる (plot)。
- 13:56 とりあえず shuffle して貪欲に詰めていくと 0.19e8 だった: https://atcoder.jp/contests/ahc004/submissions/23742353
- 14:34 とりあえず共通部分の長さを持って貪欲にする解を書いた。行ごとのそれしか見ない。点数が下がって 0.10e8。バグってそう: https://atcoder.jp/contests/ahc004/submissions/23743461
- 15:02 バグ修正できた。でも 0.32e8 としぶい: https://atcoder.jp/contests/ahc004/submissions/23744345
- 15:09 どうしようか。とりあえずすべて消して焼きなましを書いた方がいい気がする。
- 15:25 愚直焼きなましで点数が改善してしまった。0.41e8 だった。なんだよそれ: https://atcoder.jp/contests/ahc004/submissions/23744941
- 15:31 長さが 5 種類しかないことを使うと微妙に高速化できる。
- 16:03 近傍をすこし増やしたら 0.51e8 になった: https://atcoder.jp/contests/ahc004/submissions/23745916
- 16:45 AWS から 36 vCPUs の環境を借りた。
- 16:49 実行時間を 10 倍にしたら手元 0.53e8 から 0.61e8 に伸びた。ただの最適化勝負な可能性あるな。これに賭けましょう。
- 17:11 trie をしたら手元 0.58e8 に伸びた。正解ぽい。
- 17:20 焼きなましの定数を調整したら手元 0.596e8 になった。もうすこしで 0.6e8 です: https://atcoder.jp/contests/ahc004/submissions/23748700
- 17:35 trie にした上でさらに実行時間を 10 倍にしたら手元 0.65e8 になるらしい。
- 17:47 もうすこし最適化したら手元 0.63e8 になった: https://atcoder.jp/contests/ahc004/submissions/23749413
- 17:47 10 倍にすると 0.67e8 になる。
- 18:01 1 点更新以外は重くて悪化するから 1% だけとか (実質削除) にしてたけど、これを完全削除にしたら点数が悪化した。効いてたらしい。
- 18:10 1 点更新だけだと遷移の半径が小さすぎて局所解から脱出できないのかな。隣接 2 点更新をしてみたけどだめだった。
- 18:22 文字列をまるごと使う遷移は横向きを多めにした方がキャッシュの都合で点数が伸びるらしい。
- 18:28 文字列をまるごと使う遷移の高速化をしないといけない。
- 18:42 バグった。たすけて。やばい。
- 18:56 もう無理。間に合いません。
