ksaitoの日記

日々試したことの覚え書き

Google code jam 2011

エントリーしていたのですが運動会であまり時間とれず予選落ちでした。
一番簡単そうな3個目の問題のsmallを正解したところで時間切れ。
ルールを読み間違えていなければ、問題文や解法についての議論や共有、他の場所への転載が禁止されているのは、各ラウンドの開始から終了の間なので予選終了後にコード修正したコードをアップしてもルール違反にならないはず。
多分、Largeの問題にも8分以内で対応できるはずですがLargeの問題ダウンロードしておけばよかった。
誰か問題のファイルを送ってくれないかなぁ...

package google.code.jam;

import java.io.File;
import java.io.FileNotFoundException;
import java.math.BigInteger;
import java.util.Scanner;

public class BitCounter {
	BigInteger n;
	
	public BitCounter(String n) {
		this.n = new BigInteger(n);
	}
	
	public int maxBitCount() {
		int result = 1;	
		BigInteger a = new BigInteger("1");

		while (a.compareTo(n) == -1) {
			BigInteger b = n.subtract(a);
			int r = bitCount(a, b);
			if (result < r) {
				result = r;
			}
			a = getNextA(a);
		}		
		return result;
	}
	
	private BigInteger getNextA(BigInteger a) {
		String binaryString = a.toString(2);
		return new BigInteger(binaryString+"1", 2);
	}

	private int bitCount(BigInteger a, BigInteger b) {
		return a.bitCount() + b.bitCount();
	}

	public static void main(String[] args) throws FileNotFoundException {
		Scanner scan = new Scanner(new File(args[0]));
		int t = scan.nextInt();
		
		for (int i=1; i <= t; i++) {
			String n = scan.next();
			BitCounter bc = new BitCounter(n);
			System.out.println(String.format("Case #%d: %d", i, bc.maxBitCount()));
		}
	}
}

決勝戦は、どんな問題か楽しみです。