スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ARC #012 D : Don't worry. Be Together

日本語なので問題文略。

laycurse さんのコードと math さんのブログ記事を参考にしつつ自分なりに書いてみた。

解答

記号は math さんが使ったものに合わせてみた。

まず N = 1 のときを考える。
考えやすくするため、x≧0, y≧0 として (0, 0) から (x, y) へ行くと思うことにする。

答えが 0 の場合、つまり x+y > T かパリティが合わない ( x+y ≠ T (mod 2) ) ケースは除外しておく。

m := (T-x-y)/2
とおく。
T 回の移動のうち、x+y 回は (x,y) へ進むのに必要で、2m 回は"遊び"。
2m 回の遊びのうち、m 回は x or y 座標が増える方向への移動で、残り m 回は座標が減る方向への移動。

素直に考えれば、答えは多項係数の和で書けて
Σa=0,...,m T! / ( a! (x+a)! (m-a)! (y+m-a)! )
となる。
( m 回の移動のうち x 座標が増える方向への移動が a 回 )

これをそのまま計算すると一人あたり O(m) かかって遅すぎるので、うまい方法を探す。

一回の移動は上下左右のどれか。それぞれ U, D, L, R と書くことにする。
また、x or y 座標が増える方向への移動を +, 減る方向への移動を - と書くことにする。つまり + は U or R, - は D or L。

T 回の移動を + か - かだけ先に決めてしまう。
たとえば m = 4 なら ++++--+-- という列ができるかもしれない。
+ は T-m 個、- は m 個あることに注意。
+- の列は明らかに TCm 通りある。

次に、+- の列から x+m 個の要素を選ぶ。
選んだ要素を使って、次のように UDLR の列を作る:
・ 選んだ + は R に置き換える
・ 選ばなかった + は U に置き換える
・ 選んだ - は D に置き換える
・ 選ばなかった - は L に置き換える

x と y で非対称になっていることに注意。

すると、できた列はちょうど (0, 0) から (x, y) へのパスになっている。
実際、
a 個の + を選んだとすると、自動的に
・ T-m-a 個の + を選ばなかった
・ x+m-a 個の - を選んだ
・ m-(x+m-a) = a-x 個の - を選ばなかった
ことになり、
・ R は a 個
・ U は T-m-a 個
・ D は x+m-a 個
・ L は a-x 個
だけできることになる。

よって、
x 方向への移動量は a-(a-x) = x
y 方向への移動量は (T-m-a)-(x+m-a) = T-2m = y
となり、確かに (0, 0) から (x, y) へのパスになっている。

この対応がちゃんと全単射になっていることもチェックできる。

+- の列から x+m 個の要素を選ぶ方法は TCx+m 通りあるので、結局、答えは
TCm TCx+m
通りになる。



上の方法は直感的(?)だけど、本番中に思いつくのは不可能なので、まだ少しは思いつきやすそうな方法も考えてみる。

+, - に UDLR を割り当てるところで素直に立式すると、
Σa=0,...,m mCa T-mCx+a
という式ができる。
( m 個の - のうち a 個を L に割り当てると考える )

これを式変形していくと、
Σ mCa T-mCx+a
= Σ mCm-a T-mCx+a
= Σ mCa T-mCx+m-a
= TCx+m

となり、同じ結果が得られる。
ここで、最後の等号は
(1 + t)T = (1 + t)m (1 + t)T-m
を展開して tx+m の係数を比較することで確かめられる。



N が一般のときは、単に一人一人のときの結果をかけ合わせればよいので、すぐにできる。

mod が合成数のときは、先に全部約分してしまえばいい。
これは、いもす法のようにやってもいいし、自分は範囲加算 & 点の値を求める BIT みたいなやつを使った。

ソースコード

40 点解法
http://arc012.contest.atcoder.jp/submissions/71480

満点解法
http://arc012.contest.atcoder.jp/submissions/71623
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。