Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-09-27SRM428 DIV2

SRM428 DIV2 Level Three(1000pt.)

| 10:49

http://www.topcoder.com/stat?c=problem_statement&pm=10183&rd=13519

『文字aとzがそれぞれn文字・m文字ある。これらを組み合わせてできる文字列を辞書順に並べたとき、1から数えてk番めに来る文字列を求めよ。』

ビット演算とBigIntegerを組み合わせたコードを書きましたが、kが大きいときに時間切れとなってしまいました。1番めからk番めまでを順々に算出するプログラムにしてしまったこと、重量級クラスとされるBigIntegerに対して操作回数が多くなるビット演算を適用してしまったことが反省点です。ビット演算が高速なのは数値を2進法で管理しているためであり、数値を配列として保持するBigIntegerには適さないことを強く認識する必要があります。

TopSubmissionを見ると、再帰を用いてk番めを直接求める実装になっているようです。ループ内でBigIntegerによる階乗算出を実行しており、遅そうに見えるのですが問題ないレベルなのだと思われます。

// TLE
import java.math.BigInteger;

public class TheDictionary {
	public String find(int aOccur, int zOccur, int k) {
		BigInteger result = BigInteger.ONE.shiftLeft(zOccur).subtract(BigInteger.ONE);
		for (int i = 1; i < k; ++i) {
			result = next(result, aOccur + zOccur, zOccur);
			if (result == null) return "";
		}
		String binary = result.toString(2);
		while (binary.length() < aOccur + zOccur) {
			binary = "0" + binary;
		}
		return binary.replace('0', 'a').replace('1', 'z');
	}

	private BigInteger next(BigInteger source, int length, int zOccur) {
		boolean find = false;
		for (int j = 0; j < length; ++j) {
			if (!source.testBit(j)) {
				if (find) {
					BigInteger result = null;
					result = source.setBit(j).clearBit(j - 1);
					if (!source.testBit(0)) {
						BigInteger shifted = result.shiftRight(j);
						result = BigInteger.ONE.shiftLeft(zOccur - shifted.bitCount()).subtract(BigInteger.ONE);
						result = result.or(shifted.shiftLeft(j));
					}
					// System.out.println(r.toString(2));
					return result;
				}
			} else {
				find = true;
			}
		}
		// System.err.println(Long.toBinaryString(result.longValue()));
		return null;
	}
}