【Atcoder日記】ABC #365,367のC問題【二分探索、辞書順】

こんにちは。RockinWoolです。
久しぶりの投稿になりました。メンタルを病んでパソコンに向かえない日々が続いておりましたが、なんとか乗り切ることができました。そして先日ついに茶色コーダーになることができました。
さて、今回もAtcoderの挑戦日記になります。

二分探索法の問題

#365のC問題は色々計算して閾値を求めるよりも、二分探索で無骨に求める方が速さ的にも良いという(クソ)問題でした。解けなかったのは素直に悔しい。こういう閾値を求める系の問題が出てきたら二分探索法を疑うようにしなければ。二分探索法をコードは以下に示します。

    int ok=0, ng=1000000000;
    while(abs(ok-ng)>1){
        int mid = (ok+ng)>>1;
        ll tmp=0;
        for(auto v:A) tmp +=min(mid,v);
        if(tmp<=M){
            ok=mid;
        }else{
            ng=mid;
        }
    }
    cout << ok << endl;

これでmidに改良の余地がある限りはmidが調整されていき、最終的に一意に求まるという関数ができます。この考え方はよーく覚えておきたい。

低い方から辞書順に並べる問題

Atcoder367のC問題は初見では解くことができませんでした。そもそも解き方を知らないと対策できない系の問題でしたね。肝心となるのは「辞書順に低い方から並べる」という部分です。こういう数列の問題が出てきたら再起関数の実装問題なんだという合図のようです。

void solve(int lv){
    // もし数列の長さがnになったとき
    if(lv==n){
        int s=0;
        for(int i=0;i<n;i++) s+=seq[i];
        // もし総和がkで割り切れれば出力する
        if(s%k==0){
            for(int i=0;i<n;i++){
                if(i) cout << " ";
                cout << seq[i];
            }
            cout << endl;
        }
        return;
    }
    // もしiが上限r[lv]よりも低い場合はseq[lv]を増やす
    for(int i=1;i<=r[lv];i++){
        seq[lv]=i;
        solve(lv+1);
    }
}

この関数の形は基本的に使いまわししたほうが良さそうなので、今後も同様の問題が出てきたら使えるようにしておきたいですね。

まとめ

二分探索法と辞書順に並べる問題の解き方について復習しました。目指せ緑コーダー！