012BFSはqueueを3個持つ

012BFSとは?となったキッカケ

  • https://twitter.com/chokudai/status/1754369800862900253
  • chokudaiさん「01BFS知ってるなら、012BFSは発想できるでしょ」
  • 私「???」
  • 理由は、01BFSをdequeで実装するものだと思っていたため。一方でchokudaiさんはqueue 2本での01BFSをイメージしている

01BFS

  • dequeを使った実装で紹介されることが多い

012BFS

tweets

AHC 至高のアルゴリズム リンク集

その他

AHC029(RECRUIT 日本橋ハーフマラソン 2024冬)で38位。賞品を頂いた

  • 40位までならパーカー確定。pretestで41位だったかな、手元で100ケース回して良いコードを提出していたので何人かはsystem testで抜けると思っていた
  • コンテスト終了が2023-12-26(火) 21:00
  • ちょうど1ヶ月経たないくらいで賞品が届いた。早くていいね。ありがとう

賞品たち

  • パーカーL 素材の質としては普通
  • ひざ掛け(右上)
  • ネックウォーマー(左下)
  • (それぞれ、屋外のマラソンに役立ちそう)

AHC017復習 ダイクストラ内の最短路木の差分更新

問題

提出

ダイクストラ内の最短路木の差分更新

  • 解説放送でも1位や7位のユーザ解説でも「ダイクストラの実行後は最短路木ができていて、工事を[増やす/減らす]すると最短路木が部分的に変わるだけなので、差分更新で高速化します」と言われている
  • 当時は「ほーん、たしかにできそう」でスルーしたが、知っていることとやったことがあるのは違うということで挑戦してみた。1, 2日くらいでできると思っていたら5日かかった
  • ハマった理由は、スコアが上がらなかったときに「巻き戻し」する必要があるのにしていなかったから(いつもの[山登り/焼きなまし]では状態のデータが軽いので捨てるだけで済んでいて、盲点だった)
  • グラフの持ち方をvectorからsetにしたり、最短路木の管理用に新たに構造体を作ったりもした

初期解

  • 連結を重視して、各日にどこからからBFSして全点と連結させた
  • さらにスコアを伸ばすなら、すべきは初期解の洗練だろう

サンプル点

  • スコアは5頂点からのダイクストラで近似。10頂点にしてもローカルでは悪化した
  • 回転数が減るので、登りきれていないのだろう
  • (でも参加記では10以上が多かった記憶)

登り成功回数 / 登り挑戦回数 のサンプル

2338/33999
1893/26778
1982/31588
1680/29365
1735/25026
1399/43452
1546/54964
1699/44082
1558/41998
1932/44380

追記:さらに延長戦

  • 初期解を洗練させた perf 2372 https://atcoder.jp/contests/ahc017/submissions/49161734
  • 参考にした、wataさんのRustの提出 https://atcoder.jp/contests/ahc017/submissions/38654953
  • それをふまえて、
  • (前提)複数持っているダイクストラは、全ての辺が破壊されていない状態とする
  • (知恵1)ある辺を何日に削除すればいいか、全ての日にちで1度切ってみて(全日の)スコアを出し、1番良いものを選ぶ
  • (知恵2)辺の処理順はXが小さい順とする
  • (知恵3)工事の頻度が均等になるように係数orペナルティをつける
  • 初期解生成で(手元では)5500msかかるものもあったが、初期解の質が良いのだろう、提出すると順位UP(手元でも最終提出との比較で改善)
  • 初期解が優秀なので山登りの成功率は下がっている。例は以下
216/38806
288/38283
125/20027
139/5611
207/12576

abc334 C - Socks 2 累積和を使わない解法

  • 問題 https://atcoder.jp/contests/abc334/tasks/abc334_c
  • C問題にしては難しい!
  • Kが偶数の時は自明なので省略します
  • Kが奇数の時、i=0, 2, 4, 6, ... を除外した時の奇妙さをそれぞれ求めてminを取りたい。そのまま実装するとO(N2)
  • まず、i=0を除外した時の解をO(N)かけて求めます
  • 次に、i=2を除外した時の解を、上の解を利用してO(1)で求めます。変化する箇所がi=0,1,2しかないので、差分を見ればいいです
    • i=1,2のペアを解除して、i=0,1をペアにする

code

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin>>N>>K;

    VI A(K);
    rep(i, K){
      cin >> A[i];
    }

    ll ans;
    if(K%2==0){
      ll sum=0;
      rep(i,K/2){
        ll a = A[2*i];
        ll b = A[2*i+1];
        sum += b-a;
      }
      ans=sum;
    }
    else{
      // どれを除去する?
      ll sum=0;
      rep(i,K/2){
        ll a = A[2*i+1];
        ll b = A[2*i+2];
        sum += b-a;
      }
      ans=sum;

      // iを除去した場合
      for(int i=2; i<K; i+=2){
        ll kesu = A[i]-A[i-1];
        ll tasu = A[i-1]-A[i-2];
        sum -= kesu;
        sum += tasu;
        chmin(ans,sum);
      }
    }
    p(ans);   
    
    return 0;
}