予選B-D 天下一芸術
部分点1
バックトラックなどの枝刈り探索で、ペンキの塗り方をすべて試せば良い。
部分点2
「ある番号のマスに対する塗り方は、その番号のマスすべてを含む最小の長方形だけを考慮すれば良い」ことに着目する。
つまり
- 各塗料を塗る回数は1回だけなので、その1回で塗りたい番号のすべてのマスを含んでいなければならばい。
- 最小の長方形よりも大きく塗ったとしても、その外側は後から塗りつぶさなきゃいけない場所になるだけなので、塗らなくても構わない。
なので、「ある番号のマスに対する塗り方は、その番号のマスすべてを含む最小の長方形だけを考慮すれば良い」
さらに、塗る順番が決まっている、同濃度で塗れないといった、各領域どうしの関係をあらかじめ調べておけば、探索の計算時間はマス目の大きさに影響されない。
これらを考慮して、塗料の順序を枝刈り探索をしていけば、部分点2の制約でも時間内に解くことができる。
満点解法
各領域の塗る順序に関する依存関係を無閉路有向グラフ(DAG)に落としこんで、各濃さごとの塗りの状態でメモ化する動的計画法(DP)で解けば良い。