Links
結果
延長戦：天才貪欲の再現 (score : 5,388,249,433)👍️
延長戦：近い葉マージ (score : 3,496,296,312)😭
惜しいノート
- コンテスト中の考察ノート
- 右上からマージしていき、その結果をさらにマージしていくアイデアはあった
- ただ「マージした2点はもうマージに含めない（★）」というのが抜けていた
- その結果「元の点がN点だと、マージで新しくできる点がN-1点で、4段くらいしか作れない...」と考えていた
- ★のアイデアを使うと無駄な辺が減り、グリッドではなく木になる（下記画像の紫の太い線）
1位の解法
2024/09/19 追記：さらに延長戦！ビームサーチ (score : 5462997128)👍️
- AHCラジオを見ていると「貪欲からビームサーチは自然」とか「こうやって枝刈りして」など見たのでビームサーチにトライ
- ラジオではサラッと言われているけど、私の場合実装に1日かかった ^^;
- 提出(本番2位相当) https://atcoder.jp/contests/ahc037/submissions/57911179
- まずビーム幅1で貪欲と同じスコアが出るようにする
- 枝刈りでミスして大変だった
- ●枝刈りなしでビームサーチだけ完成させる
- ●枝刈りを入れてスコアが変わらず速度UPのみすることを確認
- と分けるべきだった。枝刈りなしだと重すぎて解が（手元でも）求まらない場合もありそう...
- 次に、ビーム幅を増やすとStateのコピーが重いのでMiniStateを作って候補の時点では差分のみ持った
- ビーム幅は70までいけた。wataさんの実装では2200
- ビーム幅を増やしていくと今度はMLEが起こった。resize(0)では不足で、shrink_to_fit()してcapacityも解放させる必要があった。速度も上がった
- ソート済み配列に1つ値を追加してまたソートする際、implace_mergeを使った。これも速くなった
- 状態の重複除去について。ビームサーチは多様性が大事なのに、マージの順番が違うだけで同じ状態になりうるので、これは除去したい。「setでやるのか？重そう...」などいい方法が思いつかないのでwataさんの実装を見ると、（生きている）各頂点をハッシュ化してその和をハッシュ値としていた。ラジオでは触れられていなかったが、これは学びになった
fn f(p: (i32, i32)) -> i64 {
(p.0 as i64 + 1) * 1000000007 + p.1 as i64 + 1
}
