Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-11-21SRM486(DIV1)

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);
	}
}