ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.348 カゴメカゴメ

★4昇格.Union-find,木DP,DFSなど色々な要素が入っている問題でためになるのだけれど,実装がかなり難関.個人的には今までyukicoderの問題の中で最凶クラスの実装難の問題でした.


方針:輪の包含関係を根付き木で表現する.Union-findなどで各輪の強さを求め,あらかじめ構築しておいた木において『ある輪と,その輪のすぐ外側にある輪の両方を使用することは出来ない』という条件を満たすようにDPを行う.

Step 1:根の'.'が飛び地になることがあるので,周囲をもう一周'.'で囲む.サンプル4にこの操作をすると下の図のようになる(縦と横が2マスづつ増える).こうすることで一番外側の'.'はすべて共有されることになる.

f:id:ctylim:20160227173727p:plain:w300

Step 2:Union-findを使って'.'のつながり,'x'のつながりを一つの代表元にまとめる.上の図の丸で囲ったところが各素集合の代表元(の例)である.ここで注意すべき部分は'x'は周囲8方向に存在する'x'とマージできるが,'.'は上下左右の4方向の'.'としかマージできないことである.時間計算量: O(NM)

Step 3:根を左上の'.'を含む'.'のつながりとし,そこから一枚づつ'.', 'x', '.', 'x', ...と交互に剥がしていくようにグリッド全体を走査しながら木を作っていく(dfs).木に追加した素集合を訪れたかどうかはメモしておく(vis).ここでも'x'の内側にある'.'を探すときは周囲8方向をチェックすれば良いが,'.'の内側にある'x'は上下左右の4方向しかチェックできない.サンプル4では下のような木ができる.青が'.'で赤が'x'に対応する.時間計算量: O(NM\log (NM))

f:id:ctylim:20160227173658p:plain:w300

Step 4:赤のノード('x')のみを辿ってDPを行う(dfs_m).一例として,配列dp[i][0]には「マス目iにある輪より内側にある輪のみを使ったときの最大の強さ」,dp[i][1]には「マス目iにある輪を使い,かつ内側にある輪を使ったときの最大の強さ」を記録しておく方法がある.時間計算量: O(素集合の数)

サンプル4での計算例(更新則):

 dp[28] [0] = \max (dp[80][0], dp[80][1]) + \max (dp[89][0], dp[89][1])

 dp[28][1] = dp[80][0] + dp[89][0]

最後にノード0の子の強さをすべて足しあわせることで答えとなる.

yukicoder No.348


BFSもいいけどDFSの実装のコンパクトさが体感できたので,徐々に再帰は慣れていきたい.