Typical DP Contest C - トーナメント

アルゴリズムが難しいというより計算量解析が難しい。

tdpc.contest.atcoder.jp

解法

セグ木っぽく区間に番号を割り振る。こうすると左の子と右の子のインデックスを求めるのが簡単になる。

f:id:pekempey:20160204220630p:plain

考えるべきは次の DP。

  • dp[ i ][ j ] := 区間 i でプレイヤー j が勝ち残る確率

区間 k の DP テーブルは左の子の区間で誰が勝つか、右の子の区間で誰が勝つかを全通り試せば更新できる。


Typical DP Contest C - トーナメント

再帰関数の中で $O(n^2)$ の処理が回っているが計算量は大丈夫だろうか。

こういうコードの計算量の解析は分類定理(master theorem)が有効。

$$ T(n)=2T(n/2)+O(n^2) $$

なので、分類定理より $O(n^2)$ と即座にわかる。詳しくは『アルゴリズムイントロダクション第1巻』を参考。


分類定理というのは

$$ T(n)=aT(n/b)+O(f(n)) $$

の形の漸化式を解く定理である。大雑把に言うとこのタイプの漸化式の解は

  • $T(n)=\max(O(n^{\log_b a}),O(f(n)))$
  • ただし $n^{\log_b a} = \Theta(f(n))$ のときは $T(n)=O(f(n)\log n)$

になる。実際にはこの通りに計算すると間違った解が求まる可能性があるが、正しい解との差は log 1個程度なことが多いので気にすることはない。

例 1

$$ T(n)=7T(n/3)+O(n^2) $$

$O(n^{\log_3 7})$ よりも $O(n^2)$ の方が支配的なので、$T(n)=O(n^2)$。

例 2

$$ T(n)=7T(n/3)+O(n) $$

$O(n^{\log_3 7})$ の方が $O(n)$ より支配的なので、$T(n)=O(n^{\log_3 7})$。

例 3

$$ T(n)=2T(n/2)+O(n) $$

ともに$O(n)$ なので、$T(n)=O(n \log n)$。

例 4

$$ T(n)=2(T/2)+O(n \log^k n) $$

実は $T(n)=O(n \log^{k+1} n)$ になる。分類定理が解けるクラスの漸化式ではないが、よく見るので一応書いておいた。

分類定理は今日あった期末試験に出ました。