けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

O(2^n)から計算量を減らす問題

テーマ解説記事

この記事は、Competitive Programming Advent Calendar Div2013の22日目の記事として書きました。

今年は「ナイーブにやるとO(2^n)になりそうな問題の計算量を落とす系の問題」を集めました。例えば、区間スケジューリング問題は、ナイーブに全探索しようと思うとn個の区間に対してそれぞれ「選ぶ」or「選ばない」の2択を行うO(2^n)の解法になりますが、Greedyアルゴリズムによって効率的に解くことができます。

このような問題のうち、特に、多項式時間や擬多項式時間で効率よく解けるものを中心に集めました。難易度としてはSRM DIV2 Hard、SRM DIV1 Medium程度のものが多いです。なお、個々の問題や解法についての説明はとてもあっさりしたものになっております。

また、個人の趣味の記事ということでインフォーマルな書き方をしております。競技プログラミング界隈の人々に少しでも楽しんで頂けたら嬉しいです。


0. まえがき

ところで、ナイーブにやるとO(2^n)な問題というのは多岐に渡ります。最適化問題であれば

　　min　 f(x1, x2, …, xn)
　　s.t.　　xi = 0 or 1
　　　　　様々な制約条件

という形の問題はこの枠組みで捉えられますし、数え上げ問題であれば

　　find　 (x1, x2, …, xn)の組の個数
　　s.t.　　xi = 0 or 1
　　　　　様々な制約条件

の形になります。
この「様々な制約条件」の形によって、想定解法がDPだったり、連立一次方程式だったり、最小カットだったりします。

そこで逆に、ナイーブO(2^n)な問題に対する解法を色々と整理しておくと、そのような問題に挑みやすくなるのではないかと考えました。「こういう制約の形だから最小カットだなー」とか、あるいは反対に、「最小カットになるように制約を弄れないかなー」という感じです。僕に知っている範囲で、過去にコンテストで出題された問題たちを題材に種々の解法をまとめてみます。


1. DP
　　
2. 連立1次方程式
　　
3. 最小カット
　　
4. 最大独立集合問題
　　
5. Greedy
　　
6. その他
　　


1. DP

O(2^n)から計算量を落とす競プロの問題と言えば、圧倒的にDPが多いように思います。とりわけSRM DIV2 Hardでは、「O(2^n)だなーと思ったら、前から順番に見ていくDP！」と意識するだけでも、2割くらい解ける気がします！

何故、O(2^n)な問題がDPで解けることが多いかを考えてみると、「現在の選択が遠い未来にまで直接的には影響を及ぼさない」という状況によって、自然に前から順番に見ていくDPがフィットするケースが多いです。

逆に、前から順番に見ていくDPに帰着しようと思うと、予めn個のモノをソートしておくパターンがあります。


ナップサック問題

ナイーブO(2^n)な問題をDPによって効率的に解く問題と言えば、ナップサック問題が頻繁に取り上げられます。

概要
n個の品物があり、それぞれ重さと価値がwi, viとなっている。
これらの品物から重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めよ。

制約
・1 ≦ n ≦ 50
・1 ≦ wi, vi ≦ 100
・1 ≦ W ≦ 10000

Examples
0) 
 n = 6
 (w,v) = {(2,3), (1,2), (3,6), (2,1), (1,3), (5,85)}
 W = 8

 Returns : 91　（2, 5番の品物を選んだときが最大です）

この問題は例えば

dp[i+1][j] := i番目までの品物から重さの総和がj以下となるように選んだときの価値の総和の最大値

としてDPを構成して解くことができます。計算時間は、O(nW)となります。詳しくは、診断人さんの記事を参照してもらえらばと思います。


重み付き区間スケジューリング問題

上のナップサック問題に対するDP解法は、O(2^n)より速いですが擬多項式時間になっております。一方、「前から順番に見ていくDP」によって本当に多項式時間にできる問題もあります。

概要
n個の区間[si, ti]（i = 1, 2, …, n）があり、それぞれwiの価値を持っている。
これらから区間の重なりを生じないように区間を選んで、その価値の総和を最大化せよ。

制約
・1 ≦ n ≦ 100000
・1 ≦ si < ti ≦ 10^9
・1 ≦ wi ≦ 10^9

Examples
0) 
 n = 5
 s = {1, 2, 4, 6, 8}
 t = {3, 5, 7, 9, 10}
 w = {3, 10, 6, 20, 8}

 Returns : 30　（区間2, 4）

この問題は例えば

dp[i+1] := i番目までの区間についての価値の総和の最大値

としてDP遷移式を作ることができます。計算時間はO(n^2)になります。


類題

幾つか個人的に印象に残った問題を挙げたいと思います。

「前から順番に見ていくDP」の部分がメインとなっている問題を幾つか並べました。このタイプで問題を難しくしようと思うと、予め何らかの基準によってn個のモノをソートさせたり、DP遷移自体に別のDPが必要だったり、といったパターンが多く見られました。


2. 連立1次方程式

最近、連立1次方程式を想定解法とする問題がとても多いですね。連立1次方程式で解ける問題についてpepsin-amylaseさんの記事がとても詳しいです。ここでは、特に、ライツアウト系の問題を挙げます。この問題が連立1次方程式で解ける鍵は、「制約条件が1次方程式の形で書けること」にあると言えます。なお、解法の細かい部分はpepsin-amylaseさんの記事を参照して下さい。


ライツアウト問題

今回はAOJ1308 Awkward Lightsを紹介します。

概要
m×nのライツアウトの初期盤面が与えられる。
あるマスを押すと、「押したマス、及び、そのマスからマンハッタン距離がdであるマス」
の状態が反転する。
ライツアウトの初期盤面が与えられて、全てOFFにすることができるかどうか判定せよ。

制約
・1 ≦ m, n ≦ 25
・1 ≦ d ≦ m + n

Examples
0) 
 n = m = 5, d = 1
 1 1 1 0 1
 0 1 0 1 0
 1 0 1 0 1
 0 1 0 1 0
 1 0 1 0 1

 Returns : 0（FALSE）

1)
 n = m = 5, d = 2
 0 0 0 0 0
 0 0 0 0 0
 0 0 1 0 0
 0 0 0 0 0
 0 0 0 0 0

 Returns : 1（TRUE）

この問題に限らずライツアウト系の問題は

・各マスに変数xiを割り当て、「押す」= 1、「押さない」= 0 とする
・制約条件は、xiについてのmod.2の連立1次方程式の形で書ける
・その方程式を掃き出し法を用いて解く

という解法で解けることが多いです。


類題

連立1次方程式で解く類題です。必ずしも「0 or 1」の形ではないですが、考え方が良く似た問題たちです。

3. 最小カット

次に最小カットです。最近、診断人さんが放送されたテーマです。O(2^n)な問題を最小カットに帰着できる問題は、制約条件がとても特殊な形をしています。

　　min　 f(x1) + f(x2) + … + f(xn)
　　s.t.　　xi = 0 or 1
　　　　　様々な制約条件

において、制約条件が全て

　　　xi ≦ xj（言い換えると、xi = 1 ⇒ xj = 1）

の形をしていれば最小カットによって解くことができます。

詳しく書いて行くと大変長くなってしまうため、具体的にどのように最小カットに帰着させるかは

・CKomakiさんの記事
・診断人さんの放送スライド

を参照して頂ければと思います。


コメント

上では、制約条件を「xi ≦ xj」と書きました。この制約式であれば、構成したグラフの枝に負の容量があっても各枝に一律に値を足してあげればよいです。

一方、もう少し制約の形を一般化して、

　　　xi = 1 であるにも関わらず xj = 0 となる場合には、値pのペナルティを与える

としても最小カットで解ける場合があります（xi ≦ xjの制約は、ペナルティ値pをINFにしたものと見ることができます）。この場合は、枝に負の容量がある場合の対処方法は職人技になります。


類題

診断人さんの生放送で紹介された問題と多数被っていますが、幾つか類題を挙げたいと思います。

4. 最大独立集合問題

グラフの最大独立集合問題もナイーブにやるとO(2^n)になる問題とみなせます。
一般にはNP-hardですが、特殊なグラフであれば多項式時間で解ける場合が多々あります。
この機会にそれらをまとめて整理してみたいと思います。

なお、最大独立集合問題が解けるグラフのクラスとして、パーフェクトグラフと呼ばれるクラスが知られています。
2分グラフ、区間グラフなどはパーフェクトグラフに含まれています。


フローに帰着するパターン

フロー絡みで出題されるパターンは、

  • 2分グラフ上の最大独立集合問題 -> 「頂点数 - 最大マッチング」が答え
  • 推移率を満たすDAG上の最大独立集合問題 -> Dilworthの定理により「DAG最小パス被覆」に等しい

が代表的です。
出題例として以下の問題があります。

その他

他にも、暗黙に最大独立集合問題とみなせる問題も多数出題されています。

  • 区間グラフ上の最大独立集合問題（つまり、区間スケジューリング問題）
  • 推移閉包を取った有向ツリー上の最大独立集合問題

5. Greedy系

Greedy系はむしろO(n!)から落とす問題が多い印象ですが、O(2^n)から落とす問題も色々あります。


区間スケジューリング問題

上に重み付き区間スケジューリング問題を挙げましたが、重みが無ければもっと効率よくGreedyに解くことができます。

n個の区間[si, ti]（i = 1, 2, …, n）がある。
これらから区間の重なりを生じないように最大個数の区間を選べ。

制約
・1 ≦ n ≦ 100000
・1 ≦ si < ti ≦ 10^9

Examples
0) 
 n = 5
 s = {1, 2, 4, 6, 8}
 t = {3, 5, 7, 9, 10}

 Returns : 3　（区間1, 3, 5）
マトロイド

　そして、O(2^n)から計算量を落とすGreedy系問題と言えば、やはりマトロイドが大きな枠組みを与えています。詳しくは、去年の記事を参照して頂ければと思います。


その他

　SRM328 DIV1 Medium BlockEnemy辺りが結構面白いと感じたので紹介してみます。ツリー上でmultiway cutを求める問題です。

n頂点から成るツリー（無向グラフ、各枝は重み付き）と、頂点集合の部分集合Sが与えられる。
今、ツリーから幾つかの枝を取り除くことによって、
Sのどの2頂点を選んでもそれらが分断されている状態にしたい。
このような枝の取り除き方のうち、取り除いた枝の重みの総和が最小となるものを求めよ。

制約
・2 ≦ n ≦ 50

Examples
0) 
 n = 5
 tree = {"1 0 1", "1 2 2", "0 3 3", "4 0 4"}（枝(1, 0)の重みが1、枝(1, 2)の重みが2、…）
 S = {2, 3, 4}

 Returns : 4　（枝(1, 0)と枝(0, 3)を取り除く）

Sをより細かく分断できるような枝のうち、最小重みの枝をカットすることを繰り返すGreedyで解くことができます。


6. その他

最短路問題、最小カット問題

最短路問題や最小カット問題も、条件を満たす枝集合を求める問題なので、ナイーブにやるとO(2^|E|)になる問題と言えます。

マトロイド交差問題

共通の台集合を持つ2つのマトロイドがあったとき、両方のマトロイドで独立な最大サイズの集合を求める問題です。2分グラフの最大マッチング問題、有向全域木問題、カラフル全域木問題、全域木をパッキングする問題などがマトロイド交差問題の枠組みに入ります。

種々の指数時間アルゴリズム

本記事では、主に多項式時間や擬多項式時間に落とせる問題を扱いましたが、指数の底を小さくする問題も色々あります。wataさんのスライドがとても面白いです。


7. おわりに

ここまで読んで頂いてありがとうございます。僕は「多項式時間で効率良く解ける問題たちがどのような絡繰りで効率的に解けるのか？」を考えるのが好きで、このような記事を書くことにしました。とても雑多な内容になってしまいましたが、少しでも楽しんで頂けたら嬉しいです。それでは、皆様よいお年を！