| 第22回日本情報オリンピック 二次予選 |
|
|
2022年12月13日
情報オリンピック日本委員会
|
解説担当：菅井遼明
小課題 1 では H=1 が成り立っています．このとき，各マスの領域は必ず縦の長さが 1 の長方形になります．
マス目を隣接するマスの色が異なる部分で区切り，いくつかの長方形に分割します．それぞれの長方形について，その中のマスを指定したときの領域は以下のようになります．
適切に場合分けを行うことで，時間計算量 O(W) で解くことができますが，それより悪い計算量であっても得点を得ることができます．
塗りつぶしを使うときに指定する色は，1, 2, 3, 4, 5 のみ考えればよいです．よって，指定するマスと色の組み合わせを全探索し，それぞれについて得点を計算することで解くことができます．
マスを指定したとき，そのマスの領域に含まれるマスを列挙する必要があります．これを行うには，以下のような方法があります．
時間計算量 O(HW) などで解けます。
小課題 2 と比べて色の種類が増えていますが，実は考える必要のある色の個数はかなり絞り込むことができます．
具体的には，マス (x,y) を指定して塗りつぶしを使うとき，マス (x,y) の領域が大きくなる色のみ考えればよいです．よって，マス (x,y) の領域に隣接するマスの色が候補となります．
さらに，マス (x,y) に直接隣接するマスの色しか考えなくてよいことがわかります．なぜなら，マス (x,y) の領域に含まれるマスであれば，同じ色を指定したときの結果は同じになるので，離れたマスに隣接する色はそのマスを指定したときに調べることにできるからです．
上の考察により，指定するマスを定めたときの指定する色の候補は最大 4 つとなるので，適切に実装すればこれらの候補をすべて試しても制限時間に間に合います．
時間計算量は O(H2 W2) となります．
色が異なる隣接するマスの境界で長方形を区切ると，長方形は何個かの部分に分かれます．これらの部分を連結成分と呼ぶことにします．また，連結成分に含まれるマスの個数をその連結成分の大きさと呼ぶことにします．
2 つのマス A と B が同じ連結成分に含まれるとき，塗りつぶしを使う際に A を指定しても B を指定しても同じ結果になります．よって，塗りつぶしの操作は，ある連結成分と色を選び，その連結成分に含まれるマスの色をすべてその色にする，と言い換えられます．
小課題 3 では，色は 1, 2 の 2 種類しかないので，塗りつぶしをするときはその連結成分の色と異なる色を指定する場合のみ考えればよいです．このとき，指定した連結成分はその連結成分と辺で接するすべての連結成分と合体します．よって，JOI 君の得点は，指定した連結成分の大きさに，隣接する連結成分の大きさをすべて足したものになります．
連結成分に番号を振り，各マスがどの連結成分に含まれるかをあらかじめ計算します．これは幅優先探索，深さ優先探索，素集合データ構造などで行うことができます．次に，隣接する連結成分の組を列挙します．境界の両側のマスをすべて調べることで容易に実装できます．最後に，指定する連結成分をすべて試し，それぞれについて得点を計算します．
時間計算量は O(H W) となります．
小課題 4 と同様に，各マスが含まれる連結成分と連結成分同士の隣接関係を調べておきます．
ある連結成分を色 c で塗りつぶしたとき，その連結成分の大きさは，隣接する色 c の連結成分の大きさの和だけ増加します．よって，この増加量が最大になる色を選ぶのが最適です．
色を表す整数が大きいので，単純にそれぞれの色について合計を管理することはできません．連想配列を用いたり，小さい数になるように色の番号を付け替えたりするなどの工夫をすると，効率の良いアルゴリズムが得られ，正解することができます．
時間計算量は解法によりますが，典型的な実装では O(HW log HW) となります．