https://codeforces.com/contest/1099/problem/E
'A', 'G', 'C', 'T'からなる$n\times m$配列が与えられる。これを書き換えて、すべての$2\times2$領域について同じ文字が含まれないようにするための最小書き換え文字数を求めよ。
実験をすると、行または列のどちらかは"AGAGAGAGA"のように2種類の文字を交互に繰り返さなくてはならないことがわかる。よって、最初の行または列に使う文字を全探索すればその他の行および列については貪欲に構成すればよく、その最小コストが答えになる。
これは本当に反省すべきで、きちんと実験をしなくてはならない。