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^2/3$ となることがわかっているらしい。
問題の条件ギリギリであるが、達成できなくは無い。
ただ、かなり不規則な埋め方となるので、たとえば、“H” について最密充填したとして、 残りのマスを “E”, “D” についても最密で埋める必要がある。それはちょっと無理そう。ちゃんと確認すると、
たとえば、角をH、その横にEを置いたとして、 ＨＥ？？... ？？？？... ？？？？... 同じ文字で分断せず、同じ文字も繋がってはいけないとなると、 連鎖的にガチガチに決まってしまい、ナナメに同じ文字が繋がるしか無くなる。 ＨＥＤＨ... ＤＨＥＤ... ＥＤＨＥ... ＨＥＤＨ... これではいつか盤面の端に到達し、分断されてしまう。
よって、$M=1$ は達成不可能。
$M=2$ を考える。この場合、いい配置があって、
★★ＥＥＤＤ★★ＥＥＤＤ ＥＤＤ★★ＥＥＤＤ★★Ｅ ※見やすさのためＨを★に置換 ★★ＥＥＤＤ★★ＥＥＤＤ ＥＤＤ★★ＥＥＤＤ★★Ｅ
2マスずつ繋げた文字を行毎に3つずつずらして繰り返すと、上手い具合に同じ文字は“島”となり、他と繋がらないようになる。
2行で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のループができてしまうため白にできなくなる。
■□★□■ ○にあった黒を白にすると □●□●□ ←●の黒マスは白にできなくなる。 ★□○□★ また、白を連結にするため、 □●□●□ ★のいずれかは白にする必要がある。 ■□★□■
白を連結にするためには2マス上下左右にある黒マス（★）のいずれかを白にせざるを得なくなり、
その黒マスのナナメにあるマスもまた白にできなくなる。
連鎖的に、奇数行、または偶数行、どちらかしか白マスにできなくなる。（もう一方の黒マスはまるまる残る）
偶数 奇数 ■□■□■□ ▲□▲□▲ □▲□▲□▲ □■□■□ ■: 白にできない黒マス ■□■□■□ ▲□▲□▲ ▲: 白にできる黒マス □▲□▲□▲ □■□■□ ■□■□■□ ▲□▲□▲ □▲□▲□▲
- ※偶数の盤面は■と▲を反転しても成り立つが、対称なのでとりあえずこっちで考える
- ※奇数の盤面は反転できない。▲を残すと、連結条件から外側から2行目・2列目の黒は全て白にしないといけなくなるが、それだとループが発生する。
偶数の盤面を見ると、連結条件から、2行目・2列目は全て白にしないといけなくなる。
また、2行目・2列目が白であるという前提の元、1行目と1列目を取ったら、奇数の盤面と同じになる。
よって、考えるのは $N$ が奇数の盤面のみでよく、以下のパターンのいずれかになる。
- $N$ 奇数で、1行目・1列目を全て白にできる方法が存在する → $N,N+1$ で可能
- 1行目・1列目に黒を残せば埋められる → $N$ で可能、$N+1$ 不可能
- 埋められない → $N,N+1$ で不可能
また、白マスの条件を黒マスを主体に考えると、以下のようになる。
- 黒マスをナナメに伝って、ループしたり、どこかの壁から壁へ到達してはいけない。
- 連結条件
- 全ての黒マスは、ナナメに伝って壁に到達できないといけない。
- ループ禁止条件
- 宙ぶらりんに浮かんでいる黒マスのカタマリがあったら、その周りを1周する白マスループが存在する
これを元に、具体的な事例で、機械的に構成しやすい例を考えていく。
とりあえずは、1行目・1列目は全て白にする前提で考える。
$W=\dfrac{N-1}{2}$ とする。これは、白にできない黒マスが1列に並ぶ個数に相当する。（下例では $W=4$）
□□□□□□□□□ □■□■□■□■□ □□❶□②□❸□… ❶は、左上の黒を繋げるため、黒にする必要がある。 □■□■□■□■□ ②は黒にできなくなるので、 □□②□□□□□□ ❸は、左上の黒を繋げるため、黒にする必要がある。 □■□■□■□■□ この流れは、❶と同じ行・列に対して端まで続く。 □□❸□□□□□□ □■□■□■□■□ □□：□□□□□□
また、❶を含む黒マスのカタマリは右か下の壁に繋げないといけない。 この時、漏れなくカタマリを繋げていく方法として、ジグザグに繋げていくというものがある。
□□□□□□□□□□□□□□□□□ □■□■□■□■□■□■□■□■□ □□★□□□★□□□★□□□★□□ ジグザグな★によって □■□■□■□■□■□■□■□■□ 各黒マスが連結になる。 □□□□★□□□★□□□★□□□★ □■□■□■□■□■□■□■□■□ □□：□□□□□□□□□□□□□□
これで繋げていくのを一旦考えてみる。
この時、$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$ の時は、折り返す十分なスペースがなく、必ずしもこの方法で構築できるとは限らない。
その場合、手動で個別に考えておく。
この時、$N$ が奇数なら全て構築できるものの、 $W=3,5$（$N=7,11$）の時は、1行目・1列目に置かないものは構築不可能そう（証明はできてない）ことが分かる。
$W$ 偶数の時
最後までサイコロの“5”の目のようなカタマリを作ることができ、 即座に壁とくっつけないといけないカタマリはない。
□□□□□□□□□□□□□□□□□ □■□■□■□■□■□■□■□■□ □□■□□□■□□□■□□□■□□ □■□■□■□■□■□■□■□■□ □□□□■□□□■□□□■□□□☆ □■□■□■□■□■□■□■□★□ ←★だけ浮いてるが、これは後で □□■□□□□□□□□□□□☆□☆ ☆などで繋げることはできる。
したがって、左上から右と下にジグザグを伸ばして、「┌」型をつくることができる。
┌ は、最も外側を除いた残りから、再帰的に作ることができる。
□□□□□□□□□□□□□□□□□ --- □■□■□■□■□■□■□■□■□ | □□■□□□■□□□■□□□■□□ | □■□■□■□■□■□■□■□■□ |外側の┌ □□□□■□□□■□□□■□□□□ | □■□■□■□■□■□■□■□★□ | □□■□□□□□□□□□□□□□△ --- □■□■□■□■□■□■□■□★□ | □□□□■□□□■□□□■□□□□ | □■□■□■□■□■□■□■□■□ |1つ内側の┌ □□■□□□□□□□■□□□■□□ | □■□■□■□■□■□■□■□■□ | □□□□■□□□■□□□□□□□□ --- □■□■□■□■□■□■□■□■□ | □□■□□□□□□□■□□□■□□ | あまり □■□■□★□★□■□■□■□■□ | □□□□☆□□□☆□□□□□□□□ ---
あまりがどのような形になるかも、$W \mod{6}$ の値が $0,2,4$ のどれであるかで場合分けしてもとめられる。（割愛）
また、この構築方法では、端に孤立している黒マス★が残る。これらも壁に繋げることを忘れてはならない。
基本的には、最下段では「┌と★」を結び（☆の位置）、最右行では「★同士」（△の位置）を結ぶために黒マスを配置すると、一定の法則のもと、壁に繋げられる。
