pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

もう少し早く気付きたかった。