Google Code Jam 2022 Round 1B : C. ASeDatAb

これは結構しんどかった。
https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd29b

問題

8bit変数Xの初期値は非0である。
これを0にするinteractive問題である。

クエリでは、値Vを指定すると、Vをいくつかbit-rotateし、XをX xor Vで置き換える。
その後、Xのbitcountが返る。

bit-rotateの数は、悪意を持って選択されるとき、300手以内でXを0にせよ。

解法

以下Editorialの解法。

rotateして相互に変換できる整数を同一視すると、同じbitcountを持つ整数は、4bitの時で最大10である。
「現在Xとしてあり得る値の集合」は、bitcountが4の時高々2^10通りだし、他のbitcountではもっと少ない。
状態は全部で2000通りもないので、前処理として、それぞれVとして1～255を選んだ時どうなるかを列挙し、X=0から逆向きにBFSすることで最短経路を求めよう。

クエリ処理では、初手適当なVを選んでbitcountを選び、上記「現在Xとしてあり得る値の集合」を1つ求められるので、あとは前処理の結果に従い最短経路をたどるようVを選んでいこう。

int to[256];

vector<int> C[9],cand;
map<vector<int>,vector<vector<int>>> E[256];
map<vector<int>,vector<vector<int>>> RE;
map<vector<int>,int> best;
map<vector<int>,int> D;
map<vector<int>,int> from;

string tobin(int x,int len) {
	string s;
	if(x==0) return string(len,'0');
	while(x) {
		s+='0'+(x&1);
		x/=2;
	}
	if(s.size()<len) s+=string(len-s.size(),'0');
	reverse(ALL(s));
	return s;
}

vector<vector<int>> proc(vector<int> cur,int pat) {
	vector<vector<int>> V(9);
	int i;
	FORR(c,cur) {
		FOR(i,8) {
			pat=(pat>>1)|((pat&1)<<7);
			int x=pat^c;
			V[__builtin_popcount(x)].push_back(to[x]);
		}
	}
	FORR(v,V) {
		sort(ALL(v));
		v.erase(unique(ALL(v)),v.end());
	}
	return V;
}


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cout<<"00000001"<<endl;
	cin>>x;
	vector<int> cur=C[x];
	int turn=0;
	while(x) {
		turn++;
		int mi=1000;
		int id=-1;
		FOR(x,256) if(x&&to[x]==x) {
			int ma=0;
			FORR(e,E[x][cur]) {
				if(e.size()&&D.count(e)) ma=max(ma,D[e]);
				if(e==cur) ma=10000;
			}
			if(ma<mi) mi=ma, id=x;
		}
		
		cout<<tobin(id,8)<<endl;
		cin>>x;
		if(x==0) break;
		if(x==-1) exit(0);
		cur=E[id][cur][x];
	}
	cerr<<"!"<<turn<<endl;
}

void init() {
	int i,j,x;;
	FOR(i,256) {
		x=i;
		int mi=x;
		FOR(j,8) {
			x=(x>>1)|((x&1)<<7);
			mi=min(mi,x);
		}
		to[i]=mi;
		if(mi==i) C[__builtin_popcount(i)].push_back(i);
	}
	
	FOR(i,9) {
		int mask;
		FOR(mask,1<<C[i].size()) if(mask) {
			vector<int> TC;
			FOR(j,C[i].size()) if(mask&(1<<j)) TC.push_back(C[i][j]);
			FOR(x,256) if(x&&to[x]==x) {
				E[x][TC]=proc(TC,x);
				FOR(j,9) RE[E[x][TC][j]].push_back(TC);
			}
		}
	}
	
	D[{0}]=best[{0}]=0;
	queue<vector<int>> Q;
	Q.push({0});
	while(Q.size()) {
		vector<int> cur=Q.front();
		Q.pop();
		
		FORR(e,RE[cur]) if(D.count(e)==0) {
			int mi=1000;
			int id=-1;
			FOR(x,256) if(x&&to[x]==x) {
				int ma=0;
				FORR(v,E[x][e]) {
					if(v.size()&&D.count(v)==0) ma=1000;
					else if(v==e) ma=1000;
					else ma=max(ma,D[v]);
				}
				if(ma<mi) mi=ma, id=x;
			}
			if(mi<1000) {
				D[e]=mi+1;
				from[e]=id;
				Q.push(e);
			}
		}
	}
	
}

まとめ

Round1Bでこんな実装するハメになるとは…。