KLab株式会社 採用情報

予選B-D 天下一芸術

部分点1

バックトラックなどの枝刈り探索で、ペンキの塗り方をすべて試せば良い。

部分点2

「ある番号のマスに対する塗り方は、その番号のマスすべてを含む最小の長方形だけを考慮すれば良い」ことに着目する。

つまり

なので、「ある番号のマスに対する塗り方は、その番号のマスすべてを含む最小の長方形だけを考慮すれば良い」

さらに、塗る順番が決まっている、同濃度で塗れないといった、各領域どうしの関係をあらかじめ調べておけば、探索の計算時間はマス目の大きさに影響されない。

これらを考慮して、塗料の順序を枝刈り探索をしていけば、部分点2の制約でも時間内に解くことができる。

満点解法

各領域の塗る順序に関する依存関係を無閉路有向グラフ(DAG)に落としこんで、各濃さごとの塗りの状態でメモ化する動的計画法(DP)で解けば良い。