yukicoder contest 487 D,F問題メモ
yukicoderで構築に特化したコンテストが開かれるとのことで、参加してみた。
アカウントは作っていたものの、コンテスト参加は始めてかも。
構築はひたすら実験してそれっぽい法則性を見つけるのが楽しい。
その分、理詰めでやってないので「できる/不可能な証明」などはできてないことが多い。
D Divide and Conquer
問題文
- 3の倍数 $N$ が与えられる。
- $N \times N$ のグリッドの全てのマスに “H”, “E”, “D” のいずれか1つを書き込む。
- 以下の条件を満たしつつ書き込む方法を1つ構築せよ。
- 各文字は同じ数（$N^2/3$ 個）ずつある。
- なるべく、同じ文字が上下左右に繋がらないようにする。厳密には、
- マス $(i,j)$ に対し、そこに書かれた文字を $c_{i,j}$ で表す。
- $M_{i,j}:=「(i,j)$ から文字 $c_{i,j}$ が書かれたマスのみを伝って上下左右の移動で行き来できるマス数」とする。
- $\max_{i,j}(M_{i,j})$ を最小化する。
- 異なる文字が書かれた任意の2マス $(i_1,j_1),(i_2,j_2)$ は、$c_{i_1,j_1}$ または $c_{i_2,j_2}$ が書かれたマスのみを伝って上下左右の移動で行き来することができる。
制約
- $3 \le N \le 2025$
解法
3つめの条件は、「ある1種の文字のみによって盤面が分断されてはいけない」という条件に読み替えられる。
もし $M=\max(M_{i,j})=1$ が達成できるなら、これはペンシルパズルに出てくる「分断禁」と同じになる。
分断禁の制約下で黒マスを多く敷き詰める最大個数は既に調べている人がいて、
上記サイトによると、$M=1$ の場合、黒マスの最大数は、$N$ が3の倍数の場合 $N^2/3$ となることがわかっているらしい。
問題の条件ギリギリであるが、達成できなくは無い。
ただ、かなり不規則な埋め方となるので、たとえば、“H” について最密充填したとして、 残りのマスを “E”, “D” についても最密で埋める必要がある。それはちょっと無理そう。ちゃんと確認すると、
たとえば、角をH、その横にEを置いたとして、 ＨＥ？？... ？？？？... ？？？？... 同じ文字で分断せず、同じ文字も繋がってはいけないとなると、 連鎖的にガチガチに決まってしまい、ナナメに同じ文字が繋がるしか無くなる。 ＨＥＤＨ... ＤＨＥＤ... ＥＤＨＥ... ＨＥＤＨ... これではいつか盤面の端に到達し、分断されてしまう。
よって、$M=1$ は達成不可能。
$M=2$ を考える。この場合、いい配置があって、
★★ＥＥＤＤ★★ＥＥＤＤ ＥＤＤ★★ＥＥＤＤ★★Ｅ ※見やすさのためＨを★に置換 ★★ＥＥＤＤ★★ＥＥＤＤ ＥＤＤ★★ＥＥＤＤ★★Ｅ
2マスずつ繋げた文字を行毎に3つずつずらして繰り返すと、上手い具合に同じ文字は“島”となり、他と繋がらないようになる。
2行で1セットとして考えると、$N$ が奇数でも偶数でも1セットに出現する各文字の個数は等しいので、この繰り返しで構築できる。
奇数の場合、最終行のみＨが1個多く、Ｄが1個少ない状態となるのだが、
ＨＨＥＥＤＤＨＨＥ ＥＤＤＨＨＥＥＤＤ ＤＨＥＥＤＤＨＨＥ ↑ここ
ここはＨからＤに変えても問題なく、$M$ も増えない。これで調整できる。
ただし、サンプルにあるとおり、$N=3$ の場合のみ、盤面が小さすぎて、$M=3$ が最小となる。
F Tree on Checkerboard
問題文
- 正整数 $N$ が与えられる。
- $N \times N$ で市松模様のグリッドがある。（左上が黒）
- 黒いマスを $0$ 個以上白いマスに塗り替えて、白マス全体を“木”にする(※)ことができるか判定し、可能なら一例を示せ。
- (※)グリッドを「白マスを頂点、上下左右に隣接する白マス間に辺があるグラフ」として考え、このグラフが1つの木となる。
制約
- $2 \le N \le 2000$
解法
D問題に続き、黒マス充填が絡んでくる問題、、、
と思いきや、市松模様という制約のため単なる最密充填の法則はあんまり役に立たない、、、
と思いきや、作者の解説ではやっぱり思いっきり絡んでたという不思議な問題。
白マスが以下の2つを満たせばよい。
- 白マスがひとつながりになっている。
- 白マスによりループができてはいけない。
特に、ある黒マスを白にするとそのナナメにある黒マスは、2×2のループができてしまうため白にできなくなる。
■□★□■ ○にあった黒を白にすると □●□●□ ←●の黒マスは白にできなくなる。 ★□○□★ また、白を連結にするため、 □●□●□ ★のいずれかは白にする必要がある。 ■□★□■
ここから、条件を満たす盤面は「奇数行目または偶数行目、いずれかの黒マスは全て残る」ような状態しかあり得ないことが言える。
- 奇数行目の、ある黒マスを白にする。
- 上図のように、そのナナメ4近傍の●（偶数行目）は白にできなくなる。
- まだ全体が連結でない限り、上下左右4近傍の★（奇数行目）のいずれか少なくとも1つは白にする必要がある。
- ★のいずれかを白にすると、連鎖的に同じ状態になる。
- 既に白にしたいずれかのマスの、
- ナナメ4近傍の偶数行目は白にできない
- 上下左右4近傍の奇数行目から1つは白にしなければならない
- …という状況から脱却できない。
つまり、黒マスのうち白にできるのは、以下のような分布になっている。
偶数 奇数 ■□■□■□ ▲□▲□▲ □▲□▲□▲ □■□■□ ■: 白にできない黒マス ■□■□■□ ▲□▲□▲ ▲: 白にできる黒マス □▲□▲□▲ □■□■□ ■□■□■□ ▲□▲□▲ □▲□▲□▲
- ※偶数の盤面は■と▲を反転しても成り立つが、対称なのでとりあえずこっちで考える
- ※奇数の盤面は反転できない。▲の方を黒で残すと、上下左右それぞれから2行目（2列目）の黒は全て白にしないといけなくなるが、それだとループが発生する。
特に、偶数の盤面は1行目と1列目が一意に決まっており、それを取ったら奇数の盤面と同じになる。
また、2行目と2列目は全て白にしないといけないことが確定している。
よって、考えるのは $N$ が奇数の盤面のみでよく、以下のパターンのいずれかになる。
- 1行目・1列目を全て白にできる配置が存在する → $N,N+1$ で可能
- 1行目・1列目に黒を残せば配置できる → $N$ で可能、$N+1$ 不可能
- 配置できない → $N,N+1$ で不可能
また、白マスの条件を黒マスを主体に考えると、以下のようになる。
- 黒マスをナナメに伝って、ループしたり、どこかの壁から壁へ到達してはいけない。
- 連結条件
- 全ての黒マスは、ナナメに伝って壁に到達できないといけない。
- ループ禁止条件
- 宙ぶらりんに浮かんでいる黒マスのカタマリがあったら、その周りを1周する白マスループが存在する
これを元に、具体的な事例で、機械的に構成しやすい例を考えていく。
とりあえずは、1行目・1列目は全て白にする前提で考える。
$W=\dfrac{N-1}{2}$ とする。これは、白にできない黒マスが1列に並ぶ個数に相当する。
壁に繋げられない黒マスをなくすため、最初のいくらかは自動的に決まる。
□□□□□□□□□ □■□■□■□■□ □□❶□②□❸□… ❶は、左上の黒を孤立させないため、黒にする必要がある。 □■□■□■□■□ ②は黒にできなくなるので、 □□④□❻□□□□ ❸は、❸のすぐ左上の黒を孤立させないため、黒にする必要がある。 □■□■□■□■□ この流れは、❶と同じ行に対して右端まで続く。 □□❺□□□□□□ □■□■□■□■□ ④と❺に関しても、❶と同じ列に対して下端まで続く。 □□：□□□□□□
また、❶を含む3×3の黒マスのカタマリは、右か下の壁に繋げないといけない。
②と④は塞がれているため、❻は黒にしなくてはいけない。
ここから先はある程度の自由度がある。
いくらか方法はあり得るが、機械的に構築しやすく、 また一定の範囲を連結にできる（孤立する黒マスを発生させにくい）方法を探すと、 ジグザグに繋げていくというものが見つかる。
□□□□□□□□□□□□□□□□□ □■□■□■□■□■□■□■□■□ □□★□□□★□□□★□□□★□□ ジグザグな★によって □■□■□■□■□■□■□■□■□ 各黒マスが連結になる。 □□□□★□□□★□□□★□□□★ □■□■□■□■□■□■□■□■□ □□：□□□□□□□□□□□□□□
これで左上のカタマリを、ひとまず右側に繋げていく、ということを一旦考えてみる。
この時、$W$ が偶数と奇数で、端に到達したときの処理が異なる。
$W$ 奇数の時
最後、右上隅の■が余ってしまう。
これを（1行目に■を置かずに）壁と繋げるには、ジグザグで繋げてきた大きなカタマリも壁に繋げる以外に方法はない。
□□□□□□□□□□□□□□□ □■□■□■□■□■□■□★□ 端で★が孤立してしまう。 □□■□□□■□□□■□□□▲ これを壁と繋げるには▲に置くしか無いが、 □■□■□■□■□■□■□■□ するとジグザグに繋げてきたカタマリも壁と繋がる。 □□□□■□□□■□□□■□□ □■□■□■□■□■□■□■□ すると、▼から下方向に繋げる分は、 □□▼□□□□□□□□□□□□ 壁と繋げてはいけない。
よって、▼からは下方向にジグザグで伸ばすことはできない。下方向に端まで伸ばすと、横に伸ばした時と同様、最下段で壁と繋がり、白の連結が途切れてしまう。
下方向の展開としては、折り返して蛇腹状に連結にしていくことにする。これなら漏れなく全てを連結にしつつ、 壁と繋がることを最下段付近まで回避できる。
□□□□□□□□□□□□□□□ □■□■□■□■□■□■□■□ □□■□□□■□□□■□□□■ □■□■□■□■□■□■□■□ □□□□■□□□■□□□■□□ □■□■□■□■□■□■□■□ □□■□□□□□□□□□□□□ □■□■□■□■□■□■□■□ □□□□■□□□■□□□■□□ □■□■□■□■□■□■□■□ □□■□□□■□□□■□□□□ □■□■□■□■□■□■□■□ □□□□□□□□□□□□：□□
このジグザグ戦法は、1列で $W$ を3列分消費する。
したがって、下段に到達したとき、余りの行がいくつ発生するかは $W \mod{3}$ による。
$W$ は奇数である前提と合わせて、$\mod{6}$ が $1,3,5$ のいずれかによる。
$1 \mod{6}$
□□：□□□□□□□□□□□□ □■□■□■□■□■□■□■□ ☆は黒マスにせず、代わりに★で右の孤立黒マスを壁と繋げる。 □□□□■□□□■□□□■□□ また、▲を黒マスにすると、 □■□■□■□■□■□■□■□ 最下段で孤立する黒マスも全て壁に隣接させられる。 □□■□□□■□□□■□□□□ □■□■□■□■□■□■□■□ □□□□□□□□□□□□☆□★ □■□■□■□■□■□■□■□ □□▲□□□▲□□□▲□□□□
$3 \mod{6}$
□□：□□□□□□□□□□□□ □■□■□■□■□■□■□■□ ☆は黒マスにせず、★を黒マスとする。 □□□□■□□□■□□□■□□ また、この場合は下段で余る黒マスも全て連結になるので、 □■□■□■□■□■□■□■□ ▲で1つ壁と繋げればよい。 □□■□□□■□□□■□□□□ □■□■□■□■□■□■□■□ □□□□□□□□□□□□☆□★ □■□■□■□■□■□■□■□ □□■□□□■□□□■□□□□ □■□■□■□■□■□■□■□ □□□□■□□□■□□□■□□ □■□■□■□■□■□■□■□ □□▲□□□□□□□□□□□□
$5 \mod{6}$
□□：□□□□□□□□□□□□ □■□■□■□■□■□■□■□ ☆は黒マスにせず、★を黒マスとして右の孤立黒マスを壁と繋げる。 □□□□■□□□■□□□■□□ また、▲によってサイコロの5のようなカタマリを2個ずつ壁と繋げていく。 □■□■□■□■□■□■□■□ □□■□□□■□□□■□□□□ □■□■□■□■□■□■□■□ □□□□□□□□□□□□☆□★ □■□■□■□■□■□■□■□ □□■□□□■□□□■□□□□ □■□■□■□■□■□■□■□ □□□□▲□□□□□□□▲□□
ただし、$W \lt 6$ の時は、折り返す十分なスペースがなく、必ずしもこの方法で構築できるとは限らない。
その場合、手動で個別に考えておく。
$W$ が $5$ 以下の時、全てで条件を満たす配置は見つかるものの、 $W=3,5$（$N=7,11$）の時は、1行目・1列目に置かないと構築不可能そう。 つまり、$N=8,12$ の時は不可能である。
$W$ 偶数の時
奇数の時と異なり、右上の■も孤立せずジグザグのカタマリに繋げることができる。
いつでも壁に繋げることは可能なので、どこから壁に繋げるか、というのは最後に決めることにして、寸前の状態で保留としておく。
また、右側の上から3つめの■が連結にできないが、これも後から適当に繋げることができそうなので保留とする。
□□□□□□□□□□□□□□□□□ □■□■□■□■□■□■□■□■□ □□■□□□■□□□■□□□■□□ □■□■□■□■□■□■□■□■□ □□□□■□□□■□□□■□□□☆ □■□■□■□■□■□■□■□★□ ←★だけ浮いてるが、これは後で □□■□□□□□□□□□□□☆□☆ ☆などで繋げることはできる。
この場合、左上から下方向にもジグザグを伸ばして問題ない。
これにより、「┌」型をつくることができる。
┌ 型は、再帰的に作ることができる。
□□□□□□□□□□□□□□□□□ --- □■□■□■□■□■□■□■□■□ | □□■□□□■□□□■□□□■□□ | □■□■□■□■□■□■□■□■□ |外側の┌ □□□□■□□□■□□□■□□□□ | □■□■□■□■□■□■□■□★□ | □□■□□□□□□□□□□□□□△ --- □■□■□■□■□■□■□■□★□ | □□□□■□□□■□□□■□□□□ | □■□■□■□■□■□■□■□■□ |1つ内側の┌ □□■□□□□□□□■□□□■□□ | □■□■□■□■□■□■□■□■□ | □□□□■□□□■□□□□□□□□ --- □■□■□■□■□■□■□■□■□ | □□■□□□□□□□■□□□■□□ | あまり □■□■□★□★□■□■□■□■□ | □□□□☆□□□☆□□□□□□□▽ --- |----外側----|--1つ内側--|--あまり-|
あとは、それぞれの「┌」型、右下のあまり、および孤立頂点（★）、それぞれを壁に繋げればよい。
奇数の時と同様、$W \mod{6}$ の値が $0,2,4$ のどれかで場合分けして求められる。（割愛）
基本的には、最下段では「┌と★」を結び（☆の位置）、最右行では「★同士」（△の位置）を結ぶために黒マスを配置すると、一定の法則のもと、壁に繋げられる。
あまりは、$\mod{6}$ の値によって、孤立頂点と繋げるか、または右下（▽）で1つだけ繋げるか、いずれかで解決できる。
