2016-02-04から1日間の記事一覧

Typical DP Contest C - トーナメント

アルゴリズムが難しいというより計算量解析が難しい。 tdpc.contest.atcoder.jp 解法 セグ木っぽく区間に番号を割り振る。こうすると左の子と右の子のインデックスを求めるのが簡単になる。 考えるべきは次の DP。 dp[ i ][ j ] := 区間 i でプレイヤー j が…

Typical DP Contest D - サイコロ

tdpc.contest.atcoder.jp 解法 積の倍数判定の場合は、gcd(a0 a1 ... an-1,D)=D なら a0 a1 ... an-1 は D の倍数という判定法が使える。 これを使うと dp[ 振ったサイコロの個数 ][ gcd(サイコロの目の積,D) ] := 確率 ができる。状態数は D の約数のうち素…