Codeforces Round #５３３ B. Dima and a Bad XOR
今まで参加したコンテストやイベントのことしか記事にしてなかったのでたまには個人的に面白いと思った問題を記事にしようと思います。
問題概要（自分で和訳したので誤っている可能性あり）
各項が非負整数のn*mの行列aが与えられる。数列c1,c2,...,cnであってa(1,c1) xor a(2,c2) xor ... a(n,cn) > 0となる数列はあるか？なければ”NIE"をあれば出力し、あれば”TAK"、そして数列c1,c2,...,cnを出力せよ。（文字を80％より小さくする方法がわからなかったのでa(i,j)でaのi行j列目を表しています。リンク先の問題本文を読んだ方がわかりやすいかも）
着目点
xorを取って>0、と言っているが非負整数でxorを取ると0より小さくはならないので≠0と言い換えられる。a(1,c1) xor a(2,c2) xor ... a(n,cn)が0になったとするとこのうちの整数を一つ変えるとxorを取った値が0ではなくなる（これはある数xとxorを取って0になる数はx自身以外に存在しないことを考えるとわかりやすい（？））。
解法
まずは数列cを1,1,...1としてxorをとる。これが0でなければそのまま出力。0であって全ての行が単一の整数で構成されている行だったら”NIE"、そうでなければ複数の整数で構成されている行のうち1つをx行目とするとcx=1をa(x,1)≠a(x,cx)となるcxに変更する。
