098 C - Palindromic Matrix

はじめに

解説を書いていたら通ってはいけないコードが通っているようです. 例えばこの提出コードは次の入力が通らないもののACになっています.

1
aaa

いろいろ考えていたら混乱してきたため, 2022-12-24時点で解説は書き切らず明確なところまでで終わりにします.

入出力

1
2
3
let H,W = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Ia = Array.init H (fun _ -> stdin.ReadLine())
solve H W Ia |> stdout.WriteLine

公式解説でのH,Wがともに奇数の場合の図

1
2
3
a b c b a
d e f e d
a b c b a

公式解説の補足

用語

基本的な考察

H,Wがどちらも偶数の場合

縦・横ともに回文を作るために必ず縦・横の鏡写しの分の四つ必要です. つまり全ての文字種の文字の個数は必ず4の倍数になっていなければなりません.

(H,W)がともに奇数の場合

公式解説で説明があった場合です. 先も図を引用した公式解説でいうfにあたる箇所, つまり回文(鏡映)の中心があり, ここは文字の個数が1だけあれば十分な場合があります. 他にも(H,W) = (1,3)でのabaaaaのように文字の個数が2の文字があっても許される場合があり 文字の個数が3の文字があっても許される場合があります.

少なくともHWのどちらが偶数の場合

ともに奇数の場合と違って鏡映の中心の文字が設定できないため, 文字の個数が奇数個の文字種があると破綻する場合があります. 例えば(H,W) = (1,4)の場合の"aaab"や, (H,W) = (1,6)の場合の"aaabbb"は不適です.

解説

前処理

入力の要素は自由に並べ替えられるため, 入力行列での文字の位置やどんな文字があるかは関係なく, 文字種の数と各文字の個数がいくつあるかを勘定すれば十分です.

1
  let Aq = Ia |> String.concat "" |> Seq.groupBy id |> Seq.map (snd >> Seq.length)

まずString.concat ""で入力の文字列を全て連結して一つの文字列にしています. Seq.groupBy idで文字種とその数をグループ化して取得します. 最後にある文字種がいくつあるかだけを取るべくSeq.map (snd >> Seq.length)をかけています.

(true,true)

小さいブロックから考えましょう.

まず(H,W) = (2,2)とします. このときありうるのは次の形だけです.

1
2
a a
a a

つまり全ての文字が一致して文字数は4です.

次に(H,W) = (4,4)とします. このときどこか一つに文字を置くと, その文字はちょうど鏡写しで必ず四つ存在します. 具体的には次のような形状です.

1
2
3
4
a b b a
c d d c
c d d c
a b b a

つまり現れる文字は常に4の倍数です. 変数m4はいったんmod 4でフィルターしていて, その結果から和による積み上げでs1s2を作っています. これらはどちらも0でなければなりません.

(true,false), (false,true)

これは縦・横が入れ替わっただけで本質的には同じです. 後者で考えましょう.

例えば(H,W) = (1,2)のような具体例を考えればわかるように, 公式解説の奇数・奇数ペアのfにあたる中心はありません. したがってただ一つだけある文字種があってはならないため, s1 = 0の条件が必要です.

次は二つだけある文字種がどれだけあってよいかを考えます. これも小さい方から具体的に考えましょう.

(H,W) = (1,2)で考えると次の形しかありません.

1
a a

次に(H,W) = (1,4)を考えると次の二通りが考えられます.

1
a a a a
1
a b b a

全て同じ文字種か, 文字種が二種類あって違う場合です.

ここで(H,W,Ia) = (1,4,[|"aaab"|])という不適格な場合を考えましょう.

ここで(H,W,Ia) = (1,6,[|"aaabbb"|])を考えます.

(false,false)

公式解説にあるブロックを引用します.

1
2
3
a b c b a
d e f e d
a b c b a