kmjp's blog

競技プログラミング参加記です

Codeforces #337 Div2 C. Harmony Analysis

D,Eが自信なかったけど何とか解けた。
http://codeforces.com/contest/610/problem/C

問題

2^k要素のベクトルが2^k個ある。
各要素は1か-1のいずれかであり、また異なるベクトル同士は直行している。

上記条件を満たすベクトル群の一例を答えよ。

解法

再帰的に構成できる。
2^k要素のベクトル2^k個を並べた行列をAとする。
そこから \displaystyle \left[ \begin{array}{cc} A&A\\A&-A \end{array} \right]とする行列を作ると2^(k+1)要素のベクトル2^(k+1)個を作れる。

int N;
string S[2020];

string rev(string s) {
	FORR(r,s) {
		if(r=='+') r='*';
		else r='+';
	}
	return s;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	S[0]="+";
	FOR(i,N) {
		FOR(j,1<<i) {
			S[j+(1<<i)] = S[j]+rev(S[j]);
			S[j] += S[j];
		}
	}
	FOR(i,1<<N) cout<<S[i]<<endl;
	
}

まとめ

これはすんなり。