競技プログラミングのためのF#入門
解説を書いていたら通ってはいけないコードが通っているようです. 例えばこの提出コードは次の入力が通らないもののAC
になっています.
1 |
|
いろいろ考えていたら混乱してきたため, 2022-12-24時点で解説は書き切らず明確なところまでで終わりにします.
1 2 3 |
|
H,W
がともに奇数の場合の図¶1 2 3 |
|
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 |
|
まずString.concat ""
で入力の文字列を全て連結して一つの文字列にしています. Seq.groupBy id
で文字種とその数をグループ化して取得します. 最後にある文字種がいくつあるかだけを取るべくSeq.map (snd >> Seq.length)
をかけています.
(true,true)
¶小さいブロックから考えましょう.
まず(H,W) = (2,2)
とします. このときありうるのは次の形だけです.
1 2 |
|
つまり全ての文字が一致して文字数は4です.
次に(H,W) = (4,4)
とします. このときどこか一つに文字を置くと, その文字はちょうど鏡写しで必ず四つ存在します. 具体的には次のような形状です.
1 2 3 4 |
|
つまり現れる文字は常に4の倍数です. 変数m4
はいったんmod 4
でフィルターしていて, その結果から和による積み上げでs1
とs2
を作っています. これらはどちらも0
でなければなりません.
(true,false)
, (false,true)
¶これは縦・横が入れ替わっただけで本質的には同じです. 後者で考えましょう.
例えば(H,W) = (1,2)
のような具体例を考えればわかるように, 公式解説の奇数・奇数ペアのf
にあたる中心はありません. したがってただ一つだけある文字種があってはならないため, s1 = 0
の条件が必要です.
次は二つだけある文字種がどれだけあってよいかを考えます. これも小さい方から具体的に考えましょう.
(H,W) = (1,2)
で考えると次の形しかありません.
1 |
|
次に(H,W) = (1,4)
を考えると次の二通りが考えられます.
1 |
|
1 |
|
全て同じ文字種か, 文字種が二種類あって違う場合です.
ここで(H,W,Ia) = (1,4,[|"aaab"|])
という不適格な場合を考えましょう.
ここで(H,W,Ia) = (1,6,[|"aaabbb"|])
を考えます.
(false,false)
¶公式解説にあるブロックを引用します.
1 2 3 |
|