Google Code Jam 2019 Round 2 : B. Pottery Lottery

ローカルテストできたから通った気がする。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051679/00000000001461c8

問題

100人の人がいて、それぞれ1～100の番号が振られており、自身の番号と同じ番号のコインを持っているものとする。
20個の花瓶があり、100名が順次どこかの花瓶に自分のコインを入れていく。

最後、20個の花瓶のうち最もコイン数の少ない花瓶が1つである場合、その花瓶内のコインの番号を持つ人が勝者となる。
ここで、自分は100番であるとする。
前の99名は、等確率でランダムに20個の花瓶のいずれかにコインを入れる。
99名の各人がコインを入れた後、毎回いずれかのズルを行うことができる。

• 任意の花瓶に任意の番号のコインを1枚加える
• 任意の花瓶の中身のコインの番号を知る

最適手を打ったとき、自分を90%以上の確率で勝者とせよ。
なお、以下の場合負けとなる。

• コイン数最小の花瓶に自分の番号のコインがない
• コイン数最小の花瓶が2個以上タイである
• コイン数最小の花瓶に、同じ番号のコインが2個以上あることが発覚した（他の花瓶の中身はチェックされない）

解法

色々な解法がある。自分の本番の解法は91%でギリギリ通ったが、以下は95%ぐらい通る。

• 最初60手は、後ろ10個の花瓶に大量に適当なコインを投下する。
• 次の10手で、前半10個の花瓶の中身を取得する。最小の花瓶を最後の勝者に定める。
• 次の39手で、2番手以下に適当なコインを投下する。
• 最後に自分の番で最小の花瓶に100番のコインを入れる。

int num[201];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	ZERO(num);
	int add=0;
	int nex=1,tar;
	priority_queue<pair<int,int>> PQ;
	int border=60;
	for(i=1;i<=99;i++) {
		cin>>x;
		assert(x==i);
		if(i<=border) {
			cout<<(i%10)+11<<" "<<100<<endl;
		}
		else if(i<=border+10) {
			cout<<(i-border)<<" "<<0<<endl;
			cin>>x;
			num[i-border]=x;
			FOR(j,x) cin>>y;
			
			
			if(i==border+10) {
				tar=1;
				for(j=2;j<=10;j++) if(num[j] <= num[tar]) tar=j;
				for(j=1;j<=10;j++) if(j!=tar) PQ.push({-num[j],j});
			}
			
		}
		else {
			x=PQ.top().second;
			
			PQ.pop();
			cout<<x<<" "<<100<<endl;
			num[x]++;
			PQ.push({-num[x],x});
			
		}
		
		
	}
	
	cin>>x;
	assert(x==100);
	cout<<tar<<" 100"<<endl;
	
}

まとめ

Acでも通ってたらしいけど、まぁこれはこれで通ってよかったね。