難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) 未投票 (0票)

投票の分布

まだ投票はありません。

  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.50票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Merge the Islands

作成者 yura1685

難易度(作成者設定) Lv.7

難易度(投票) 未投票 (0票)

実行時間制限
2 秒
メモリ制限
512 MiB

解説

各島は「全部残す」か「全部消す」かのどちらかとしてよいです。残す島の集合を TT とすると、費用は次の 22 つの和です。

  • TT に含まれない島の面積の合計
  • TT の島どうしをつなぐのに必要な、埋め立てるマスの最小値

22 つ目は陸地のマスの重みを 00、海のマスの重みを 11 とした頂点重みつきの最小シュタイナー木です。 c(v)c(v) をマス vv の重みとします(陸地なら 00、海なら 11)。また、dp[S][v]dp[S][v] を次のように定義します。

dp[S][v]dp[S][v] = マス vv を含み、集合 SS のすべての島のマスを含む連結なマス集合のうち、含まれる海のマスの個数の最小値

島 ii に含まれるマス vv を 11 つ選び、dp[{i}][v]=0dp[\{i\}][v]=0 と初期化します。それ以外は十分大きい値(∞\infty)とします。

その後、SS を小さい順(ビット表現の昇順)に見ていき、各 SS について以下の更新を順に行います。

  1. SS を空でない真部分集合 A,S∖AA, S\setminus A の 22 つに分割し vv で合体する。

dp[S][v]=min⁡∅≠A⊊S(dp[A][v]+dp[S∖A][v]−c(v))dp[S][v] = \min_{\varnothing \neq A \subsetneq S} \bigl( dp[A][v] + dp[S \setminus A][v] - c(v) \bigr)

  1. マス vv に対し、vv と隣り合うマス uu を以下で更新する。

dp[S][u]←min⁡(dp[S][u], dp[S][v]+c(u))dp[S][u] \leftarrow \min(dp[S][u],\ dp[S][v] + c(u))

これは最短経路問題と同じ形なので、すべての vv の dp[S][v]dp[S][v] を初期距離として Dijkstra 法で処理できます。このとき、

min⁡S≠∅(min⁡vdp[S][v]+(S に含まれない島の面積の合計))\min_{S \neq \varnothing} \Bigl( \min_v dp[S][v] + (S \text{ に含まれない島の面積の合計}) \Bigr)

が求める答えとなります。計算量は O(3KHW+2KHWlog⁡(HW))O(3^KHW + 2^KHW\log(HW)) です。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。