Codeforces Round #337 (Div. 2):C問題補足 - アルゴリズマーの備忘録

こんな記事が。 pakapa104.hatenablog.com 今日少したまたまその問題について思考していたので、少し言及してみようかと思いました。

まず、求めるベクトルの個数は2^k個です。今思えば気付く人はこの時点で気付いたのかもしれません。が、取り敢えず、 k=0での文字列を"+"とします。

作ることの出来る文字列は"+*"、"++"、"*+"、"**"の4つのみ。ここで内積が0になる組み合わせは{"++","+*(*+)"}、{"**","*+(+*)"}の4通り。

"++"と"**"、"+*"と"*+"の内積が0にならないことから内積が0になる組み合わせの最大は2です。

2^n個の組み合わせが最大の時、どの2つを選んでその内積をとっても、1が2^(n-1)個、-1が2^(n-1)個含まれています。言い換えると、2つの各要素を見た時、同じものの数が2^(n-1)個、異なるものの数が2^(n-1)個入っています。

これをもう1セット後ろに追加してあげると、同じものの個数、異なるものの個数はそれぞれ2倍になり、内積は0のまま。これがk=n+1のときの回答のうちの2^n個。

ここで、2つの内片方の全要素に-1をかけて全部逆にしてみましょう。同じだったものが異なるものになり、異なったものが同じになる…-1と1の個数変わらないですね。

ということで、2^n個の各文字列に対し、+を*に、*を+に変えてあげて後ろに追加してあげる。これがk=n+1の時の残りの2^n個の答えです。合計2^(n+1)=2^k個。

再帰で解けると述べましたが、再帰じゃなくても解けます。予め"+"を文字列の配列に保存しておき、ループを回す中で、配列の全要素の文字列にこの操作を行うことでループ終了時には配列内に答えが出来ています。

2^k次元のベクトルでどの2つを選んでも内積が0になるベクトルの個数の最大値は2^kなのか。

取り敢えず先程k=1では正しいことを証明しました。では、一般の時は？<\p>

まず、基準に{1,1,1,…,1,1}は使っておきましょう。（ここがダメな時はわからないです。）

他のベクトルの-1の個数は2^k-1個になります。-1の並べ方は2^kC2^(k-1)。そんなの並べていたらキリがないです。

取り敢えず代表で左半分が1、右半分が-1のものを入れてあげます。そうすると、次に入れるベクトルは左半分のうちの半分が1で半分が-1、右半分のうちの半分が1で半分が-1となります。

これって左半分と右半分を別に解くなら既に解いてますよね？そう、k-1のパターンです。

ただし、左側と右側は関係無いです。よって元のk-1のパターンをそのままの場合はA、1を-1に、-1を1に変える場合はBとすると、AA、AB、BA、BBの中から内積が0になる組み合わせの最大値は2。

よってkの時の組み合わせの最大値をakとおくと、ak=2a(k-1)になります。a1=2より、ak=2^k通りが最大値です。

結局自分で考えて納得したかっただけです。証明がかなり雑でごめんなさい。