[yukicoder] No.44 DPなすごろく

問題

No.44 DPなすごろく - yukicoder

動的計画法で解けるみたいですが、まだ学習しておりません。

なので、愚直に考えました。

考え方

,

を考えます。

上記を満たす組み合わせは、

を用いて、 組あることが分かります。

これは、 の取りえる値の範囲は、

だからです。

の値が の数となるので、これの並び方を数え上げれば良いです。順列を考えるので、二項係数を求める必要があります。二項係数の求め方は下のサイトを参考にしました。

d.hatena.ne.jp

コード

import java.util.Scanner;

public class Exec0044 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        scan.close();
        long ans = 0;
        int n = N / 2;
        for(int i = 0; i <= n; i++) {
            int k = N - 2 * i;
            int n1 = k + i;
            ans += comb(n1, i);
        }
        System.out.println(ans);
    }
    // n >= m
    public static long comb(int n, int r) {
        if (n - r < r) r = n - r;
        if (r == 0) return 1;
        if (r == 1) return n;

        int[] num = new int[r];
        int[] den = new int[r];

        for (int k = 0; k < r; k++){
            num[k] = n - r + k + 1;
            den[k] = k + 1;
        }

        for (int p = 2; p <= r; p++) {
            int pivot = den[p - 1];
            if (pivot > 1) {
                int offset = (n - r) % p;
                for (int k = p - 1; k < r; k += p) {
                    num[k - offset] /= pivot;
                    den[k] /= pivot;
                }
            }
        }

        long result = 1;
        for (int k = 0; k < r; k++) {
            if (num[k] > 1) result *= num[k];
        }

        return result;
    }

}