098 C - Palindromic Matrix¶

• created: 2022-12-24 sat
• ご意見・ご要望はissue・プルリク用のGitHubまで
• 競技プログラミングのためのF#入門
• GitHub上の対応ディレクトリ
• 公式ページ
• 要点: アルゴリズムの検討

はじめに¶

解説を書いていたら通ってはいけないコードが通っているようです. 例えばこの提出コードは次の入力が通らないものの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

公式解説の補足¶

• サイズ 1, 2, 4 のグループ: 解説ページの行列でa,bは四箇所, c,d,eは二箇所, fは一箇所あります. この行列(のブロック)として何箇所に現れるかをサイズと呼んでいます.
• H,Wが奇数と奇数ではない場合, サイズ1の要素があると回文にならないため条件文に適切に反映させる必要があります.

用語¶

• a,b,cなどのアルファベットを文字種と呼ぶ. アルファベットをいくつ含むかを「文字種の数」または「文字種の個数」と呼ぶ.
  • 特に"aaabbc"という入力に対して次のように定まる.
    • 文字種はa,b,cの3個ある.
• 入力の中で各アルファベットが何文字あるかを表す数を「文字の数」または「文字の個数」と呼ぶ.
  • 特に"aaabbc"という入力に対して次のように定まる.
    • 文字aは3個.
    • 文字bは2個.
    • 文字cは1個.

基本的な考察¶

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

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

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

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

少なくともHかWのどちらが偶数の場合¶

ともに奇数の場合と違って鏡映の中心の文字が設定できないため, 文字の個数が奇数個の文字種があると破綻する場合があります. 例えば(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でフィルターしていて, その結果から和による積み上げでs1とs2を作っています. これらはどちらも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