Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-25SRM300台を練習していく

SRM 302 DivisorInc

|  SRM 302 DivisorInc - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 302 DivisorInc - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6186

はじめはNを増やすように探索しようかと考えたが、間に合わないので方針を転換。

Mを減らしながら、メモ化再帰ならいける。

こういう問題を素早く解くのは苦手だ・・・110点ぐらい。


import java.util.ArrayList;
import java.util.List;

public class DivisorInc {

	public int inf = 99999999;

	public List<Integer> sel(int x) {
		List<Integer> l = new ArrayList<Integer>();
		int sq = (int)Math.sqrt(x);
		for (int i = 2 ; i <= sq ; i++) {
			if (x % i == 0) {
				l.add(i);
				if (i != 2) {
					l.add(x / i);
				}
			}
		}

		return l;
	}

	public int memo[] = new int[100001];

	public int rsearch(int N, int M) {
		if (memo[M] != 0) {
			return memo[M];
		}

		if (N == M) {
			return 0;
		}
		if (N > M) {
			return inf;
		}

		List<Integer> s = sel(M);
		java.util.Collections.sort(s);
		int lne = s.size();

		int min = inf;
		for (int i = lne - 1 ; i >= 0 ; i--) {
			min = Math.min(min, rsearch(N, M - s.get(i)) + 1);
		}
		memo[M] = min;
		return min;
	}

	public int countOperations(int N, int M) {
		if (N == M) {
			return 0;
		}
		if (sel(N).size() * sel(M).size() == 0) {
			return -1;
		}
		int ret = rsearch(N, M);
		if (ret >= inf) {
			return -1;
		}
		return ret;
	}
}