Educational Codeforces Round 48 (Rated for Div. 2) - D. Vasya And The Matrix
概要
n行m列の行列で、毎行のxorの結果はa[1~n]、毎列のxorの結果はb[1~m]として与えられる。これを満たす行列を存在するのならば、YESと答えて、1つ構築せよ。存在しないのならば、NOとだけ答えよ。
制約： 1 <= n, m <= 100, 0<= a[i], b[i] <= 10^9 出力する行列の各要素は2*10^9以下。
ACするまで
1. ずっと考えて、うまく1点だけピックアップするようにやろうとするも、厳しい。
2. 構築のテンプレとして、想定解がスカスカの疎行列であることがよくあるので、対角成分しかない行列を考える->むりぽ
3. 1h経って何も見えないので、ギブアップ
4. 解説解法、奇想天外ながらも確かに典型で疎行列を考えるパターンだった。(対角成分を詰めるパターンではないけど)。この解法を本記事の中では天才解法という。
5. さらに言うと、天才解法以外にも、凡人解法が存在していて、地道に桁ごと見ていくことで、構築できるみたい。
6. 両方ACした。
考察
凡人解法
以下のtsubasaさんが書いたブログを大いに参考にしました。こちらも合わせてごらんください。
emtubasa.hateblo.jp
XORの問題なので、「困難は分割せよ」の通りに、
bit演算は、当然ながら桁ごとが独立して扱える！
構築可能条件は、天才解(公式解答)と同じです。(構築可能条件を確証があまり持てないながらも、意外には思いつくとは思う)現時点では、この構築可能条件は、「これを満たすならば構築不可能」とはまだ言い切れないので、必要条件にとどまっています。
ひとまず、行のXORと列のXORが一致しないのを除外してみます。
そうすると、下図のように、「(着目した桁において)bitが立ってる数の個数」が行と列において、かならず偶奇が一致するとわかります。(XORの偶奇を考えればわかる)
さて、偶奇が一致した時に、うまく行列の成分に1を配置して、条件を満たす者が作れるのでしょうか？
奇数個一致する場合と、偶数個一致する場合と場合分けをして、奇数個の場合は簡単です。偶数個の場合は、様々な考え方がありますが(参考にしてもらったtsubasaさんは別のもっと実装が軽い方法でやっていました)、僕のこの方法が一番思いつきやすいのではないでしょうか？
奇数個は、着目してる成分の行も列もその桁で立っていたら、立てることにします。(最終的に、どの行も列も、奇数個立つので問題ない)
ただし、0個立ってる場合は例外処理をしましょう。
逆に、行と列で、その桁においての立ってるbit数の偶奇が一致しないのならば、どうがんばっても構築できません。
見ての通り、仮の判定条件とした(行のXORと列のXORが一致)もので、作れる、作れないがきれいに分かれています。よって、判定条件は必要十分であったとわかります。
