paizaオンラインハッカソン7に参加してみた – 水着(Java※ダメな例付き)

2015.12.22
注意: この記事は1年以上前に掲載されたものです。情報が古い場合がありますのでお気を付け下さい。

当ブログでは順次『paizaオンラインハッカソンVol.7 プログラミングで彼女をつくる』の回答例をC++及びSwiftをベースに上げているが、今回は番外編という位置付けで水着のお題をJavaで回答した例を上げてみたい。なお、今回はダメな例も挙げ、どこがまずいのかも説明したい。

今回のお題の目的

入力された数値の階乗を全ての桁の代わりに、最下位の桁より後ろの全ての0を取り除いた数値の下位9桁を出力するというものである(ただし、そこから先頭の全ての0を除く)。

なお、今回はC++では64bitをこえる整数型は使えず、paizaオンラインハッカソンでは任意精度演算のライブラリーも使えないということから、今回はあえてJavaを使った。

回答例

ダメな例

参考URL: https://github.com/saitomarch/POH7/blob/master/java/mizugi_bad.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.*;

public class Main {
    public static BigInteger factorial(BigInteger bigint) {
        BigInteger result = new BigInteger("1");
        for (BigInteger k = new BigInteger("1"); k.compareTo(bigint) <= 0; k = k.add(new BigInteger("1"))) {
            rslt = result.multiply(k);
        }
        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String numstr = factorial(new BigInteger(line)).toString();

        numstr = numstr.replaceAll("0*$", "");
        final int LIMIT = 9;
        if (numstr.length() > LIMIT) {
            numstr = numstr.substring(numstr.length() - LIMIT);
        }
        numstr = numstr.replaceAll("0*^", "");

        System.out.println(numstr);
    }
}

良い例

参考URL: https://github.com/saitomarch/POH7/blob/master/java/mizugi.java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static long factorial(long num) {
        long result = 1;
        final long LIMIT = 100000000000l;
        for (long k = 1; k <= num; k++) {
            result *= k;
            while (result % 10 == 0) {
                result /= 10;
            }
            if (result / LIMIT > 0) {
                result %= LIMIT;
            }
        }
        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String numstr = String.valueOf(factorial(Integer.parseInt(line)));

        numstr = numstr.replaceAll("0*$", "");
        final int LIMIT = 9;
        if (numstr.length() > LIMIT) {
            numstr = numstr.substring(numstr.length() - LIMIT);
        }
        numstr = numstr.replaceAll("0*^", "");

        System.out.println(numstr);
    }
}

解説

今回のコードでは、ダメな例・良い例ともにfactorial()メソッド以外は同一の処理となっている ((階乗を求めたあと、後ろに0があったら、それを除去、その次に下位9桁を残した上で、前の0を除去する処理など)) 。双方のfactorial()メソッドの大きな違いはダメな例ではBigIntegerを使って単純に計算を、良い例ではlongを使って補正をかけながら計算を行っているという大きな違いがある。

なお、ダメな例でもアルゴリズム自体は正しいので、提出時に途中までは正解となる。しかしながら、テストケース4でタイムオーバーとなってしまい、そこから先が進まなくなってしまう。

これは、BigIntegerでは任意精度演算としてintやlongなどでは扱えない巨大な数を扱えるという大きな特徴を持っているが、テストケース4以降ではそれがあまりにも巨大すぎて階乗処理で処理が終わらなくなってしまうという問題があるからである。

そこで、今回のお題はそもそも全ての階乗の数値を求めているわけではないことに気づくかどうかが大きなポイントとなる。具体的には以下の通りである。

  • 一番後ろの数字は0以外であること
  • 一定以上の数値があれば問題なく、64bitの整数型でも問題ない。

したがって、今回の良い例では以下の補正を行った。

  • 計算結果が10の倍数になったら、そうではなくなるまで10で割る。
  • 計算結果が一定以上 ((今回は100000000000)) になったら、それを割ったあまりの数にする。

上記のような対策をとることによって、BigIntegerで単純な計算を行うとタイムアップするようなものでも、スピーディーに行える計算と、求められている答えを出すという両方の課題をクリアしている。

最後に

今回は階乗という、32bit整数型はおろか64bit整数型でさえ扱いきれない可能性のある数値をもとにした結果をいかにして正しく、かつスピーディーに行えるかが重要となった。

しかも、64bit整数型では扱いきれないからといって単純にBigIntegerを使って計算するということもできないわけではないが、それだと大きい数が来た時にタイムオーバーとなってしまう。かといって通常の変数型ではオーバーするという状態になった時、どういう条件で出力されるのかを読んだ上で補正を行うという、発想の転換が重要になるだろう。

今回のはかなりいやらしい問題ではあるが、決してクリアできない問題ではないので、自信のある方は是非チャレンジしてみると良いだろう。

タイトルとURLをコピーしました