Codeforces Global Round 14 1515E - Phoenix and Computers

問題

要約

$1$番から$N$番までのコンピュータが1列に並んでいます。

最初全てのコンピュータはOFFになっており、コンピュータの電源を任意の順番でONにしていきます。

ここで、両隣のコンピュータがONならば、真ん中のコンピュータも自動的にONになります。

全てのコンピュータをONにする方法は何通りあるでしょうか? 素数$M\ $で割った余りを求めてください。

補足

  • 左端・右端のコンピュータは「両隣」がないので自動的にONになりません
  • 電源をONにできるのは、電源がOFFのコンピュータだけです。

制約

  • $3\leq N \leq 400$
  • $10^8\leq M\leq 10^9$

考察

切り口

数え上げ問題なので、とりあえず以下を考えてみます。

  • 組み合わせ(${ }_nC_k = \frac{n!}{k!(n-k)!}$)

    • combinationの数学的性質と、計算のしやすさを利用する。
    • $n$が$10^6$程度までなら、事前計算で$O(1)$で求まる
  • 場合分け・DP

    • 問題を適切に分割する。dpなら状態間の推移も考える。
    • bitDPや木DP、分割統治など派生いろいろ。累積和やFFT、in-placeなどで計算量削減が求められる場合もある
  • 順列

    • 順列固有の性質を利用する。N個のアイテムを順番に選ぶ場合など。
  • 全探索

    • dfsなどでありうる状況を全列挙する。制約が軽く、答えの個数を直接数えられるなら有効。

基本的にはこの中から使えそうなものを選んでいく形でいいでしょう。

しかし、今回の問題ですが、どれを使えばいいのか微妙に分かりにくいです。

$N\leq 400$という制約の軽さはDPっぽいですが、全てのコンピュータが同一の性質を持っているので${ }_nC_k$でまとめて解けそうな雰囲気もあります。

$1$から$N$を順番に選んでいくのは順列らしさもあります。全探索は流石に無理そうなので除外。

制約が軽い=その制約でないと解けない とは限らないので、可能性は除外せず、できるところから考えていきます。

基本的な考察

このタイプの方針が分かりにくい問題は、問題に関する基本的な性質を考えるところから入ると良さそうです。

まず、どのコンピュータを手動でONにするかを決め打ってみます。

手動でONにするコンピュータをo, 自動でONにするコンピュータをxとします。

ここで、xが2連続することはありえないことが分かります。コンピュータが自動でONになるには、両隣のコンピュータがONになる必要があるからです。

xが2連続する場合、一方が自動でONになるためにはもう一方が先に自動でONにならなければならないため、どちらも先にONになれず矛盾してしまいますね。

また、右端と左端がxになることも、問題の制約からありえません。

逆に, oは何連続しても問題なさそうですね。少なくとも、oが連続している部分を左端から順にONにしていけば全て手動でONにできます。

よって条件は

  • xが連続せず、両端にも出現しないこと

となります。

ありうるパターンの1例はoooxoxoooxooxoooとなります。

ここで、あるパターンを異なる2つのパターンに分割することを考えてみます。(DPなどで問題を分割する必要性を見越しておく)

このとき、分割した2つのパターンはできるだけ独立な挙動をしてほしいです。

なので、試しにxを基準に分割を行います。

例) oooxoxoooxooxooooooxoxooo + x + ooxooo

このように分割すると、左側に対する操作によって右側のコンピュータが自動でONになったり、逆に右側に対する操作で左側のコンピュータが自動でONになったりしないので、安全に分割できます。

しかも、分割後のパターンは

  • xが連続せず、両端にも出現しないこと

という分割前の条件を引き継いでいます。

さらに、真ん中のxの左右はoなので、左右のパターンに対して操作をすると、どこかのタイミングで自動でONになってくれます。

ここで、左側のコンピュータを全てONにする方法が $c_{l} $ 通り、右側のコンピュータを全てONにする方法が$c_r$通りあるとします。

また、左側のパターンに含まれるoの数が$o_l$、右側のパターンに含まれるoの数が$o_r$であるとします。

このとき、分割前のパターンにおいて、全てのコンピュータをONにする方法$c_{all}$は以下の式で計算できます。

$$c_{all} = c_l c_r \times { }_{(o_l+o_r)} C_{o_l}$$

コンピュータを手動でONにする操作は($o_l+$o_r)回行うことになりますが、このうちを$o_l$回を左の処理に割り当て、残りの$o_r$回を右の処理に割り当てる方法は ${ }_{(o_l+o_r)} C_{o_l}$通りあります。

左側を処理する順番は$c_l$通り存在し、右側を処理する順番は$c_r$通り存在するので、それぞれを割り当てると$c_{all} = c_l c_r \times { }_{(o_l+o_r)} C_{o_l}$通りになります。

具体例

例として、

分割前のパターン oooxoxoooxooxooo

左のパターン oooxoxooo

右のパターン ooxooo

とします。

このとき左のパターンは7回、右は5回コンピュータを手動でONにするので、

rrllrlllrllr

のような操作順が考えられます。(このような操作順は${ }_{(o_l+o_r)} C_{o_l}={ }_{12}C_5$通り存在します)

左側に対する操作と、右側に対する操作を1つずつ選びます。

左右のパターンそれぞれのoに対して左から順に$0,1,2...$と振っていくとして、

例えば左側に対する操作としては6 5 1 0 2 3 4の順にoを手動でコンピュータをONにし、 右側に対する操作としては3 2 4 0 1 の順にoを手動でコンピュータをONにしたとします。

この操作順のlの部分に、選んだ左側の操作($c_l$通り)を当てはめます。同様に、rの部分にも選んだ右側の操作($c_r$通り)を当てはめます。

このようにすると、例えば r3 r2 l6 l5 r4 l1 l0 l2 r0 l3 l4 r1 という、コンピュータをONにするための操作列が得られます。

rrllrlllrllrの選び方、左側に対する操作の選び方、右側に対する操作の選び方を変えると、得られる操作列は全て異なったものになります。

よって、最終的に得られる操作列はこれらの積、$c_l c_r \times { }_{(o_l+o_r)} C_{o_l}$通りになります。

複数のパターンをまとめて計算する

以上の考察から、xを含んだパターンはxを基準に分割できることが分かりました。

そこで、パターン2つを組み合わせて長さ$i$のパターンを作ることを考えてみます。

作り方による重複を避けなければいけないので、以下の例のように、右側のパターンに含まれるものはoのみとしてみます。(組み合わせた後のパターンから、組み合わせる前のパターンが何であったかを一意に復元できるので、操作順による重複が起きなくなります。)

例) ooxoxoo+x+ooooooo

このとき、左のパターンの長さと含まれるoの個数が分かっていれば、パターン全体の場合の数が求められます。

つまり、左のパターンに関しては、長さとoの個数が等しい複数のパターンをまとめて計算できます。

また、左のパターンにおけるxの個数が決まると、組み合わせた後のパターンにおけるxの個数は1個増えます。これによって、oの個数が自動的に決まります。

そこで、長さが等しく、かつoの個数も等しいような複数のパターンを纏めて管理することを考えてみます。

$A(i,j)$を、「長さが$i$であり、oの数が$j$であるような全てのパターンにおける、各パターンの操作順の個数の総和」とします。

これまで特定のパターンにおける場合の数について話していましたが、以降は$A(i,j)$を使って、「ある条件を満たすパターンの集合における、各パターンの操作列の総和」を管理していきます。この手の数え上げにありがちな、とてもややこしいポイントです。

$A(i,j)$の求め方を考えてみます。以下では$(i>j)$、すなわちパターン中にxが含まれており分割可能である場合について考えます。

$A(i,j)$で扱うパターンは、長さが$i$であり、oの数が$j$であるものです。

これらのパターンは、以下の形式へと一意に分解可能です。

(長さ$k$でoの数が$j-(i-1-k)$のパターン) , x , (長さ$i-1-k$で、全てoからなるパターン)

このとき、左のパターンの操作列の総数は$A(k,j-(i-1-k))$で、右のパターンの操作列の総数は$A(i-1-k,i-1-k)$です。

また、左のパターンのoの数は$j-(i-k)$で、右のパターンのoの数は$i-1-k$です。

この形に分解される操作列の総数は、単一パターンの場合と同様に$c_{all} = c_l c_r \times { }_{(o_l+o_r)} C_{o_l}$で求められるので、

$A(k,j-(i-1-k))A(i-1-k,i-1-k) \times { }_{j} C_{j-(i-1-k)}$

が得られます。

両端がoでなければならない制約から、$k$は$1$以上$i-1$以下となり、以下のような「貰うDP」の推移式が得られます。

$k={1,2,...,i-1}$について、$A(i,j)$+=$A(k,j-(i-1-k))A(i-1-k,i-1-k) { }_{j} C_{j-(i-1-k)}$

$A(i,j)$を計算するのに必要な要素$A(i',j')$については、$(i>i')$の関係が成り立つので、$i$が小さい順に求めていくDPをすればOKです。

最後に、$i=j$の場合を求めておきましょう。

$i==j$なので、パターンは全てo、すなわち全てのコンピュータを手動でONにしなければなりません。

ONにしたコンピュータが1台以上ある場合、そのコンピュータと隣り合うコンピュータしか起動することができません。

離れたコンピュータ2台が起動していて、その間のコンピュータが全てOFFの状態であると、連続してOFFになっているコンピュータの数がどこかのタイミングで1になってしまい、自動で起動してしまうからです。

よって、最初に選んだコンピュータから、右か左かを選びONにしていく必要があります。

例: oooooに対して、左から$0,1,2...$と番号を振っていくと、0,1,2,3,42,3,1,4,02,3,4,1,0など

これを求める方法は2種類ほどあります。

その1

最後にONにするコンピュータは必ず両端のどちらかになります。(両端でないなら、$N-1$個のコンピュータをONにした時点で最後のコンピュータが自動でONになる)

なので、$i$個のコンピュータを全て手動でONにする方法は、

  • 左の$i-1$個をONにする→右端をONにする
  • 右の$i-1$個をONにする→左端をONにする

のどちらかです。

よって$i-1$個のコンピュータを全て手動でONにする方法の2倍になります。

$1$個のコンピュータをONにする方法が1通りなので、$2^{i-1}$通りが答えとなります。

その2

最初に左からj番目(0-indexed)を起動した場合、左のj個と右の(i-1-j)個をONにする順番の並び替えなので${ }_{i-1}C_{j}$通りがありえます。

$j=0...i-1$の総和は$\sum_{0}^{i-1}{ }_{i-1}C_{j}=(1+1)^{i-1}=2^{i-1}$なので、$2^{i-1}$通りが答えとなります。

よって、$A(i,i)=2^{i-1}$となり、これは推移せずに直接求められます。

以上を用いることで、$A(i,j)$を$1\leq j\leq i\leq N$について全て求めることができます。

このとき、$A(i,j)$を求めるコストは最大で$O(N)$なので、全て求めるための計算時間は$O(N^3)$となり制約に間に合います。

解答としては$A(N,0)$から$A(N,N)$までの総和を出力すれば良いです。

実装

  • パターンの分割について考察する。
  • 遷移を考察してDPに落とし込む。
  • $A(i,i)$を求める。$(O(N))$
  • $A(i,j)$を求める。$(O(N^3))$
  • $A(N,i)$の総和を求め、出力する。 $(O(N))$

その他

oの数ではなく、xの数を使って考えてもよいです。筆者はそちらで解きました。 xが連続で出現しない性質上、oの数は長さの半分以下にならないので、xで管理した方がメモリが定数倍改善される利点があります。

感想・あとがき

DP全般苦手だったので解けて嬉しかったです。 コンテスト中の思考を整頓する意味も兼ねて記事を書いてみました。 文章にまとめなおしたことで、参加している時よりも論理的に考えて書けたと思います。 不明瞭・不適切な点ありましたら、コメント欄等で指摘していただければ幸いです。