No.348

まずは輪を調べる.

グリッドを走査して x を探し, その x から連なっている部分をひとつの輪として番号をつけるのを繰り返す.

続いて輪の包含関係を調べる.

一番外側の . から幅優先探索で . をたどる. 途中で見つけた x が所属する輪が一番外側の輪になる. (グリッドの外周に . を足しておけば楽である) 見つけた輪はマークしておく.

続いてそのまま次の(使用していない) . を探す. 見つかった . の4近傍を探せば, マーク済みの輪が見つかるので, 外側の輪が確定する. 見つけた . から同様に幅優先探索を行い, 外側の輪のすぐ内側の輪を確定させる. 以後これを繰り返して輪の包含関係を木構造で表現する.

木構造ができたならば, 問題は次のように言い換えられる.

ある木構造があり, 各ノードには数値が設定されている. ノードに以下の条件で色をつけたとき, 色がついているノードの数値の合計の最大値はいくつか

• あるノードに色をつけたとき, その子には色をつけることができない

ノード $i$ の数値を $v_i$, ノード $i$ の子の集合を $C_i$ として, ノード $i$ に色をつけたときの合計の最大値を $A(i)$, 色をつけないときの合計の最大値を $B(i)$ とすると,

$$A(i) = v_i + \sum_{j \in C_i} B(j) \\ B(i) = \sum_{j \in C_i} \max(A(j), B(j))$$

となる. あとはこれを木の葉から順に DP で解けばいい.