yukicoder No.758 VVVVV

N×Nの格子点を想定する。
一番左下の格子点を(0, 0), 一番右上の格子点を(N, N)とする。
右向きの(i, j)から(i+1, j)への移動と
上向きの(i, j)から(i, j+1)への移動
のみによって、(0, 0)から(n, n)に移動する経路のうち対角線をまたがない経路数を数えたい。
とくに、上向きの移動から右向きの移動に変化する箇所(山と呼ぶことにする)がk個ある場合の経路数を数えたい。この経路数をN(n, k)と置く。

対角線をまたがないという条件を無視すれば、そのときの(0, 0)から(n, n)への経路のうち山がk個ある経路数は

{ \left( \begin{array}{c} {n-1} \\ k \end{array} \right) \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }

となる。
これは、山のx座標の選び方とy座標の選び方がそれぞれ{ \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }通りあるからである。

同様に、(0, -1) から (n, n) への経路のうち山が k 個あるのは
{ \left( \begin{array}{c} {n} \\ k \end{array} \right) \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }通りである。

このうち、(0, -1) → (0, 0) → (n, n) と移動し y < x なる格子点を (0, -1) 以外で通らない経路を考える。
(0, -1) → (0, 0) の経路は1通りしかないので、この経路数が求めたい値になっている。
この経路は山が k 個あることから↑→の経路の組 k 個に分解できる(谷の存在しない k 個の経路に分解できる)。
分解したそれぞれの経路について、出発点 (0, -1) に近いほうから1, 2, 3, ...,, k と番号を振る。
i 番目の経路について { a_i } = （上向きの移動回数）－（右向きの移動回数）と置く。
いま、y < x なる格子点を (0, -1) 以外で通らないという条件から、任意の m について
{ \sum_{i=1}^{m} a_i > 0 }
が成り立つ。とくに、m = k のとき
{ \sum_{i=1}^{k} a_i = 1 }
となり、
m = 1 のとき
{ a_1 ≧ 1 }
となる。

(0, -1) → (0, 0) → (n, n) と移動し y < x なる格子点を (0, -1) 以外で通らない経路について、
1, 2, 3,..., k の経路を
1, 2, 3,..., ,k-2, k-1, k
2, 3, 4, ..., ,k-1, k, 1
3, 4, 5, ..., k, 1, 2
4, 5, 6, ..., 1, 2, 3
と順番に循環させたものすべての集合を考えると、それは(0, -1) から (n, n) への経路のうち山が k 個ある経路全体に等しくなることを示したい。
つまり、
{ N(n, k) = \frac{1}{k} \left( \begin{array}{c} {n} \\ k \end{array} \right) \left( \begin{array}{c} {n-1} \\ k \end{array} \right) }
であることを示したい。

上の循環させた経路は、y - xが最小となる谷が常にk, 1の間で形成され、その谷ではy - x < 0 であることから、循環させた経路の集合に重複する経路はない。
また、任意の(0, -1) から (n, n) への経路のうち山が k 個ある経路は循環させることで、y < x なる格子点を (0, -1) 以外で通らない経路に帰着できるので上の等式が成り立つ。
（時間があるときに説明を追加する）
（Eulerian Numbers | T. Kyle Petersen | Springerに詳しく載っている。）

No.720 行列のできるフィボナッチ数列道場 (2)

$$A=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$

$$F=\begin{bmatrix} 1  \\ 0  \end{bmatrix}$$

としたときの、

$$(A^n+A^{2n}+...+A^{mn})F$$
$$=A^n \frac{E-A^{mn}}{E-A^n} F$$

の第二成分が答え。

 

 

 

 

testestestさんに教えていただいた解法

フィボナッチ数列の第i項目は

$$\frac{1}{\sqrt 5} \left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)$$

で表されるから、求める和は等比数列の和の差であらわせる。上記の計算はa+b√5の形を持ちながら計算すればよい。

yukicoder No.699 ペアでチームを作ろう２

No.699 ペアでチームを作ろう２ - yukicoder

本当に何も考えずに全探索すると12!＝479001600回の計算が必要で間に合わない。

ペア(a,b)とペア(b,a)を同一視すると、12!/(2)^6=7484400回の計算にまで落ちる。C++ではこれで通るようだが、Javaでは全然駄目だ。そこで、二つのペアを(a,b),(c,d)と列挙するのと、(c,d),(a,b)と列挙するのを同一視することにする。このとき、12!/(6!2^6)=10395回の計算になり、これは十分1秒以内に処理できる。

ねねじゃっじ　0014 - ベル数

https://www.ei1333.site/problems/14

解説を読んだ。

{1,2,3,...,N-1,N}を分割する方法の数をベル数という。B_Nで表す。

ベル数は

B_N

=\sum_{i=1}^N 1/{k!} \sum_{k=1}^i (-1)^{i-k} k^N \binom{i}{k}

=\sum_{i=1}^N \sum_{k=1}^i  \frac{(-1)^{i-k}}{(i-k)!} \frac{k^N}{k!}　

i組のグループに分けるときの分け方についてそれぞれ包除原理を用いて求めている。

ここで、和を取る順序を変更する。k^N/k!についてまとめると、

B_N=\sum_{k=1}^N \frac{k^N}{k!}\sum_{i=1}^{N-k}  \frac{(-1)^{i}}{i!} 　

\sum_{i=1}^{N-k}  \frac{(-1)^{i}}{i!} については前計算しておくことができるので、O(N)でB_Nが求まる。

 

CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel)　A - 迷子の高橋君 / Takahashi is Missing!

問題

https://beta.atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_e

数直線上に Aさんと Bさんがいる。Aさんと Bさんの距離は L だけ離れている。Aさんと Bさんはそれぞれ同時に動く。Aさんは 現在地を xとすると x -1, x, x +1のいずれかに動くことができる。Bさんは 現在地を ｘ とすると 確率ｐでｘ－１に、確率１－ｐでｘ＋１に動く。AさんとBさんが同じ位置になるまで Aさんと Bさんは動き続ける。Aさんと Bさんの動きは離散的だとする。すなわち X から X +1に動く時、X +0.5などの値は取っていないとする。A さんは B さんと同じ位置になるように動く。 A さんが最適な動きをしたときの動く回数の期待値はいくらか求めよ。

アプローチ

Aさんと Bさんの距離 L が奇数のとき A さんは必ず一度その場から動かない動きをする必要がある。 なぜなら A さんと B さんそれぞれ両方とも その場から動くとき L の偶奇が保たれるため A さんと B さんが出会う、つまり L=0 になることはないからである。 よって距離 L が 奇数のとき A さんは最初のターンで動かないとしても一般性を失わない。これは A さんが B さん の現在地 から離れる方向に１だけ離れた位置からスタートしたと考えても良い。 L が偶数のときは A さんは B さん との距離をつめる方向に動くのが最適である。 A さんと B さんの距離をL =２R とした時の残りのターン数の期待値を E(R) とする。このときE(R+1)＝ｐE(R-1) + ( 1 - p )E(R) + 1が成り立つ。この式は一般項が求まるのでO(１）で答えが求まる。

Submission #2107181 - CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel)