狠狠撸

E問題 ?解説 ?
「天下?一魔法使い」
天下?一プログラマーコンテスト2015 ?予选础

問題概要
円周上にN個の点が等間隔で並んでいる ?
点をつないでいくつかの多?角形を作る ?
?各点はちょうど1つの多?角形に含まれなければならない ?
?多?角形の頂点数は全てK以上でなければならない ?
?多?角形がひとつながりになっていなければならない ?
このような点のつなぎ?方は何通りか？ ?
3 ?≦ ?N ?≦ ?400 ?
3 ?≦ ?K ?≦ ?N

部分点 ?1
N ?≦ ?50 ?
N/3 ?< ?K

部分点 ?1
N/3 ?< ?K ?
→ ?多?角形は?高々2つしか作れない ?
N ?< ?3K ?であり、多?角形を3つ以上作るには点が?足りない

部分点 ?1
多?角形が１つの場合：１通り ?
多?角形が２つの場合： ?
「K頂点以上の多?角形を２つ作る場合の数」?
（ひとつながりでないものも含めたもの） ?
から ?
「２つの多?角形が交差しない場合の数」 ?
を引く

部分点 ?1
?K頂点以上の多?角形を２つ作る場合の数 ?
N個の点を2つのグループに分ける場合の数と同じ ?
?‘A?’と?’B?’を合計N個並べる場合の数 ?/ ?2 ?と同じ?
（２つのグループは区別しないため） ?
?‘A?’の個数を ?K ?から ?N-‐??K ?まで試し、その和を取る ?
?‘A?’の個数がa個のときは、N ?C ?a ?
コンビネーションの計算にはパスカルの三?角形などを?用いれば良良い

部分点 ?2
N ?≦ ?50 ?
この部分点は、計算量量が多項式ならば満点解法よりも多少効
率率率が悪い部分があっても取ることができます

満点解法
N ?≦ ?400 ?
O(N^3) ?のアルゴリズムなら満点を取ることができます

満点解法
「ひとつながりかどうかを無視した場合の数」 ?
から ?
「ひとつながりでない場合の数」 ?
を引く

満点解法
説明のため、点の個数が ?i ?個のときの答えを ?
A[i] ?
としておきます（忘れないでください） ?
（つまり、この問題?自体の答えは ?A[N] ?になります）

ひとつながりかどうかを無視した場合の数
N個の点をいくつかの「K個以上の点を含むグループ」に分
ける場合の数と同じ ?
dp[i] ?= ?i ?個の点をいくつかの「K ?個以上の点を含むグルー?
?　?　?　 ? ?プ」にわける場合の数 ?
というDPを計算する

DPの計算
dp[i] ?= ?i ?個の点をいくつかの「K ?個以上の点を含むグルー?
?　?　?　 ? ?プ」にわける場合の数 ?
追加する多?角形は真北北の点を含むようにすると、このように
重複なく計算できる ?
dp[0]
?=
?1
?
for
?(i
?:
?0
?~
?N)
?for
?(j
?:
?K
?~
?N)
?{
?

?
?dp[i+j]
?+=
?dp[i]
?*
?(i+j-?‐1)
?C
?(j-?‐1)
?
}

ひとつながりかどうかを無視した場合の数
説明のため、 ?
G[i] ?= ?dp[i] ?
?　?　 ? ? ? ?= ?i ?個の点をいくつかの「K ?個以上の点を含むグル?
?　?　?　 ? ? ? ?ープ」にわける場合の数 ?
としておきます（忘れないでください）

真北北の点を含む連結成分に注?目して分割する ?
連結成分：ひとつながりになっている極?大な部分集合
ひとつながりでない場合の数

各部分をそれぞれ円に直してみる ?

?赤：A[6] ?
?青：G[3] ?
緑：G[4] ?
灰：G[6] ?
これらを掛け合わせたものがこの分割での場合の数 ?
（?赤のみひとつながりで、それ以外はなんでもよい）

ある分割についての場合の数は ?
?A[(真北北の点を含む連結成分に含まれる点の個数)] ?
?分割された各部分について?
?　G[(その部分に含まれる点の個数)] ?
を掛け合わせたもの ?
各分割に対してこれを?足し合わせれば、ひとつながりでない
場合の数が求まる

DP[i][j] ?= ?i ?個の点のうち ?j ?個の点が真北北の点を含む連結成?
?　?　?　?　?　分に含まれる場合の数 ?/ ?A[j] ?
= ?i ?個の点のうち ?j ?個の点が真北北の点を含む連結成分に含まれるような分割につ?
?　いて、真北北の点を含む連結成分以外のつなぎ?方の個数を?足し合わせたもの ?
というDPを計算する
DP
DP[0][0]
?=
?1
?
for
?(i
?:
?0
?~
?N)
?for
?(j
?:
?0
?~
?i)
?{
?

?
?for
?(k
?:
?0
?~
?N)
?{
?

?
?
?
?DP[i+k+1][j+1]
?+=
?DP[i][j]
?*
?G[k]
?

?
?}
?
}

?Gを前計算する ?
?DPを前計算する ?
?Aを?小さい?方から計算していく ?
?A[N] ?を出?力力する
答えの求め?方
A[0]
?=
?1
?
for
?(i
?=
?1~N)
?{
?

?
?A[i]
?=
?G[i]
?

?
?for
?(j
?:
?1~(i-?‐1))
?{
?

?
?
?
?A[i]
?-?‐=
?DP[i][j]
?*
?A[j]
?

?
?}
?
}

?Gを前計算する?　?　?　?　?　?　?　?　← ?O(N^2) ?
?DPを前計算する?　?　?　?　?　?　?　 ?← ?O(N^3) ?
?Aを?小さい?方から計算していく?　← ?O(N^2) ?
となり、O(N^3) ?なので満点を得ることができる
計算量量

狠狠撸

天下一プログラマーコンテスト2015 予選A E問題解説

More Related Content

天下一プログラマーコンテスト2015 予選A E問題解説

狠狠撸

天下一プログラマーコンテスト2015 予選A E問題 解説

More Related Content

天下一プログラマーコンテスト2015 予選A E問題 解説

天下一プログラマーコンテスト2015 予選A E問題解説

天下一プログラマーコンテスト2015 予選A E問題解説