Hatena::Grouptopcoder

TopCoder戦記

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

2009-12-23

SRM456 DIV2 Level Two(500pt.)

| 19:23

http://www.topcoder.com/stat?c=problem_statement&pm=10699&rd=13909

アルゴリズムを再構成したものです。斜め方向の移動だけで行けるものとそうでないものに分け、行けないものは斜め方向の移動だけで1マス下に移動してから前進することで到達します。

public class NewSilverDistance {
	public int minSteps(int sx, int sy, int gx, int gy) {
		final int dx = Math.abs(gx - sx);
		final int dy = gy - sy;
		if (((dx + dy) % 2) == 0) {
			return Math.max(dx, Math.abs(dy));
		} else {
			return Math.max(dx, Math.abs(dy - 1)) + 1;	// +1は前進する分
		}
	}
}

2009-09-13SRM430 DIV2

SRM430 DIV2 Level Two(500pt.)

| 10:12

http://www.topcoder.com/stat?c=problem_statement&pm=9921&rd=13521

特定の整数aが与えられたとき、a + b == a | b であるbのうちk番目に小さいものを求める。

当初は考えたアルゴリズムをキューを介して実現しましたが、パフォーマンス及び可読性の面から好ましくないと判断して純粋なビット演算を用いた実装にリファクタリングしています。


まずはリファクタリング前のコード。

// 421.79 pt.

import java.util.LinkedList;
import java.util.Queue;

public class CopyOfBitwiseEquations {
	public long kthPlusOrSolution(int x, int k) {
		Queue<Long> queue = f(x, k);
		long result = 0L;
		while (k > 0) {
			Long p = queue.poll();
			if (k % 2 == 1) {
				result += p;
			}
			k >>= 1;
		}
		return result;
	}

	private Queue<Long> f(int x, int k) {
		k = 1 + (int)Math.ceil(Math.log(k) / Math.log(2));
		Queue<Long> list = new LinkedList<Long>();
		for (long i = 1L; list.size() < k; x >>= 1, i <<= 1) {
			if (x % 2 == 0) {
				list.add(i);
			}
		}
		return list;
	}
}

上記のコードは正常に動作しますが、キューの役割がわかりにくく直感的ではありません。書いた本人もキューやその値に対して明確な意味づけができず、変数名などが適当になっています。

そこでシンプルにビット演算のみで作成し直したのが以下のコードです。算術シフトと論理シフトの使い分けやint型を32ビット以上右シフトしたときの動作異常などに注意する必要があり、コードは短いものの技術的にはややこしいコードになっています。しかしこれらを知った上で読めば、ロジックを端的に表現したわかりやすいコードであることがご理解いただけるのではないでしょうか。

// refactored
public class BitwiseEquations {
	public long kthPlusOrSolution(int x, int k) {
		long result = 0L;

		for (int i = 0; k > 0 && i < 64; ++i) {
			if (i >= 32 || (x >>> i) % 2 == 0) {	// int型を32以上右シフトすると動作異常
				if (k % 2 == 1) {
					result += 1L << i;
				}
				k >>= 1;			// kは必ず正なので算術シフトで良い
			}
		}
		return result;
	}
}