日本情報オリンピック 第3回 女性部門

2023年1月24日
情報オリンピック日本委員会

解説

解説担当：菅井遼明

小課題 1

小課題 1 では H = 1 が成り立っています．このとき，JOIG 王国は標高が等しいマスからなる縦の長さが 1 の長方形に分かれます．

長方形の個数が 2 個以上である場合は，隣接する長方形の境界に運河を建設することで，平地の個数を長方形の個数と同じにすることができます．

長方形の個数が 1 個である，つまりすべてのマスの標高が等しい場合は，どのように運河を建設しても平地の個数は 2 個になります．

小課題 2

標高が異なる隣接するマスの境界でマス目を区切ると，マス目は何個かの部分に分かれます．これらの部分を連結成分と呼ぶことにします．また，連結成分に含まれるマスの個数をその連結成分の大きさと呼ぶことにします．

H = 2 のとき，各連結成分の形は非常に限られています．上下を確認しながら左から右へ標高が同じマスを辿っていくことで，JOIG 王国に含まれるマスを連結成分に分解することができます．

また，運河を建設したとき，運河が連結成分の中を通過しているとき 2 個，そうでないとき 1 個の平地ができます．具体的には，連結成分の左端が左から L 列目，右端が左から R 列目であったとき，x = L, L + 1, …, R - 1 のときは 2 個の平地が，そうでないときは 1 個の平地ができます．

累積和を用いることで，それぞれの x について平地の個数を高速に求めることができます．

時間計算量は O(W) となります．

小課題 3

x としてありうる値を全探索します．運河の左側と右側それぞれについて，平地の個数を足し合わせればよいです．

平地の個数を調べるには，幅優先探索 (BFS) を行う，深さ優先探索 (DFS) を行う，素集合データ構造 (Union-Find 木，DSU) を用いるなどの方法があります．

時間計算量は O(HW²) となります．

小課題 4

x = 1, 2, …, W - 1 の順に運河の左側の平地の個数を調べることを考えます．各平地に含まれるマスの集合を管理する素集合データ構造を持ちます．

x を増やしたとき，x - 1 列目と x 列目の境界，x 列目内の境界に対応する更新を行うことで，平地の個数を高速に調べることができます．

運河の右側の平地の個数についても，x = W - 1, W - 2, …, 1 の順に同様に求めることができます．

素集合データ構造の実装により，時間計算量は O(HW α(HW)) や O(HW log HW) となります．