0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

K 個の青いボールと N − K 個の赤いボールがあります。同じ色のボールは区別が不可能です。すぬけ君と高橋君はこれらのボールで遊んでいます。

まず、すぬけ君が、 N 個のボールを左から右に一列に並べます。

次に、高橋君は、これらのうち K 個の青いボールのみを回収します。高橋君は、 1 回の操作で連続して並ぶ青いボールを何個でも回収することができます。高橋君は、常に K 個の青いボールを回収するのにかかる操作の回数が最小になるように行動します。

K 個の青いボールを回収するために高橋君がちょうど i 回操作をする必要があるボールの並べ方は何通りあるでしょうか。 1 ≤ i ≤ K をみたす i それぞれについて答えを計算し、 10⁹ + 7 で割った余りを答えてください。

2.制約

1 ≤ K ≤ N ≤ 2000

3.入力例

入力

2000 3

出力

1998
3990006
327341989

4.初見の感想

同じものを含む順列の問題ですね～
なるほど、(実装)わからん

5.問題の方針

青色のかたまりが何個あるかで分類したい
赤色の球を先に並べておいて、その間に青い球を挿入するという考え方を使う！(これにより挿入箇所の数を固定＝操作回数別に考えられる)
赤色の玉の数はN-K個。つまり挿入箇所は両端も含めてN-K+1個。
i個の挿入箇所を選ぶとすると、N-K+1個からi個選べばよい。
N個の青玉をi個の挿入箇所にどう入れるのは、N-1個の青玉同士の間の中から区切り棒を入れるi-1か所を選ぶのと同じ
つまりN-K+1Ci×K-1Ci-1ってことです。数Aって難しい。

6.実装の方針

幸いN,Kは2000以下なのでパスカルの三角形を使ってコンビネーション(C)の値を事前計算しときます。
定義通り割り算する方法だとオーバーフローなどを考慮する必要が出てきて僕の実力ではやや難しそうです…(特殊な方法はありますが)
1000000007のあまり忘れないでね

7.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        //入力
        string[] input = Console.ReadLine().Split();
        long N = long.Parse(input[0]);
        long K = long.Parse(input[1]);
        long mod = 1000000007;
        long[,] ncr = new long[N+1, K+1];
　　//パスカルの三角形を実行
        for (long i = 0; i < N+1; i++)
        {
            for (long j = 0; j < K+1; j++)
            {
　　　　 //1行目だけ初期化すればあとは自動計算
                if (j == 0) ncr[i, j] = 1;
                else if (i == 0) ncr[i, j] = 0;
                else ncr[i, j] = (ncr[i - 1, j]+ncr[i-1,j-1])%mod;
            }
        }
        for (var i = 1; i <= K; i++)
        {
            long a = ncr[N-K+1,i];
            long b = ncr[K - 1, i - 1];
            Console.WriteLine(a * b % mod);
        }
    }
}

8.最後に

学びが多すぎてびっくり…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 132 D - Blue and Red Balls