Codeforces #712 Div1 : B. 3-Coloring

また変わった感じのadaptive。
https://codeforces.com/contest/1503/problem/B

問題

N*Nの盤面を使ったadaptive問題である。
この盤面を3色で塗り分ける。

先手は1色を指定するので、後手はそれ以外の2色のいずれかを選び、まだ塗ってないマスを1つ塗る。
途中、同じ色のマスが隣接したら後手の負けである。

自分が後手を取る場合、全マスを塗り切る手順を答えよ。

解法

盤面を市松模様状に白黒の2種類に分ける。

• 先手が色1を指定した場合
  • 白マスが余っていたら、色2で塗る。余ってなければ黒マスを色3で塗る。
• 先手が色2を指定した場合
  • 黒マスが余っていたら、色1で塗る。余ってなければ白マスを色3で塗る。
• 先手が色3を指定した場合
  • 黒マスが余っていたら、色1で塗る。余ってなければ白マスを色2で塗る。

色1は黒マスにしか来ないので絶対に衝突しない。
色2は白マスにしか来ないので絶対に衝突しない。
色3は白黒両方のマスに来る可能性があるが、色3が塗られるときは白黒いずれかが他の色ですでに埋まった状態なので、色3が白黒両方のマスに塗られることはない。

int N;
int A[101][101];

void ans(int y,int x,int v) {
	A[y][x]=v;
	cout<<v<<" "<<(y+1)<<" "<<(x+1)<<endl;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<int,int>> C[2];
	FOR(y,N) FOR(x,N) C[(y+x)%2].push_back({y,x});
	FOR(i,N*N) {
		cin>>x;
		if(x==1) {
			if(C[1].size()) {
				ans(C[1].back().first,C[1].back().second,2);
				C[1].pop_back();
			}
			else {
				ans(C[0].back().first,C[0].back().second,3);
				C[0].pop_back();
			}
		}
		else if(x==2) {
			if(C[0].size()) {
				ans(C[0].back().first,C[0].back().second,1);
				C[0].pop_back();
			}
			else {
				ans(C[1].back().first,C[1].back().second,3);
				C[1].pop_back();
			}
		}
		else if(x==3) {
			if(C[0].size()) {
				ans(C[0].back().first,C[0].back().second,1);
				C[0].pop_back();
			}
			else {
				ans(C[1].back().first,C[1].back().second,2);
				C[1].pop_back();
			}
		}
	}
	
}

まとめ

本番も時間こそかかってないけどちょっと苦戦してるな。