提出 #27697706

---

ソースコード 拡げる

#include <vector>
#include <iostream>
using namespace std;

vector<int> find_grouping(int N) {
	// Find one way to divide {1, 2, ..., N-1} into 3 groups
	if (N % 3 == 2) {
		return vector<int>(); // does not exist, returns empty vector
	}
	int A = N * (N - 1) / 6;
	vector<vector<vector<bool> > > dp(N, vector<vector<bool> >(A + 1, vector<bool>(A + 1, false)));
	dp[0][0][0] = true;
	for (int i = 1; i <= N - 1; ++i) {
		for (int sum1 = 0; sum1 <= A; ++sum1) {
			for (int sum2 = 0; sum2 <= A; ++sum2) {
				if (sum1 >= i && dp[i - 1][sum1 - i][sum2] == true) {
					dp[i][sum1][sum2] = true; // put i into group 1
				}
				if (sum2 >= i && dp[i - 1][sum1][sum2 - i] == true) {
					dp[i][sum1][sum2] = true; // put i into group 2
				}
				if (dp[i - 1][sum1][sum2] == true) {
					dp[i][sum1][sum2] = true; // put i into group 3
				}
			}
		}
	}
	if (dp[N - 1][A][A] == false) {
		return vector<int>(); // does not exist, returns empty vector
	}
	vector<int> g(N);
	int curi = N - 1, cursum1 = A, cursum2 = A;
	while (curi >= 1) {
		if (cursum1 >= curi && dp[curi - 1][cursum1 - curi][cursum2] == true) {
			g[curi] = 1;
			cursum1 -= curi;
		}
		else if (cursum2 >= curi && dp[curi - 1][cursum1][cursum2 - curi] == true) {
			g[curi] = 2;
			cursum2 -= curi;
		}
		else {
			g[curi] = 3;
		}
		--curi;
	}
	return g;
}

int main() {
	int N;
	cin >> N;
	vector<int> g = find_grouping(N);
	if (g == vector<int>()) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				char color = '?';
				if (g[j] == 1) color = 'R';
				if (g[j] == 2) color = 'B';
				if (g[j] == 3) color = 'W';
				cout << color;
			}
			cout << endl;
		}
	}
	return 0;
}

提出情報

ジャッジ結果