Google Code Jam 2022 Qualification Round : E. Twisty Little Passages

なるほど…。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a45fc0

問題

N頂点の単純無向グラフがある。
ここで以下の手順を合計K回以上使用し、このグラフの辺の数を推測せよ。

今プレイヤーはある頂点にいるとする(部屋の番号はわかる)。

• 指定した頂点に移動し、そこの辺の数を得る。
• 現在いる頂点に隣接するいずれかの頂点にランダムで移動する。

解法

KがNより小さいので、全頂点をたどることはできない。
かといって、適当にサンプリングして外挿すると、ウニ型のように稀にある高次数の頂点を見逃す。
そこで、前者と後者を交互に行おう。後者を行うと、高次数の頂点に到達する可能性が高い。

高次数の頂点は例外的な頂点なので、前者で移動した頂点について（後者で移動した頂点を除いて）辺の数を外挿し、後者で移動した頂点の辺の数を足そう。

int N,K;
int num[101010];
void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	
	cin>>N>>K;
	MINUS(num);
	
	int small=0;
	ll smallS=0;
	int large=0;
	ll largeS=0;
	
	cin>>x>>y;
	small++;
	smallS+=y;
	num[x]=y;
	
	vector<int> cand;
	FOR(i,N) cand.push_back(i+1);
  	random_shuffle(ALL(cand));
  	
	FORR(c,cand) if(K&&num[c]==-1) {
		K--;
		cout<<"T "<<c<<endl;
		cin>>x>>y;
		num[x]=y;
		small++;
		smallS+=y;
		
		if(K) {
			K--;
			cout<<"W"<<endl;
			cin>>x>>y;
			if(num[x]==-1) {
				num[x]=y;
				large++;
				largeS+=y;
			}
		}
		
	}
	
	//cerr<<" "<<N<<" "<<small<<" "<<smallS<<" "<<large<<" "<<largeS<<endl;
	ll a=(smallS*(N-large)/small+largeS)/2;
	cout<<"E "<<a<<endl;
	
}

まとめ

交互に行うの、思い付きはしたものの確度の確証が持てず試さなかった。
一度試しておけば良かったかな…。