C: Palindromic Matrix - CODE FESTIVAL 2017 qual A

code-festival-2017-quala.contest.atcoder.jp

要素がアルファベットの行列が与えられる。各行及び各列が回文になるように要素を並び替えたい。可能かどうか判定せよ。

まずすべての要素について、a～zの登場回数をmod4でカウントしておく。

そして行及び列の偶数奇数で場合分けする。両方共奇数の場合はmod4 = 1 or 3の文字がちょうど1個必要。また、真ん中の文字を覗いたカウントで、mod4 = 2の文字はそれぞれ真ん中の列及び真ん中の行で使われ、ちょうどh+w-2個必要である。残りはすべてmod4 = 0にっている必要がある。偶数の場合はすべてがmod 4 = 0になるなど、場合分けがあるがあとは同様に可能。O(HW)。