【今日の精進】ABC283G - Partial Xor Enumeration

毎日格上の問題を倒すやつの89日目です。

問題リンク

atcoder.jp

問題概要

数列 のいくつかの要素をxorしてできる数のうち、小さい方から 番目から 番目までのものを列挙してね。

解法

xorの基底の練習問題です。

noshiさんが広めたよくわからないすごい方法で基底を求めます。

xor の掃き出しすごい簡単に出来るんですね

vector<int> basis;
for(int e : a){
for(int b : basis)
chmin(e, e ^ b);
if(e)
basis.push_back(e);
}

これで数列 a の基底が basis に入る

— 熨斗袋 (@noshi91) 2019年11月30日

すると、あとは上の位から決定すればよいです。

提出コード

N,L,R=map(int,input().split())
base=[]
for i in list(map(int,input().split())):
    for j in base:
        i=min(i,i^j)
    if i:
        base.append(i)
base.sort()
ans=[]
for i in range(L-1,R):
    ans.append(0)
    for j in range(len(base)-1,-1,-1):
        if (i>>j)&1:
            ans[-1]=max(ans[-1],ans[-1]^base[j])
        else:
            ans[-1]=min(ans[-1],ans[-1]^base[j])
print(*ans)

Submission #48629696 - UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283)

感想

あまりにもうまくいっててびっくりした

空いた日にやってたこと

87日目

【今日の精進】
Codeforces Round 588 (Div. 1)
0完。何を四天王！？

A...SCCっぽいけど合わず

[バーチャル参加]
hirayuu_cfさんのCodeforces Round 588 (Div. 1)での結果は633位でした！
パフォーマンス：552相当
レーティング：2118→2018 (-100)#CodeforcesAnytimehttps://t.co/XpiYTuHg6d

— はるく@0完 (@halc_kyopro) 2023年12月16日

88日目

【今日の精進】
Codeforces Round 576 (Div. 1)
A...難しそうだけど要はソートした列の上で種類数が特定以下で最大の長さのものをしゃくとりで求めるだけ
B...遅延セグ木にモノイド載せて
C...何もわかりません
D..."全く"同じ問題がAtCoderにあり、しかもこどふぉの方が先…

— はるく@0完 (@halc_kyopro) 2023年12月17日