Official
B - Bad Mood Editorial by hos_lyric
(より詳しい解説は後日ブログで公開します)
作られるグラフは頂点数と辺数が一定の平面グラフなので,Euler の公式より連結成分数の最小・最大は面数の最小・最大に対応します.
面数を最小にするには,例えば各マスに \
を書けば外面のみになるのでよいです.
面数の最大値を考えます.\(M = 1\) または \(N = 1\) のときは外面のみになります.\(M, N \ge 2\) のとき,外周にあるマスに書く辺は高々 \(1\) 個,その他のマスに書く辺は高々 \(2\) 個の内面に寄与できることと,各内面は \(4\) 辺以上に囲まれることを用いると,内面の個数が \(\lfloor \frac14 (M N + (M - 2) (N - 2)) \rfloor\) 以下であることがわかります.
この内面数は,例えば \(i\) 行 \(j\) 列のマスには \(i + j\) が偶数のとき /
,奇数のとき \
を書けば実現できます.
posted:
last update: