「増井技術士事務所 今週のお題:指定された回数で移動できる経路は何通り?正答率80%」
解けなかったのでメモ。
回答
/* 入力値 m (0 < m <= 20) 横マスの数 n (0 < n <= 20) 縦マスの数 a (1 < a <= m + n) 入力フォーマット m n a ------------------------------- 求め方 以下の数式で求まるはず。 p = aCk * (a-k)Cwi * (a-k-wi)Chj 入力値 m n aより以下の値を求める。 ①斜め移動の回数をkと置く k = m + n - a ②横移動の回数をwiと置く wi = n - k ③縦移動の回数をhjと置く hj = n - k ------------------------------- 実装方針 ①順列数を求める機能 ②組み合わせ数を求める機能 ③上記の式を実装した機能 */ #include<stdio.h> // 順列数を求める機能 int permutation(int n, int r) { int i, p = 1; for(i = n; (n - r) < i; i--){ p *= i; } return(p); } // 組み合わせ数を求める機能 int combination(int n, int r) { int p, q, c; // 順列数を求める p = permutation(n, r); // 重複度の順列数を求める q = permutation(r, r); // 順列数を重複度の順列数でわる c = p / q; return(c); } // 上記の式を実装した機能 long ans(int m, int n, int a) { int k, wi, hj, t1, t2, t3; long ans = 1; k = m + n - a; wi = m - k; hj = n - k; t1 = combination(a, k); t2 = combination(a - k, wi); t3 = combination(a - k - wi, hj); ans = ans * t1 * t2 * t3; return(ans); } int main(int argc, const char * argv[]) { int m, n, a; scanf("%d %d %d", &m, &n, &a); printf("%ld\n", ans(m, n, a)); return 0; }