yukicoder : No.3246 80% Accuracy Calculator

問題文を見落として手間取った…。
https://yukicoder.me/problems/no/3246

問題

整数変数A,B,Cがある。Cは0である。

以下のクエリを8888回まで用いて、どこかの変数に、初期値A,Bに対するA*Bの値を書くんした状態にせよ。

• 1つ変数を指定し、その値を問い合わせる。80%の確率で正確な値を返し、20%の確率で適当な値を返す。
• 3つ変数a,b,cを指定し、cにa+bを代入する。ただし、a,bはcと同じであってはならない。また、80%の確率で正確な加算を行い、20%の確率で適当な値を代入する。

解法

まず1つ目のクエリについては、同じクエリを連打し、1つの値の登場頻度がある程度大きくなったら、その値が正しい値と考えて(確率的に)問題ない。
2つ目のクエリに対しても、加算のたびに前者のクエリを使い、加算がちゃんと行えてるか確認すればよい。

あとはBの初期値を覚えておき、Aをバイナリ法の要領で加算していこう。
a := A*2^n
b := A*(Bの下位n bit)
c := 一時変数

とすると以下をnの小さい順に行っていけばよい。

• Bのn bit目が立っている場合、c =a+bとしたうえで、bとcの役割を入れ替える
• c = a+aとしたうえで、aとcの役割を入れ替える

const int K=20;
string S="ABC";
int num[3];

int ask(int x) {
	map<int,int> M;
	int i,y;
	FOR(i,K) {
		cout<<"? "<<S[x]<<endl;
		cin>>y;
		assert(y>=0);
		M[y]++;
		if(M[y]>=10) return y;
	}
	assert(0);
	return -1;
}

void add(int a,int b,int c) {
	int exp=num[a]+num[b];
	assert(a!=c);
	assert(b!=c);
	int x;
	while(1) {
		cout<<"+ "<<S[a]<<" "<<S[b]<<" "<<S[c]<<endl;
		cin>>x;
		assert(x==0);
		if(ask(c)==exp) {
			num[c]=exp;
			break;
		}
	}
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	num[0]=ask(0);
	num[1]=ask(1);
	int B=num[1];
	int C=num[0]*num[1];
	
	int cur=0,ret=2,tmp=1;
	FOR(i,10) {
		if(B&(1<<i)) {
			B^=1<<i;
			add(cur,ret,tmp);
			swap(ret,tmp);
		}
		if(B==0) break;
		add(cur,cur,tmp);
		swap(cur,tmp);
	}
	assert(num[ret]==C);
	cout<<"! "<<S[ret]<<endl;
}

まとめ

1つ目のクエリの実行回数の調整に手間取った。