Topcoder SRM 486 div2 500 "OneRegister"

問題：http://www.topcoder.com/stat?c=problem_statement&pm=10992 （要ログイン）

プラクティス．

ある数字が与えられたときにその数字自身に対して+,-,*,/の操作を行うことで指定された数値にするための操作列を求める．

それぞれの操作を施すことを選ぶので4のべき乗になると思ったのでBFSで操作の結果が対象の値となる最短を求めようとした．本番では最短がいくつかあるときに辞書順になることを読み逃してアウト．本番中は自分で書いてて気づかなかったけど-の場合は必ず0になるから考慮しなくてもいいみたい．あと，double型にする必要はなさそう．実質の値の変化は+と*だけで-は無し，/は確実に1になるはずだから．

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class OneRegister {

	public String getProgram(int s, int t) {
		Queue<C> q = new LinkedList<C>();
		q.add(new C(" ", s));
		Set<Double> set = new HashSet<Double>();
		while (q.size() > 0) {
			C c = q.poll();
			if (Math.abs(c.v - t) < 1e-5) {
				String result = c.op;
				for(C cc : q){
					if(c.op.length() == cc.op.length() && Math.abs(c.v - cc.v) < 1e-5){
						result = result.compareTo(cc.op) <= 0 ? result : cc.op;
					}
				}
				return result.trim();
			}
			if (!set.add(c.v)) {
				continue;
			}
			if (c.v > 1e-5) {
				if (!c.op.endsWith("*") && Math.abs(c.v - 1) > 1e-5) {
					q.add(new C(c.op + '/', c.v / c.v));
				}
				if (!c.op.endsWith("/") && c.v * c.v <= t) {
					q.add(new C(c.op + '*', c.v * c.v));
				}
				// if (!c.op.endsWith("+")&&Math.abs(c.v - c.v) > 1e-5) {
				// q.add(new C(c.op + '-', c.v - c.v));
				// }
				if (!c.op.endsWith("-") && c.v + c.v <= t) {
					q.add(new C(c.op + '+', c.v + c.v));
				}
			}
		}
		return ":-(";
	}

	class C {
		String op;
		double v;

		public C(String op, double v) {
			this.op = op;
			this.v = v;
		}

		@Override
		public String toString() {
			return "C [op=" + op + ", v=" + v + "]";
		}

	}
}