Nyaanの日記

競プロ用(精進記録など)　乱文失礼します

Beginners Typhoon After Contest#01 EX - No Bingo!

初めてブログ記事を書いた
フォントやレイアウトが壊れまくっており厳しい…

www.hackerrank.com
昨日ようやく解説の意味がわかったので自分なりの理解をまとめておく。

題意の問題は以下のように読み替えられる。

順列p _ iについて、以下の条件を満たすp _ iの場合の数を求めよ。
条件 \ \ldots \ p _ i = i ,p _ j = N + 1 - jを満たすi,jがともに一つ以上存在する。


場合分けをする。
A \ldots 全事象の場合の数
B \ldots 全てのiに対してp _ i \neq iとなる場合の数
C \ldots 全てのiに対してp _ i \neq N + 1 - iとなる場合の数
D \ldots 全てのiに対してp _ i \neq iかつp _ i \neq N + 1 - iとなる場合の数

とすると、求める場合の数はA - (B + C) + Dとなる。
A,B,Cは容易に求まるのでDについて考える。

まずNが偶数の時について考える。(このときN = 2Mとおく。)

a _ n := (少なくともn個のiについてp _ i = iまたはp _ i = N + 1 - iとなる順列の場合の数)
とおくと、包除原理よりD = \sum _ {i=0} ^ N ( a _ i (-1) ^ i ) が成り立つ。
よってa_nを求めればDの値が求まることになるが、直接求めるのは難しい。

ここで1とN、2とN-1、\ldots、MとM+1をペアにして考える。
これらのM個の組のうちいくつの組が条件を満たすかで場合分けすることを考える。
条件( \ast ) を以下のように定める。

条件( \ast ) \ \ldots \ とある組(i , N + 1 - i)で{ \bf "斜めのラインを防いだ穴"}が1つ以上ある。
すなわち、 p _ i = i , p _ i = N + 1 - i , p _ {N + 1 - i } = i , p _ {N + 1 - i} = N + 1 - i
のうち1つ以上を満たす。

次に数列f _ kの第n項を以下のように定める。

( f _ k ) _ n := (少なくともk個の組について( \ast ) を満たすとき、
k個の組の中で{\bf"斜めのラインを防いだ穴"}の個数がn個となる順列の場合の数)


この時、1対1の性質から a _ n = \sum _ {k=0} ^ M ( f _ k ) _ n が成り立つため、
f _ kの和を高速に求めれば題意の問題が解けることがわかる。

さて、組(i , N + 1 - i)において斜めのラインを防いだ穴がどのように配置され得るかを考えると、
2個配置される \ldots (i , i)(N+1-i,N+1-i) \ , \ (i,N+1-i)(N+1-i,i)の2通り
1個配置される \ldots (i , i)\ ,\ (N+1-i,N+1-i) \ , \ (i,N+1-i)\ , \ (N+1-i,i)の4通り
となる。
この事実をもとに形式的冪級数を導入すると f _ k = \ _ n C _ k ( 2 x ^ 2 + 4 x ) ^ k となるため、
二項定理より a = \sum _ {k=0} ^ M ( f _ k ) = (2 x ^ 2 + 4 x + 1 ) ^ M が従う。
(この辺りはmaspy氏の形式的冪級数の解説記事を読むと理解しやすいと思う。)

N = 2 M + 1と表される場合も、同様の考察を経ることで a = (2 x ^ 2 + 4 x + 1 ) ^ M (x + 1)を導ける。
あとは適切な実装によりこの問題を高速に解くことが出来る。
提出
Programming Problems and Competitions :: HackerRank

感想
とても難しい…こういう考察を素早く進められるようになりたい。