Harbour.Space Scholarship Contest 2023-2024 : E. Guess Game

まぁまぁ良かった回。
https://codeforces.com/contest/1864/problem/E

問題

整数集合Sが与えられる。
うち2要素を等確率で選んだとする。
その値をa,bとする。

• 先手には、aとa or bの値を教える
• 後手には、bとa or bの値を教える

先手から順に、

• aとbの大小関係がわかるならその大小関係
• わからないならわからない

と交互に答える。

最終的に大小関係が確定するまでの回答数の期待値を求めよ。

解法

上のbitから順にみて行くことを考える。

• a or bが0であるbitは無視してよい。
• a or bが1であるbitに対し
  • 自身のもつaまたはbが0を持っていれば相手の方が大きいことが確定する。
  • 自身のもつaまたはbが1を持っている場合、今度は相手が0/1どちらを持っているか判断する。自分が0なら相手が大きいことが確定だし、そうでなければそのbitは等しいと2回の解答を掛けて確定する

上記作業を、順次行う。
Sをソートしておき、2進数表記においてprefixが正しい要素の集合毎に、上記手順で回答回数をカウントしよう。

int T,N;
ll S[202020];
const ll mo=998244353;
ll ret=0;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void dfs(int d,int L,int R) {
	if(L==R) return;
	if(d<0) {
		(ret+=1LL*(R-L)*(R-L))%=mo;
		return;
	}
	
	int M=L;
	while(M<R&&(S[M]&(1<<d))==0) M++;
	// 01
	(ret+=1LL*(M-L)*(R-M))%=mo;
	// 10
	(ret+=2LL*(M-L)*(R-M))%=mo;
	// 11
	(ret+=1LL*(R-M)*(R-M))%=mo;
	dfs(d-1,L,M);
	dfs(d-1,M,R);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>S[i];
		sort(S,S+N);
		ret=0;
		dfs(30,0,N);
		ret=ret*modpow(1LL*N*N)%mo;
		cout<<ret<<endl;
	}
	
}

まとめ

こういうタイプの問題、自分では考えないなぁ…。