SRM661 Div2(hard)復習

ちょっと前にSRM661 Div2のeasyとmedを復習したんですが, hardもやっと解けました.

あとこの前のTCO Round2B で無謀にもチャレンジしたせいでレートが200下がって一気に灰色まで落ちました. 泣きたい..

hard(950) : ColorfulLineGraphsDiv2

問題文のおおよその意訳

ボブは以下の２つの手順でN個の節点からなるグラフを作ろうとしている.

1からNの番号をつけた節点を用意し, それぞれの節点にはK色のうちのいずれか一色で色を塗る.
それぞれの節点i $(2\leq i \leq N)$ から, 節点iと色の異なる節点j $( j\lt i )$ に枝を張る. ただし, ボブは枝を張らないこともある.

N $(1 \leq N \leq 100)$ とK $(1 \leq K \leq 3)$ が与えられたとき, ボブが作りうるグラフの数を求め, $10^9+7$ で割った余りを答えよ.

解法

枝の張り方は色さえ決まっていたらO(N)で求められますが, そもそも色の塗り方が $K^N$ , 最悪 $3^{100}$ あるので, 塗り方ごとに枝の張り方を考えて数えるなんて事は到底無理. さてどうするか.

色々悩んだんですが, 最終的にDPになりました. 例えば, K=2として以下のようにN=2のグラフにもう一つ節点を加えてN=3のグラフを作ることを考えます.

f:id:Tawara:20150624001112p:plain

まず三つめの節点から枝を張らない場合, 好きな色の節点(赤か青)を三つ目の節点に選べるので2通り作れます. 次に三つ目の節点から枝を張る場合, 一つ目の節点に枝を張りたいなら青以外の色, すなわち赤を三つ目の節点に, 二つ目の節点に枝を張りたい場合は青を三つ目の節点に選ぶ必要があります. よって枝を張る場合も2通り作れて, 合計4通り作れます.

上のことは書いてみると結構当たり前のことなんですが, 枝を張る場合と張らない場合を分けて考えるのが一番のポイントなんじゃないかなーと思います. 三つ目の節点の色を決めてから枝を張れるかどうか考えると非常にややこしいんですが, 分けて考えてしまうととても楽です. 枝を張る先ごとに色を決めるってのが超重要.

因みに3色の場合も同様に以下のように考えられます.

f:id:Tawara:20150624003708p:plain

枝を張らない場合は3通りで, 枝を張る場合は張る先の節点以外の色を三つ目の節点の色に使えるので2*2=4通り, 合計7通りです.

もうちょっと一般的にn-1個の節点からなるグラフにn個目の節点を加えてグラフを作ることを考えると, 枝を張らない場合は単純にK通り, 張る場合は枝を張る先の節点i ( $1\leq i \leq n-1$ )ごとにn個目の節点にiと違う色すなわちK-1色のいずれかを選ぶことになるので, 作り方は

$K + (n-1)(K-1)$

通りとなります. よってボブの作りうるn個の節点からなるグラフが $a_n$ 通りだとすると, 漸化式

$a_{n+1} = a_n \lbrace K + n(K-1)\rbrace$

が成り立ちます. あとはこの式でn = 1からNまで順に求めていけば終わりです.

実装

前述の漸化式実装するだけなのでめちゃくちゃシンプルになりました.

class ColorfulLineGraphsDiv2:
    def countWays(self, N, K):
        mod = 10**9+7
        result = 1
        for i in range(N):
            result *= (K + i*(K-1)) % mod
        return result % mod

終わりに

後から聞いたんですが, Div2は制約が緩いのでここまでちゃんとやらなくても解けたらしいです(その分コードは長くなりそうですが). 逆にDiv1では制約が恐ろしいことになってて( $10^{12}$ とか), 単に漸化式作るだけでは無理だったそうな.

なにはともあれ, これでSRM661は終わりです. この調子で今までの宿題も少しずつ解いていきたい.

f:id:Tawara:20150624011117p:plain

俵言

しがない社会人が書く、勉強とかのこと。最近は機械学習や kaggle 関連がメイン。

SRM661 Div2(hard)復習

hard(950) : ColorfulLineGraphsDiv2

問題文のおおよその意訳

解法

実装

終わりに