2022年4月13日

2022 年4月13日

今日の一曲

競技プログラミング　軍ミラグロ府義強

ABC236 F- Spices

[XORの基底、内部は分からない、類題あり、解説動画優秀、掃き出し法]

先日行われたARC138 D-Differ by K bitsの類題ってことで良いですか？良いですよ。

掃き出し法のわけが分からない実装ですが、

• 公式解説 by admin

を見るとちょっとだけ「あー、そんな感じノコとしてるのね。知らんけど」ってなります。

for(int e : order){
        
        for(int b : basis){
            chmin(e, e ^ b);
        }
        if(e){
            basis.push_back(e);
        
        }
    }

このコード、Twitterでのし袋さんがのけてたやつみたいな感じです。

これをすると、basisに配列 orderの中から基底が取り出せるらしい。

このコードだと、eに加工が施された後にbasisにpushサれてしまうので、ちょっと変える。

 for(int e : order){
        ll mae = e;
        for(int b : basis){
            chmin(e, e ^ b);
        }
        if(e){
            basis.push_back(e);
            maes.push_back(mae);
        }
    }

こう。

なんかね、解説動画見るとスッキリする。

• a,bが基底のとき、aとa^bの2つでも基底になる

っていう説明が理解の手助けになりました。

ほとんど写経みたいなものですが、にぼしのコード貼っておきます。 202