CodeIQ：枚数で考えるパスカルの三角形

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「枚数で考えるパスカルの三角形」（CodeIQ）を参照してください。

問題の概要

パスカルの三角形（下図）があります。

n=0	1
n=1	1 1
n=2	1 2 1
n=3	1 3 3 1
n=4	1 4 6 4 1
n=5	1 5 10 10 5 1

このn段目の各数字を日本の紙幣（10000円、5000円、2000円、1000円）と硬貨（500円、100円、50円、10円、5円、1円）で構成する場合、その最小枚数の合計はいくらか、という問題です。

私のプログラム

Javaで解答しています。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;

/**
 *
 * @author kamio
 */
public class Main {

    /**
     * 組み合わせを計算する
     * @param n
     * @param r
     * @return 組み合わせの数。n<rなら-1。
     */
    public static long C(int n, int r){
        if(n<r) return -1;

        long ret = 0;
        long nx = 1;        // n!
        long n_rx = 1;      // (n-r)!

        for(int i=r+1; i<=n; i++)   nx *= i;
        for(int i=1; i<=(n-r); i++) n_rx *= i;

        ret = nx/n_rx;

        return ret;
    }

    /**
     * 組み合わせ計算BigIntegerバージョン
     * @param n
     * @param r
     * @return 組み合わせの数。n<rなら-1。
     */
    public static long bC(int n, int r){
        if(n<r){
            return -1;
        }

        BigInteger nx = new BigInteger("1", 10);
        BigInteger n_rx = new BigInteger("1", 10);

        for(int i=r+1; i<=n; i++){
            String v = String.valueOf(i);
            nx = nx.multiply(new BigInteger(v, 10));
        }

        for(int i=1; i<=(n-r); i++){
            String v = String.valueOf(i);
            n_rx = n_rx.multiply(new BigInteger(v, 10));
        }

        BigInteger ret = nx.divide(n_rx);

        return ret.longValueExact();
    }

    /**
     * 日本の貨幣の定義
     */
    final static int[] MONEY = {10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1};

    /**
     * 最小どれだけの紙幣、硬貨が必要かを計算
     * @param total 金額
     * @return 紙幣、硬貨の枚数
     */
    public static long countMoney(long total){
        long cnt = 0;

        for(int i=0; i<MONEY.length; i++){
            cnt += total / MONEY[i];
            total = total % MONEY[i];
	}
        return cnt;
    }

    /**
     * @param args the command line arguments
     * @throws java.io.IOException
     */
    public static void main(String[] args) throws IOException {
        try (BufferedReader stdReader = new BufferedReader(new InputStreamReader(System.in))) {
            String line;

            while ((line = stdReader.readLine()) != null) {
                ArrayList<Long> Vals = new ArrayList<>();   // 各項の値リスト
                int n = Integer.parseInt(line);
                for(int r=0; r<=n; r++){
                    Vals.add(bC(n,r));
                    //System.out.print(bC(n, r));
                    //System.out.print(" ");
                }
                //System.out.println("");

                long total = 0;
                for(long l: Vals){
                    total += countMoney(l);
                }

                System.out.print(total);
            }
        }
        return;
    }

}

解説

それでは解説します。
クラス名がMainなのはCodeIQの自動判定システムの仕様でこの名前が強制されるためです。

指定された段の値を求める

指定された段に含まれる値を生成してValsに格納しています。
漸化式を求めないと計算が膨大になりますが「パスカルの三角形」と明確に書かれているのでWikipediaを調べれば簡単にわかります。二項定理ですね。高校の数学で習ったと思いますが、当然のように忘れているので調べると各項の係数は_nC_rで求めることができます。
Javaの標準ライブラリに組み合わせを計算するクラスかメソッドがあれば使いたかったのですが無いようなので作りました。C()とbC()です。実務で同様のメソッドを作るならせめてcombin()とかにすべきですね。
なぜ2つもあるのかを後述します。

オーバーフロー

最初に解答を提出した時、ひょっとしたら64bit整数では足りなくなるかも、とは思いましたが面倒だったのでそのまま出しました。予想どおりN=40で桁あふれしてNGになりました。
それで長倍精度整数を使うように変更したのがbC()です。

貨幣の数を数える

countMoney()でトータル何枚必要かを計算しています。
この計算は簡単で、大きい貨幣から順に割り算してその商をその貨幣の枚数、あまりを次の貨幣単位の計算に回せば良いだけです。計算の順番は66行目のint[] MONEYで定義しています。
この問題はパスカルの三角形のN段目の各項ごとに枚数を合計しなければいけないので102〜104行目でそれをやっています。

雑感

この問題は「パスカルの三角形」という明確なキーワードがあるためあまり難しくありませんでした。ただ、私はオーバーフローでの再提出以外に2回ミスっています。1回はデバッグプリントを削除し忘れて、もう1回は95行目のC()をbC()に変更し忘れてです。確認はきちんとしなければなりませんね。