Codeforces #978 : Div2 D2. Asesino (Hard Version)

これまた不参加の回。
https://codeforces.com/contest/2022/problem/D2

問題

N人の人がおり、それぞれはナイト・嘘つき・詐欺師のいずれかである。
ただし、詐欺師は1人だけしかいない。

以下のクエリを用いて、詐欺師を特定せよ。

• i番の人に、「jj番の人はナイトか？」と聞く。

ナイトは、ナイト・嘘つきのことを正しく判定し、詐欺師に対しナイトと判定する。
嘘つきと詐欺師は、ナイト・嘘つきのことを誤って判定し、詐欺師に対しナイトではないと判定する。

解法

2人で交互に判定しあうと、詐欺師がいない限り両者の意見は一致する。
よって、クエリ2回で2名を判定できる。つまりN人をN手で判定できる。

問題はNが奇数の時だが、Nが大きい間は2人ずつ減らし、N=5の時はうまく場合分けすれば5手で判定することができる。

int T,N;
int ask(int a,int b) {
	cout<<"? "<<a<<" "<<b<<endl;
	cin>>a;
	return a;
}

void ans(int a) {
	cout<<"! "<<a<<endl;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		while(N>5) {
			x=ask(N-1,N);
			y=ask(N,N-1);
			if(x!=y) {
				if(ask(N-2,N)==ask(N,N-2)) ans(N-1);
				else ans(N);
				break;
			}
			N-=2;
		}
		if(N>5) continue;
		if(N==3) {
			if(ask(1,2)==ask(2,1)) {
				ans(3);
			}
			else if(ask(1,3)==ask(3,1)) {
				ans(2);
			}
			else {
				ans(1);
			}
		}
		if(N==4) {
			x=(ask(1,2)==ask(2,1));
			y=(ask(1,3)==ask(3,1));
			if(x==0&&y==0) ans(1);
			if(x==0&&y==1) ans(2);
			if(x==1&&y==0) ans(3);
			if(x==1&&y==1) ans(4);
			
		}
		if(N==5) {
			int a12=ask(1,2);
			int a31=ask(3,1);
			x=a12+ask(2,3)+a31;
			if((3-x)%2==0) {
				if(ask(1,4)==ask(4,1)) {
					ans(5);
				}
				else {
					ans(4);
				}
			}
			else {
				if(a12==ask(2,1)) {
					ans(3);
				}
				else if(a31==ask(1,3)) {
					ans(2);
				}
				else {
					ans(1);
				}
			}
		}
		
	}
}

まとめ

こういう細かい場合分けが必要な問題、一発で正答できる気がしないな。