B - Colorful Lines(ARC130)
問題
感想
色とかグリッド上の状態をどのようにすればいいのか。ちょっと複雑で迷った。
解法
まず、一番知りたいのは最終的な「各色のカウント数」である。それを知るためには以下の二点に気を付けなくてはいけない。
同じ行、列にクエリが飛んで来たらもともと塗られていた色は塗りつぶされる。
色を塗った以降の行、列の個数を保持しておく。そうすることで最終的に塗りつぶされている個数がわかる。
愚直にやってもいいのだが、クエリを逆順にするといい感じに解決できそうなのが見える。 上の課題は順に以下のような説明がつく。
行、列にそれぞれ使用済みの番号を保持する。すると、使用済みである場合はそのクエリは結局は塗り替えられてしまう色となるため無視できる。
逆順に回すと、そのクエリを受け付けた時点の個数さえ把握しておけば塗り替えられるマス目はおのずと把握できる。
以上、パズル要素が強い問題でした。
感想
仕事終わりのモヤがかかった頭ではちと迷う。あと、この逆順という発想はすごく大事。DPでもお目にかかるので手札として持っておくべきだなと。
