2022.03.18 83日目

白準1010号(架橋)

質問する

元で都市の市長になった.この町には町を東と西に分ける大きな直線形の川が流れている.しかし元知では橋がないため、市民たちが川を渡るのに大きな不便があったため、橋を建てることにした.川沿いに橋を建てるのに適した場所をウェブサイトと言います.元で江辺をよく調べたところ、江西にはNのサイトがあり、東にはMのサイトがあることが分かった.(N ≤ M)
元は西のサイトと東のサイトを橋につなぎたいと思っています.(1つのサイトには最大1つのブリッジしか接続できません.)元ではできるだけ多くの橋を建てたいので、西のサイト数に応じて(N個)橋を建てたいです.足が重ならないと言ったら、橋を建てることができれば、足の数を計算することができます.

私の答え

MのうちN個を選択し、パスカル法則(nとrが同時に1、rが0の場合は1、nのうちr=n-1のうちr-1個+n-1のうちr個を選択)を用いる

一度選択すると重複する場合は関係ないのでx

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            arr = new int[M + 1][N + 1];
            System.out.println(func1(M, N));
        }

    }

    static int func1 (int m, int n) {

        if (arr[m][n] > 0) {
            return arr[m][n];
        }

        if (n == 0 || n == m) {
            return arr[m][n] = 1;
        }

        return arr[m][n] = func1(m - 1, n - 1) + func1(m - 1, n);
    }
}

考える

11050号(離項係数1)応用問題

組合せ・動的計画法