Codeforces Round #530 Div2 E. Nice Table
- 問題概要
A, G, C, TからなるN*Mのテーブルに対して、最小回数の操作を施して、どの2*2のマス内に各文字が一回ずつ登場するようなテーブルに直せ。
- 解法とその証明
文字をa,b,c,dで代表させることにする。この時、
abab
cdcd
abab
cdcd
のような状態から任意の行のみについてズラすか、任意の列のみについてズラすことで、2*2のマス内に各文字が一回ずつ登場する。逆に、このようにズラした後のテーブルのみを考えればいいことも証明できる。
※任意の行についてズラすとは、上の4*4のマスを例えば以下のような模様にすることである。
abab
dcdc
baba
cdcd
<proof>
任意の行と任意の列についてズラして、どの2*2のマスにもa,b,c,dが一回ずつしか現れないと仮定する。
ここで、ある行にa,b,c,dのうち3文字以上が含まれている場合を考えれば、この行の長さ3の文字列のどこかに必ず3文字が含まれている部分が存在する。
これを例えばc1c2c3だとすれば、c2の上下にある文字は、c1c2c3に含まれない文字であることが確定する(そうでなければ、2*2のマス内に含まれない文字が存在する)。
そして、c2の上下が決まると、2*2マス内に1回ずつ現れるという仮定から、この上下の行はそれぞれ一意に定まり、これらの行も3文字を含んでいてかつ文字列として等しいことが分かる(下のテーブルを参照)。
dcdad
babcb (c1c2c3 は abc に対応する)
dcdad
従って、新たに定まった行に対しても3文字を含んでいることから、その上下の文字列も等しいことになり、結局偶数行目と奇数行目の文字列が等しいことが導かれる。
つまり、各列については違う文字を2つしか含まない。
行と列についての議論を変えても同じことが言える。また、同じ行または列に4文字以上が含まれる場合でも、長さ3の文字列を取り出せば同様のことが言える。
従って、条件を満たすテーブルは、各行または各列に2種類の文字しか含まないことが分かる(1種類の文字しか含まない時は自明にOUT)。
これは結局、一番最初に書いたテーブルについて、任意の行あるいは列についてのみズラす操作をすることで達成できる。
自分の提出コードはありませんが、snukeさんのコードが分りやすいと思ったので載せておきます。(列についての操作を、テーブルを反転させることで行についての操作に帰着させています。)
