Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-11-21SRM486(DIV1)

SRM486 第一問(300pt) OneRegister

|  SRM486 第一問(300pt) OneRegister - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM486 第一問(300pt) OneRegister - hama_DU@TopCoderへの道

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

うーむ。

  • 1にしたいなら「/」一つでいいのか。s = tならなにもしなくていいよね。
    • 特殊なサンプルが通るようにコーナーケースを書いた。
  • 「+」と「*」の再帰で解けるかな?かな?
    • t % s > 0 のときは、一旦「/+」「2」にしてから再帰関数にぶっ込む。
    • そうじゃないときはそのままぶっ込む。

サンプル通った。

  • (s, t) = (1, 1000000000) でstack overflowした。
    • 再帰が深く入りすぎたのかな?
  • 関数引数をlongにしたら大丈夫だった。
  • 提出。

システムテスト落ちた…

  • なんで?
    • t % s = 0 だったので、そのまま再帰にぶっ込んでた
    • t % s = 0 の場合でも、最初に「/+」して 2にする場合を考慮してなかった!

汚いコードになってしまったが…まぁいい

  • 提出。通った
public class OneRegister {

	public int Goal;
	public static final String OK = ":-)";
	public static final String NG = ":-(";
	public String answer;

	public String search(long s, String now) {
		if (s > Goal) {
			return NG;
		} else if (s == Goal){
			if (answer.equals("") || now.length() < answer.length() ||
					(now.length() == answer.length() && now.compareTo(answer) < 0) ) {
				answer = now;
			}
			return OK;
		}

		String mul = search(s * s, now + "*");;
		String add = search(2 * s, now + "+");
		if (add.equals(NG) && mul.equals(NG)) {
			return NG;
		} else {
			return OK;
		}
	}

	public String getProgram(int s, int t) {
		Goal = t;
		if (s == t) {
			return "";
		}
		if (t == 1) {
			return "/";
		}

		answer = "";
		String ans = "";
		if (t % s != 0) {
			ans += "/+";
			s = 2;
			search(s, ans);
		} else if (s == 1) {
			search(2, "+");
		} else {
			search(s, ans);
			search(2, "/+");
		}

		if (answer == "") {
			return NG;
		}
		return answer;
	}
}


SRM486 第二問(450pt) QuickSort

|  SRM486 第二問(450pt) QuickSort - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM486 第二問(450pt) QuickSort - hama_DU@TopCoderへの道

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


ん?

  • 普通にメモ化再帰(数値の列に対して、コストを保存)でいいんでね
  • gorigori実装
  • テストしてみる
    • サンプル通った
    • 1〜50までの数値をshuffleしてテストケース生成して通してみる
      • 間に合った。
  • Systestもあっさり通過。あれっ、簡単…

import java.util.ArrayList;
import java.util.HashMap;

public class QuickSort {

	public HashMap<ArrayList<Integer>, Double> memo
	 = new HashMap<ArrayList<Integer>, Double>();

	public int[] toArray(ArrayList<Integer> list) {
		int a[] = new int[list.size()];
		int idx = 0;
		for (int i : list) {
			a[idx] = i;
			idx++;
		}
		return a;
	}

	public double cost(int[] L) {
		int len = L.length;
		if (len == 1) {
			return 0;
		}
		if (len == 2) {
			if (L[0] > L[1]) {
				return 1;
			}
			return 0;
		}

		ArrayList<Integer> x = new ArrayList<Integer>();
		for (int i : L) {
			x.add(i);
		}
		if (memo.containsKey(x)) {
			return memo.get(x);
		}

		double cost = 0;
		for (int i = 0 ; i < len ; i++) {
			cost += cost(L.clone(), i);
		}
		cost = cost / len;
		memo.put(x, cost);

		return cost;
	}

	public double cost(int[] L, int idx) {
		int len = L.length;
		int val = L[idx];
		ArrayList<Integer> smaller = new ArrayList<Integer>();
		ArrayList<Integer> larger = new ArrayList<Integer>();
		double cost = 0;
		for (int i = 0 ; i < len ; i++) {
			if (L[i] < val) {
				if (i > idx) {
					cost++;
				}
				smaller.add(L[i]);
			} else if (L[i] > val) {
				if (i < idx) {
					cost++;
				}
				larger.add(L[i]);
			}
		}

		int[] small = toArray(smaller);
		int[] large = toArray(larger);

		double smallcost = 0;
		int smallsize = small.length;
		if (smallsize > 0) {
			smallcost = cost(small);
		}

		double largecost = 0;
		int largesize = large.length;
		if (largesize > 0) {
			largecost = cost(large);
		}
		cost += smallcost + largecost;
		return cost;
	}

	public double getEval(int[] L) {
		return cost(L);
	}
}