sio.txt

技術室奥プログラミングコンテスト#5 Day2 - I 問題「sio」（yukicoder No. 1213）解説


《問題ページ》
　https://yukicoder.me/problems/no/1213


《解説》
　N×M のマス目の中に S, I, O のミノを置いていく方法のうち、空きマスの個数が最小になる配置を「最密配置」と呼ぶことにします。さらに、最密配置のうち、I ミノの使用個数が最小の配置を「正規配置」と呼ぶことにします。つまり、正規配置での I ミノの使用個数がこの問題の答えになります。
　また、I ミノを使わない配置のうち、空きマスの個数が最小の配置を「限界配置」と呼ぶことにします。

〈補題１〉
　限界配置に I ミノをいくつか（0 個以上）置いて最密配置にできるなら、その最密配置は正規配置である。

〈証明１〉
　それはそう（I が最小 ⇔ I 以外が最大、なので）。

　次に、N×M のマス目に対し、以下の［図１］のように模様を書き込みます。
［図１］
　　┏┓┏┓┏┓┏‥‥‥
　　┗┛┗┛┗┛┗
　　┏┓┏┓┏┓┏
　　┗┛┗┛┗┛┗
　　┏┓┏┓┏┓┏
　　：
　　：
　　：
　すると、S ミノと O ミノはどのような置き方をしても ┏, ┓, ┗, ┛ をそれぞれちょうど１個ずつ覆い隠すことになります。そのため、O ミノを「各模様の個数の最小値（＝ ┛の個数）」と同じ数だけ使った配置は限界配置になります。
　O ミノを単純に格子状に並べた限界配置は、N と M が両方とも 4 で割ると 3 余る数である場合を除いて、I ミノをいくつか置くことで最密配置（そして〈補題１〉より正規配置）にすることができます（［図２］参照）（最密性：空きマスの個数が 4 個未満になることから明らか）。
　そして N と M が両方とも 4 で割ると 3 余る数である場合は、同様の配置に対して I ミノを置いても空きマスが 5 個できてしまうので、これが最密配置かどうかはまだわかりません。実は、N と M の少なくとも一方が 3 である場合はこれが最密配置になります（〈証明２〉参照）（よって〈補題１〉より正規配置）。そして、N と M がどちらも 3 より大きい場合は、［図２］のように配置することで空きマスを 1 個だけにできます（正規性：〈証明３〉参照）。

　以上。


［図２：正規配置の具体例一覧］
○偶数×偶数
　　　┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘
　　　┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘
　　　┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘

○奇数×偶数
　◇奇数×(4*W)
　　　匚ニニコ匚ニニコ匚ニニコ
　　　┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘└┘
　　　┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘└┘
　　　┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘└┘

　◇奇数×(4*W + 2)
　　　■■匚ニニコ匚ニニコ匚ニニコ
　　　┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘└┘└┘
　　　┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘└┘└┘
　　　┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘└┘└┘└┘└┘└┘

○奇数×奇数
　◇(4*H + 1)×(4*W + 1)
　　　■匚ニニコ匚ニニコ匚ニニコ
　　　冂┌┐┌┐┌┐┌┐┌┐┌┐
　　　||└┘└┘└┘└┘└┘└┘
　　　||┌┐┌┐┌┐┌┐┌┐┌┐
　　　凵└┘└┘└┘└┘└┘└┘
　　　冂┌┐┌┐┌┐┌┐┌┐┌┐
　　　||└┘└┘└┘└┘└┘└┘
　　　||┌┐┌┐┌┐┌┐┌┐┌┐
　　　凵└┘└┘└┘└┘└┘└┘

　◇(4*H + 1)×(4*W + 3)
　　　■■■匚ニニコ匚ニニコ匚ニニコ
　　　冂┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　||└┘└┘└┘└┘└┘└┘└┘
　　　||┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　凵└┘└┘└┘└┘└┘└┘└┘
　　　冂┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　||└┘└┘└┘└┘└┘└┘└┘
　　　||┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　凵└┘└┘└┘└┘└┘└┘└┘

　◇(4*H + 3)×(4*W + 3)
　　☆min{N, M} = 3
　　　■■■匚ニニコ匚ニニコ匚ニニコ
　　　■┌┐┌┐┌┐┌┐┌┐┌┐┌┐
　　　■└┘└┘└┘└┘└┘└┘└┘

　　☆min{N, M} > 3
　　　┌┐┌┐冂┌┐┌┐┌┐┌┐┌┐
　　　└┘└┘||└┘└┘└┘└┘└┘
　　　匚ニニコ||┌┐┌┐┌┐┌┐┌┐
　　　┌┐冂■凵└┘└┘└┘└┘└┘
　　　└┘||匚ニニコ匚ニニコ匚ニニコ
　　　┌┐||┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘凵└┘└┘└┘└┘└┘└┘
　　　┌┐冂┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘||└┘└┘└┘└┘└┘└┘
　　　┌┐||┌┐┌┐┌┐┌┐┌┐┌┐
　　　└┘凵└┘└┘└┘└┘└┘└┘


《補足：N と M が両方とも 4 で割ると 3 余る数である場合》
　与えられた配置に対し、その配置の空きマスに書かれている ┏, ┓, ┗, ┛ の個数を A, B, C, D とし、それらの最小値を E, 和を S とします。そして、A, B, C, D から E を引いた値をそれぞれ a', b', c', d' とし、その和を s' とします。すると、s' は空きマスの個数の下界となる、すなわち s' ≦ S が成立します。
　S ミノや O ミノを置く場合、A, B, C, D の値がそれぞれ 1 ずつ減るだけなので s' の値は変化しません。I ミノの場合は、置く向きと位置に応じて
○横向き
　◇奇数番目の行に置く：A, B の値がそれぞれ 2 ずつ減る
　◇偶数番目の行に置く：C, D の値がそれぞれ 2 ずつ減る
○縦向き
　◇奇数番目の列に置く：A, C の値がそれぞれ 2 ずつ減る
　◇偶数番目の列に置く：B, D の値がそれぞれ 2 ずつ減る
となるので、s' の値は以下のように変化します。
○E の値が変化しなかった場合：s' の値は 4 減る
○E の値が 1 減った場合：s' の値は変化しない
○E の値が 2 減った場合：s' の値は 4 増える

〈証明２：N = 3 の場合は S = 5 が最密であること〉
　M = 4*W + 3 を満たすように W をとると、ミノを１個も置いていない空配置での A, B, C, D の値は以下のように表せます。
　　A = 2 * (2*W + 2) = 2*W+1  +  3 + 2*W
　　B = 2 * (2*W + 1) = 2*W+1  +  1 + 2*W
　　C = 1 * (2*W + 2) = 2*W+1  +  1
　　D = 1 * (2*W + 1) = 2*W+1  +  0
　そして、N = 3 であることから、I ミノを縦に置くことはできません。そのため s' の値は奇数行目と偶数行目に置いた I ミノの個数のみによって決まるので、それらをそれぞれ x, y とします。すると、s' は x-y = W または x-y = W+1 の場合に最小値 s' = 5 をとります。従って、s' が空きマスの個数の下界であることから、S = 5 となる配置は最密配置となります。（証明終）

〈証明３：min{N, M} > 3 の場合の［図２］の配置の正規性〉
　N = 4*H + 3, M = 4*W + 3 を満たすように H, W をとると、空配置での A, B, C, D の値は以下のように表せます。
　　A = (2*H + 2) * (2*W + 2) = (2*H + 1)*(2*W + 1)-1  +  2*(H + 1) + 2*(W + 1)
　　B = (2*H + 2) * (2*W + 1) = (2*H + 1)*(2*W + 1)-1  +              2*(W + 1)
　　C = (2*H + 1) * (2*W + 2) = (2*H + 1)*(2*W + 1)-1  +  2*(H + 1)
　　D = (2*H + 1) * (2*W + 1) = (2*H + 1)*(2*W + 1)-1  +  1
　［図２］より S = 1 が実現できるので、最密配置であるためには s' = 1 である必要があります。そして、I ミノをどのように置いても A, B, C, D の偶奇は不変であることと、A, B, C の偶奇が一致することから、s' = 1 となるのは a' = b' = c' = 0 かつ d' = 1 となる場合に限られます。この条件を満たすためには最少でも I ミノを奇数行目に W+1 個、奇数列目に H+1 個置く必要があり、そして［図２］の配置はまさにその最少個数を実現する配置になっています。（証明終）