AtCoder Regulae Contest 115 A - Two Choices
問題文
キーワード
偶奇性
解法
まず全探索を考えると、各問題の結果の全列挙にO(2^M)、(i, j)の全ペアの判定にO(N^2)、全体でO(2^M*N^2)となり間に合わない。
ここで、各問題の結果は全列挙しなくても、(i, j)のペアの判定が行える。
以下の例を考えると、(i, j)の解答が異なる問題数が奇数個である場合、偶奇性から(i, j)の正答数が等しくなる可能性が無いことが分かる。
iの1と解答した問題数をa、jの1と解答した問題数をb、i,j共に1と解答した問題数をabとすると。(i, j)の解答が異なる問題数はa + b - 2 × abと表すことができる。これが奇数であるには、以下の式が成立すれば良い。
a + b - 2 × ab ≡ 1 (mod. 2)
a + b ≡ 1 (mod. 2)
これはaとbの偶奇が異なる場合のみ成立するため、(i, j)が1と解答した問題数の偶奇が異なれば、正答数が等しくなる可能性が無いことが分かる。
この方法で愚直に判定するとO(N^2)になってしまうが、1の数が奇数のものと偶数のものを予めカウントしておき最後にかけ合わせればよく、これでO(N)で問題を解くことができた。
ACコード
感想
300点問題にしては難しい。XOR問題の典型思考である桁毎に考えるに従って、どつぼに嵌ってしまった。
