Codeforces Round #337 (Div. 2) C. Harmony Analysis
問題文
http://codeforces.com/contest/610/problem/C
問題概要
以下の条件を満たすベクトルの集合の一例を示せ。
- 集合のサイズは 2k
- ベクトルの次元は 2k
- ベクトルの各成分は 1 か -1
- どの 2 つの要素を持ってきても内積が 0
ただし 0≦k≦9。
解法
k の解が分かっていれば、そこから k+1 の解を構成できる。
たとえば、k=2 での解が {A, B, C, D} だとすると、 k=3 での解は {A.A, B.B, C.C, D.D, A.-A, B.-B, C.-C, D.-D} になる。何故これで構成できるのかは、以下の等式を考えると分かる。
- (A.A, B.B)=(A, B)+(A, B)=0
- (A.-A, B.B)=(A, B)+(-A, B)=(A, B)-(A, B)=0
- (A.-A, B.-B)=(A, B)+(-A, -B)=(A, B)+(A, B)=0
- (A.A, A.-A)=(A, A)+(A, -A)=(A, A)-(A, A)=0
Codeforces Round #337 (Div. 2) C. Harmony Analysis
もう少し早く気付きたかった。