2016年2月5日金曜日

いまさらCode Jam Japan(2011) 決勝 問題B「バクテリアの増殖」 Small

もう5年近く前のことですが、私と同じように解いた解説が出てこないので書いてみます。

問題はこれです。
https://code.google.com/codejam/contest/1363489/dashboard#s=p1

要約すると、

a(0)=A
a(n)=a(n-1)a(n-1)
を満たす配列anの第B項をCで割った余りで答えよ。

このA,B,Cの値の組のテストケース数は500以下
Aの値は1,000以下
Bの値はSmallは2以下、Largeは1,000以下
Cの値は1,000以下


公開鍵暗号の原理と同じで周期から計算できるんだろーなとは思ったんですが、やはりGoogleの解説もそのようになっています。
https://code.google.com/codejam/contest/1363489/dashboard#s=a&a=1

このCode Jam Japanの決勝問題は問題Aが簡単、それに比べて問題B以降が難しく、終了時点で問題AのSmall, Largeだけ解けた人が112位から355位まで大渋滞しています。
https://code.google.com/codejam/contest/1363489/scoreboard#sp=91

200位以内に入れば景品のTシャツがもらえるんですが、問題Aを解いただけでは早く解いた者勝ちです。そこに入れない場合は、どの問題でもいいからSmallだけでも解ければTシャツ圏内に入れる、という状況でした。

で、この問題BのSmallはBが2以下なので、 第2項まで求めればいいようになっています。つまり(AA)(AA)までのmodが計算できれば解けることになります。

 X = AA mod C
として、
 X(AA)
を求めるわけですが、当然指数のAAはmodは効かずこれ自体が天文学的数字になる可能性があります。どうにかXの方をmodしながらべき乗していって求める方法を考えないとダメそうです。

で、苦し紛れに
 (XA)A
で同じにならないかな?と思ってもこれは
 X(A*A) = X(A2)
にしかなりません。

掛け算で並べて書けばわかりやすいんですが、例えばAが5とするとXの5乗は
 X*X*X*X*X
これのさらに5乗は縦に書き足せば
 X*X*X*X*X*
 X*X*X*X*X*
 X*X*X*X*X*
 X*X*X*X*X*
 X*X*X*X*X
Xが5*5個なので
 X(5*5) = X(52)
にしかなりません。

しかし、これをさらに5乗すれば
 X(5*5*5) = X(53)
になります。
ということは、この調子でXを5乗する、を5回繰り返せば
 X(5*5*5*5*5) = X(55)
が求まることになります。同様に、X(AA)を求めるためには、XをA乗するのをA回繰り返せばよい、ということになります。

A,B,Cがjavaのintとして与えられているとして、BigIntegerクラスのmodPowを使って書けば、

BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.modPow(a, c);
for (int i = 0; i < A; i++)
    X = X.modPow(a, c);

とまあ、とても短いプログラムで求めることができます。

実際私はmodPowメソッドの存在を知らなかったのでこれ相当の関数を自分で作り、終了前15分で解答提出、260位(?)あたりから一気に89位に浮上、終了時点で96位、最終的に93位で無事Tシャツを頂きました。

BigIntegerを使ってキレイに書きなおせば以下のようなコードになります。

import java.math.BigInteger;
import java.util.Scanner;

public class B {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++) {
            System.out.println("Case #" + i + ": " +
                resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
    }

    private static int resolv(int A, int B, int C) {
        BigInteger a = BigInteger.valueOf(A);
        BigInteger b = BigInteger.valueOf(B);
        BigInteger c = BigInteger.valueOf(C);
        BigInteger X = a.modPow(a, c);
        if (B == 2)
            for (int i = 0; i < A; i++)
                X = X.modPow(a, c);
        return X.intValue();
    }
}


実はこのBigIntegerクラス、1,0001,000も扱えてしまうので、上で書いたようなことは全く考える必要もなく、そのまま素直にコーディングすれば解けてしまうのでした。


import java.math.BigInteger;
import java.util.Scanner;

public class B2 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++) {
            System.out.println("Case #" + i + ": " +
                resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
    }

    private static int resolv(int A, int B, int C) {
        BigInteger a = BigInteger.valueOf(A);
        BigInteger b = BigInteger.valueOf(B);
        BigInteger c = BigInteger.valueOf(C);
        BigInteger X = a.pow(A); // 最大1,0001,000
        BigInteger Xm = X.mod(c);
        if (B == 2)
            Xm = Xm.modPow(X, c); // そのまま計算
        return Xm.intValue();
    }
}


結局ライブラリ知ってるもん勝ちな問題でした。