出展 †
問題 †
直線上に並ぶN個のボールの位置が与えられる．
このボールそれぞれが直線上をt(>0)または-tだけ移動し，さらに複数のボールが追加される．
その結果が与えられるとき，可能なボールの移動の仕方は何通りあるか求めなさい．
解法 †
- 移動後のボールの個数をMとすると，tの候補がNM個に絞れる．
- tそれぞれについて，|移動前位置-移動後位置| = tになるボールの組に枝を張る
- 作ったグラフの連結成分それぞれについて，
- 移動前のボール数 = 移動後のボール数 なら組み合わせは1通り
- 移動前のボール数+1 = 移動後のゴール数 なら組み合わせは(移動後のボール数)通り
- それ以外なら組み合わせは0通り
- tごとに各連結成分内の場合の数の積を求め，その和をとれば良い．
回答 †
![[PukiWiki]](../../image/pukiwiki.png "[PukiWiki]")
