キーエンスプログラミングコンテスト2021 D - Choosing Up Sides (700)

コンテスト中の考察

$ _{2^n}C_2 = \frac{2^n(2^n-1)}{2} = 2^{n-1}(2^n-1)

1試合毎に$ 2^{n-1}のペアができるため、最小で$ 2^n-1が必要そうでかつこれでできそう

ABの数が合うパターンは$ _{2^n-1}C_{2^{n-1}}通りあるがこれを試すのは明らかに間に合わなさそう

$ N=1だと"AB"、$ N=2だと"ABAB","ABBA","AABB"

ここから以下のようにすると$ N=kの場合のパターンができそう

$ N=k-1のパターンを2度繰り返したものを追加

$ N=k-1のパターンにそのABを逆転したものを追加

前半半分をA、後半半分をBにしたものを追加

よって$ N=1の場合から順に作ることができる

これは$ O(2^nn^2)よりは小さいはずなので$ N \le 8)なら間に合う

コンテスト後の考察

$ N=k-1で条件を満たすパターンが作れているとする

この時、$ 2^{k-1}-1回同じチームになり、$ 2^{k-1}回違うチームになっている

$ N=kでは上のコンテスト中の考察の方法でパターンを作る(最後のAAAABBBBパターンを除いて考える)

前半$ 2^{k-1}同士と後半$ 2^{k-1}同士の中でそれぞれ同じチームになる回数は単純に$ N=k-1の場合の倍なので$ 2^k-2回ずつで違うチームになるのは$ 2^k回ずつ

ある前半$ 2^{k-1}の一つとある後半$ 2^{k-1}の一つが同じチームになる回数は後半部分は明らかにABの出現回数が同じになるようになっていることから$ 2^k-1回ずつで違うチームになるのも同様

最後に前半半分をA、後半半分をBにしたものを追加を追加すると

前半$ 2^{k-1}同士と後半$ 2^{k-1}同士の中でそれぞれ同じチームになる回数が1回増加

ある前半$ 2^{k-1}の一つとある後半$ 2^{k-1}の一つ違うチームになる回数が1回増加

以上からどんな組み合わせでも$ 2^{k}-1回同じチームになり、$ 2^{k}回違うチームになることが分かる