Codeforces #635 Div1 D. Yui and Mahjong Set

Interactiveどうも苦手だ。
https://codeforces.com/contest/1336/problem/D

問題

変則的な麻雀を考える。
1～Nのいずれかの値を持つ数牌を考える。初期状態で同じ値の牌は最大N個しか持ちえない。

ここで初期状態でNの値が与えられる。ただし手持ちの牌の数や牌の値はわからないので、これを当てたい。
クエリとして、1～Nのいずれかの牌を1つ追加し、追加後の順子・刻子の組み合わせの数を答えてもらう、ということを最大N回行える。
初期状態の牌を答えよ。

解法

数値iの牌の数をC[i]とする。今値xの牌を加えたとき、刻子と順子の数の変化を見ると

• 刻子は、C[x]!=0であればC(C[x],2)個増加する
• 順子は、C[x-2]*C[x-1]+C[x-1]*C[x+1]+C[x+1]*C[x+2]個増加する。

刻子については1手で1個値を特定できてオトクだが、C[x]=0のケースは2個追加しないとこれを達成できない。
そこで、どこか1回同じ場所に2個牌を追加することで、初期状態でC[x]=0の場合でもそのC[x]を特定し、その分追加できない値が1か所生じるので、順子の結果で穴埋めすることを考える。

そこで、N-1、N-2、…、3,1,2,1とN-1から降順で処理して、1の周辺だけちょっと変則的に処理しよう。
1を2回足すのでC[1]を特定でき、その前後の順子の結果から、C[2]、C[3]…と順次特定できる。
C[N-2]とC[N-1]の数がわかれば、最初のN-1とN-2を追加したときの順子の数の変化から、C[N]も求められる。

int N;
int ON=0;
int ret[101]={0,2,1,3,0,2};
int A[101]={};
int H;
vector<vector<int>> hist;
int T[202];

pair<int,int> pat() {
	int i;
	int a=0,b=0;
	for(i=1;i<=ON;i++) a+=ret[i]*(ret[i]-1)*(ret[i]-2)/6;
	for(i=1;i+2<=ON;i++) b+=ret[i]*ret[i+1]*ret[i+2];
	return {a,b};
}
pair<int,int> pat2() {
	int i;
	int a=0,b=0;
	for(i=1;i<=ON;i++) a+=A[i]*(A[i]-1)*(A[i]-2)/6;
	for(i=1;i+2<=ON;i++) b+=A[i]*A[i+1]*A[i+2];
	return {a,b};
}



pair<int,int> ask(int v) {
	int a,b;
	cout<<"+ "<<v<<endl;
	ret[v]++;
	if(ON) {
		auto x=pat();
		a=x.first;
		b=x.second;
	}
	else {
		cin>>a>>b;
	}
	hist.push_back({a,b,v});
	H=hist.size();
	return {a,b};
}

void pop() {
	A[hist.back()[2]]--;
	H--;
	hist.pop_back();
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,201) T[i]=i*(i-1)*(i-2)/6;
	
	if(ON) {
		N=ON;
		auto a=pat();
		x=a.first;
		y=a.second;
	}
	else {
		cin>>N;
		cin>>x>>y;
	}
	hist.push_back({x,y,0});
	for(x=N-1;x>=3;x--) ask(x);
	ask(1);
	ask(2);
	ask(1);
	for(i=2;i<=103;i++) if(hist[H-1][0]-hist[H-2][0]==T[i]-T[i-1]) {
		A[1]=i;
		break;
	}
	x=hist[H-1][1]-hist[H-2][1];
	pop();
	y=hist[H-1][1]-hist[H-2][1];
	if(hist[H-1][0]-hist[H-2][0]==0) {
		pop();
		if(hist[H-1][1]-hist[H-2][1]==0) {
			A[2]=0;
		}
		else {
			A[2]=1;
		}
	}
	else {
		for(i=2;i<=103;i++) if(hist[H-1][0]-hist[H-2][0]==T[i]-T[i-1]) {
			A[2]=i;
			break;
		}
		pop();
	}
	A[3]=x/(A[2]+1);
	pop();
	A[4]=(y-(A[1]+1)*(A[3]))/(A[3]);
	for(x=3;x<=N-2;x++) {
		assert(x==hist[H-1][2]);
		y=hist[H-1][1]-hist[H-2][1];
		A[x+2]=(y-A[x-2]*A[x-1]-A[x-1]*A[x+1])/A[x+1];
		pop();
	}
	
	while(H>1) pop();
	
	cout<<"! ";
	for(i=1;i<=N;i++) cout<<A[i]<<" ";
	cout<<endl;
}

まとめ

こういうのどうやれば得意になるんだろ。