AOJ1271 Power Calculus

AOJ Volume12

問題リンク Power Calculus

  • 概要

x^nを求めるための最小乗除回数を答えよ。最初x^1から始まり、計算の途中で表れたx^kを使ってx^iから、x^(i+k)もしくはx^(i-k)を得ることができる。
1 <= n <= 1000

  • 解法

反復深化法を使って解きました。自分がこの方法を使うのはこの問題が初めてでした（どーでもいい）。
自分の考えを整理する意味も込めてちょっと詳細に解法の説明をしようかなと思います。
反復深化法は、まぁ基本深さ優先探索なのですが、潜る深さDが決まっているのが特徴らしいです。このDを、解が求まるまで増やしていくので、ノードの訪問順は幅優先探索とだいたい似ていることになります。当然、ノードの浅い場所は何度も訪れるので無駄なのですが、メモリが節約できるのがイイ感じです。また、ある深さのノードに居て、そのノードから深さDまで潜っても絶対に解が得られないと分かるような条件が存在する場合は更に探索空間を小さくできます。
自分のソースも枝刈りの条件や、解が速く求まりそうな工夫を色々凝らしています。
まず、配列kには、その途中で得られた指数たちが格納されます。配列uは指数Nを作成したことがあるかどうかの真偽値が入っています。再帰メソッドの説明をします。
boolean dfs(int d, int x, int max, int len);
残りの潜る深さ d
今注目する指数 x
これまで生成した中で最大の指数 max
配列kの長さ len
dfsの返り値は解が見つかったか否か
dfsの中のアルゴリズムを書き下してみます。

1. d==0のとき
　もう探索できないので指数nを作れているかどうかを調べて終了
2. d==1のとき
　残り1回しか潜ることができない。なので、xとnの差の絶対値の分の指数が求められているならばnを作ることができると分かる。それを調べて終了する。
3. 配列kの後ろの方から順に見ていく
3-1. s = x+k[i]を次の注目指数とする。sが既に求められている指数であったり、0未満であったり、nから離れ過ぎているとき(nの2倍よりも大きい値である場合としています)は調べない。
3-2. sをreach()メソッドに渡して、解にたどり着くことができる可能性があるかどうかを調べる。可能性があれば再帰する。これをs = x-k[i], s = k[i] - xについても同様に処理する。

色々補足を。nの2倍より大きいsならば探索をしていないところですが、これは勘のようなものです。nの2倍より大きい値を使わない方がより短いステップで解にたどり着くことができるんじゃないかと・・・。
reach()メソッドは、単純に、その値から深さDまでに一番指数を大きくするような潜り方をしたときにnに届くかを調べているだけです。
3のところで配列を後ろから見て言っているのは、潜り方をより解に近付けるためです。基本的に配列の後ろの方に値が大きいものが収まるはずなので、値が大きい方から探索をした方が、より解に近付くという考えがあったからです。実際にこれで結構な高速化ができました。

自分の最初の反復深化法はこんな仕上がりになりました。これは色々な探索の難問に応用できそうで面白そうです。

ちなみに、ローカルマシンで、Nを1〜1000の場合全てについて求めてみると58秒程度の実行時間がかかりました。恐る恐るサブミットしてみたら6500msくらいで終わってくれました。周りの方の提出履歴を見るともっと速く解けるみたいですね。

  • ソース
import java.util.Scanner;

//Power Calculus
public class AOJ1271 {

	int n;
	int[] k;
	boolean[] u;

	boolean reach(long b, long x, int rest){
		long r = b+x;
		while(rest--!=0)r+=r;
		return n<=r;
	}

	boolean dfs(int d, int x, int max, int len){
		if(d==0){
			return u[n];
		}
		if(d==1){
			return u[Math.abs(x-n)];
		}
		for(int i=len-1;i>=0;i--){
			int s = k[i]+x;
			if(!(2*n<s||u[s]||!reach(s, Math.max(max, s), d-1))){
				u[s] = true;
				k[len] = s;
				if(dfs(d-1, s, Math.max(max, s), len+1))return true;
				u[s] = false;
			}
			s = x-k[i];
			if(!(s<0||!reach(s, max, d-1)||u[s])){
				u[s] = true;
				k[len] = s;
				if(dfs(d-1, s, max, len+1))return true;
				u[s] = false;
			}
			s = k[i] - x;
			if(!(s<0||!reach(s, max, d-1)||u[s])){
				u[s] = true;
				k[len] = s;
				if(dfs(d-1, s, max, len+1))return true;
				u[s] = false;
			}
		}
		return false;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			int x = 1, res = 0;
			while(x<n){
				x*=2; res++;
			}
			for(;;){
				u = new boolean[2500];
				k = new int[res+1];
				u[1] = true;
				k[0] = 1;
				if(dfs(res, 1, 1, 1)){
					System.out.println(res); break;
				}
				res++;
			}
		}
	}

	public static void main(String[] args) {
		new AOJ1271().run();
	}
}