別の投稿を見て気になって自分でやってみた。
問題は
「1000個数字が並んでいる。そこから連続する13個の数字を取り出して、それら13個の数字の積を考える。その最大値を求めよ。」
というもの。
13個の掛け算を1000回近くやらせるのは癪に障るし、そのまま尺取り法のように考えると、除算が1000回近く起こってしまい、よろしくない。
多数の積を取るということから、対数を使おう。
$\log_a M$を$a$を底(てい)とする$M$の対数と呼び、次のように定められる。
実数r,a>0, a\neq1,M>0に対し、\\
a^r=M \iff r= \log_a M
簡単に言うと、正の数$M$をある1でない正の数$a$の累乗で表そうとした場合の指数を表すものである。
例えば$2^3=8$だから$\log_2 8 = 3$となる。
また、指数は実数全体まで拡張して考える。この考えのもとでは$2^{\frac{1}{2}}=\sqrt{2}$となるため、$\log_2\sqrt{2}=\frac{1}{2}$となる。
指数には指数法則$a^x\times a^y = a^{x+y}$が成り立つ。指数がもともと掛け算の個数という立場に立てば、それらの掛け算は個数の合計分掛けたものという点では自然に理解できるのではないだろうか。これを対数の表現にするとこうなる。
a>0, a\neq1,M>0,N>0に対し、\\
\log_a {MN} = \log_a M + \log_a N
この性質から、掛け算を対数の足し算に変換できる。また対数には
M>0,N>0とする。\\
a>1のとき、M<N \iff \log_a M < \log_a N
という性質がある。つまり、$a>1$では元の数の大小と対数を取った時の大小が一致する。これを利用して、掛け算を対数の足し算として、尺取り法で対数の和が最大になる区間を探すことによって求められる。
今回対数を取るために、JavaのMathクラスのメソッドMath.log10(x)を使用する。$a=10$として引数の対数を取る、つまり$\log_{10}x$を求めるメソッドである。
(ちなみに、$a=10$として取る対数を常用対数と呼んだりする。)
必要な対数は0~9の10個の数字それぞれに対するものだけであるので、それをあらかじめ計算し配列に入れておく。しかし、0に対する対数は数学上定義されておらず、メソッドの定義としても「負の無限大」となるため、尺取り法でこれを加えてしまうと元に戻せなくなってしまう。そのため、0に対する対数として便宜上-1000を設定する。これにより、0を含む区間では必ず対数の和が負になり、最大の候補から外れるうえ、0が外れるときに元に戻すことも可能になる。
最大になる区間がわかったら、その積を実際に求める。対数の定義から求めようとすると、浮動小数点の誤差の問題で正確な値が出ない恐れがあるためである。
その考えで書いたコードが以下になる。
import java.util.*;
import java.util.stream.*;
public class Main {
private static final String NUMS
= "73167176531330624919225119674426574742355349194934"
+ "96983520312774506326239578318016984801869478851843"
+ "85861560789112949495459501737958331952853208805511"
+ "12540698747158523863050715693290963295227443043557"
+ "66896648950445244523161731856403098711121722383113"
+ "62229893423380308135336276614282806444486645238749"
+ "30358907296290491560440772390713810515859307960866"
+ "70172427121883998797908792274921901699720888093776"
+ "65727333001053367881220235421809751254540594752243"
+ "52584907711670556013604839586446706324415722155397"
+ "53697817977846174064955149290862569321978468622482"
+ "83972241375657056057490261407972968652414535100474"
+ "82166370484403199890008895243450658541227588666881"
+ "16427171479924442928230863465674813919123162824586"
+ "17866458359124566529476545682848912883142607690042"
+ "24219022671055626321111109370544217506941658960408"
+ "07198403850962455444362981230987879927244284909188"
+ "84580156166097919133875499200524063689912560717606"
+ "05886116467109405077541002256983155200055935729725"
+ "71636269561882670428252483600823257530420752963450";
public static void main(String[] args) {
final int SPAN = 13;
final double[] log10 = IntStream.range(0, 10).mapToDouble(Math::log10).toArray();
log10[0] = -1000;
double logMax = IntStream.range(0, SPAN).mapToDouble(i -> log10[getNum(i)]).sum();
int head = 0;
double partial = logMax;
for (int i = 0, j = SPAN; j < NUMS.length(); i++, j++) {
partial = partial - log10[getNum(i)] + log10[getNum(j)];
if (partial > logMax) {
logMax = partial;
head = i + 1;
}
}
long result = IntStream.range(head, head + SPAN)
.mapToLong(i -> getNum(i))
.reduce(1L, (x, y) -> x * y);
System.out.println(result);
}
private static int getNum(int i) {
return NUMS.charAt(i) - '0';
}
}