「第17回オフラインリアルタイムどう書く」参考問題のへなちょこ解答（Java）

どう書く Java

久しぶりにイベント（http://atnd.org/events/46348）開催前に参考問題を解けました。

今回は、「回文基数」です！

たとえば101, 234432のように、右から読んでも左から読んでも同じ数字の並びを持つ数を「回文数」というのですね。初めて知りました。

今回は、入力で与えられた数字を変換して、回文数を得ることができる基数を求めなさい、という問題です。

考えたこと

基数は、入力値よりも大きくはなりません。そこで、基数が入力値未満の間、入力値を基数n（n=2から開始し、1ずつ増やす）の値に変換し、回文数かどうかをチェックします。

変換するとはいっても、基数が大きくなってくると、変換後の値を表現するのは大変です。16進数なら16種類の識別子（0〜9とa〜f）があれば値を表現できますが、100進数では100種類の識別子が必要です。

幸い、この問題では「回文になっているか」さえチェックできればよいので、最上位ケタと最下位ケタから中央に向かって1つずつ数字を比較し、変換値のケタの並び順にはこだわらないことにします。

自分の解答

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * Question: http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
 */
public class Scheherazade {

	public String solve(String input) {
		BigInteger dn = parse(input);

		StringBuilder sb = new StringBuilder();
		for (BigInteger base = BigInteger.valueOf(2); base.compareTo(dn) < 0; base = base
				.add(BigInteger.ONE)) {
			List<BigInteger> num = getNum(dn, base);
			if (0 < num.size() && isPalinum(num)) {
				sb.append(String.valueOf(base));
				sb.append(',');
			}
		}
		if (sb.length() == 0) {
			return "-";
		}
		return sb.substring(0, sb.length() - 1);
	}

	boolean isPalinum(List<BigInteger> num) {
		for (int i = 0; i < num.size() / 2; i++) {
			if (0 != num.get(i).compareTo(num.get(num.size() - 1 - i))) {
				return false;
			}
		}
		return true;
	}

	List<BigInteger> getNum(BigInteger origin, BigInteger base) {
		List<BigInteger> result = new ArrayList<>();
		BigInteger answer = origin;
		for (; 0 < answer.compareTo(BigInteger.ZERO);) {
			BigInteger[] dr = answer.divideAndRemainder(base);
			result.add(dr[1]);
			answer = dr[0];
		}
		return result;
	}

	BigInteger parse(String input) {
		return new BigInteger(input);
	}
}

勉強になった点

intのケタが足りない

問題に用意されたテストデータを使ってテストしたところ、intを使って書いていたせいで、ケタが足りなくて死にました！ ksg! BigIntegerさんこんにちは。BigDecimalでもいいですね。

BigIntegerの値の比較はcompareToメソッドを使う

BigIntegerを使った際に、数値の比較でミスをしました。回文数かどうかをチェックするisPalinumメソッドで、変換後の数値を1つの位ごとに格納したListから、2つずつ値を取り出して、等しいかどうか見ています。

ここで、最初にintで書いた名残りで、演算子「!=」を使っていました。これではオブジェクト同士を比較するだけで、値の比較はできません。当然コンパイルは通るので、見逃してしまいました。

BigIntegerのdivideAndRemainderメソッド

配列の1番目の要素で除算の結果、2番目の要素で剰余の結果を返してくれるメソッドです。

剰余を得るならModでいいかと思ったのですが、BigIntegerにはm mod nを返すModメソッドと、m % nを返すRemainderメソッドがあり、実装が異なるんですね。どっちがどうというのは理解していません（宿題？）。

わからなかったのでdivideAndRemainderメソッドを使ったというのが正直なところです。