yukicoder contest 376 E
解き方
※ ここに書く解き方は、解説に書かれている方法とは異なる サンプルにもあるが、$ N = 1 のときは全通り試すことで、条件を満たす書き込み方は存在しないことが確認できる。
よって、以降は$ N \gt 1 の場合のみを考える。
まず、$ 1 以上$ 2^{N} 以下の整数$ i それぞれについて、$ r_{i} を$ i 行目に含まれる要素のbitwise XOR とする。
また、同じく$ c_{i} を$ i 列目に含まれる要素のbitwise XOR とする。
このとき、同じ行にある$ ２ つの要素を入れ換えたときにどうなるかを考えると、$ r_{i} は変化しない。
一方で、入れ換えた要素がある列の$ c_{i} は、入れ換えた$ ２ つの要素と元の$ c_{i} の値の合わせて$ 3 つの数のbitwise XOR に変化する。
よって、$ 1 以上$ 2^{N} 以下の任意の整数$ i について$ r_{i} = c_{i} = 0 である状態から初めて、要素を入れ換えていくことを考える。
まず、$ 0 以上$ 2^{2N} 未満の整数を順番にマス目に書き込んだ状態から始める。
言い換えると、$ 1 以上$ 2^{N} 以下の任意の整数$ i と$ j について、$ a_{i,j} = (i-1) \times 2^{N} + j-1 とする。
このとき、$ 1 以上$ 2^{N} 以下の任意の整数$ i と$ j について明らかに$ r_{i} = c_{j} = 0 である。
なぜなら、同じ行に含まれる$ 2^{N} 個の要素を考えると、下記の2つを満たすからである。
$ 2^{N} 個の全ての要素について、上位$ N bit は等しい
下位$ N bit には$ 0 以上$ 2^{N} 未満の数がちょうど$ 1 回ずつ現れる
同じ列に含まれる$ 2^{N} 個の要素についても、上位$ N bit と下位$ N bit を入れ換えれば上と同じことが成り立つ。
さて、ここから要素の入れ換えを何度か繰り返し行うことで、条件を満たす書き込み方を作っていく。
まずは、これをどのような発想で実現するかを示すために、$ r_{1}, r_{2}, c_{1}, c_{2} を$ 1 にする方法について述べる。
$ c_{1} と$ c_{2} を$ 1 にするのは比較的簡単で、$ 1 以上$ 2^{N} 以下の整数$ i を適当に$ 1 つ選び、$ a_{i,1} と$ a_{i,2} を入れ換えれば良い。
なぜなら、$ a_{i,1} は偶数であり、$ a_{i,2} = a_{i,1}+1 であることから、$ a_{i,1} と$ a_{i,2} のbitwise XOR が$ 1 となるためである。
ここでは、この後の説明の都合上、$ a_{1,1} の値と$ a_{1,2} の値を入れ換えることで$ c_{1} = c_{2} = 1 となるようにしたとする。
次に、$ r_{1} と$ r_{2} を$ 1 にすることを考える。
$ r_{1} と$ r_{2} の値を変える手段として、$ 1 以上$ 2^{N} 以下のある整数$ j について、$ a_{1,j} と$ a_{2,j} の値を入れ換えることが考えられる。
しかし、最初の状態では、$ a_{1,j} と$ a_{2,j} の下位$ N bit は全く同じであるため、どの$ j を選んで入れ換えても、$ 1 にはできない。
ここで、$ c_{1} = c_{j} = 1 にするために行った操作を思い出すと、$ a_{1,1} と$ a_{1,2} の値を入れ換えている。
これにより、$ a_{1,2} と$ a_{2,2} をさらに入れ換えることで、$ r_{1} と$ r_{2} に$ 1 の位のbit を立てることができる。
ただし、これだけでは$ r_{1} = r_{2} = 2^{N}+1 となるため、$ 1 と$ 2 以外の適当な$ j に対して$ a_{1,j} と$ a_{2,j} の値をさらに入れ換える。
これにより、余計な$ 2^{N} を打ち消すことができ、$ r_{1} = r_{2} = 1 となる。（$ N \gt 1 のときはこのような$ j が存在する）
このように$ r_{1},r_{2},c_{1},c_{2} を全て$ 1 にすることができるため、後は残りの行や列も同じように入れ替え操作を行っていけば良い。
$ 1 \lt k \lt 2^{N-1} を満たす全ての$ k について、$ a_{2k-1,2k-1} と$ a_{2k-1,2k} の値を入れ換える。
$ 1 \lt k \lt 2^{N-1} を満たす全ての$ k について、$ a_{2k-1,2k} と$ a_{2k,2k} の値を入れ換える。
$ 1 \lt k \lt 2^{N-1} を満たす全ての$ k について、適当な$ j （例えば$ 1 ）を$ 1 つとり、$ a_{2k-1,j} と$ a_{2k,j} の値を入れ換える。
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
int main () {
int n = 0;
int res = 0;
res = scanf("%d", &n);
if (n <= 1) {
printf("-1\n");
return 0;
}
for (int i = 0; i < (1<<n); i++) {
for (int j = 0; j < (1<<n); j++) {
}
}
for (int i = 0; i < (1<<(n-1)); i++) {
}
for (int i = 0; i < (1<<n); i++) {
for (int j = 1; j < (1<<n); j++) {
}
printf("\n");
}
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_376_E
提出のURL 提出時刻 結果 備考
感想
D問題が解けた後、この問題が解けるまでの間に40分間以上経っているため、けっこう悩んだと思われる。
上で書いた通り、全てを$ 0 にするのは単純に順番に埋めていけばよいだけであるため簡単であり、
行か列のどちらかであれば、$ 1 にするのもそんなに難しくはなかったと思う。
両方を$ 1 にするのはなかなか難しく、$ 2 x$ 2 や$ 4 x$ 4 の場合をいろいろ試して、漸く具体例を見つけた気がする。
そこから、上の方法に辿り着いた。
このツイートに拠ると、やっぱり$ N=2 の場合（$ 4 x$ 4 の場合）について、 上に書いた要素を入れ換える方法で$ 1 にする手順をいろいろ試して見つけたらしい。