Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-15SRM300台を練習していく part9

SRM 321 WeirdSort

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

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

てきとーに書いたら通ってしまった。

辞書順最小だからdfsでよくね

⇒ {1, 1, 1, 1, …, 1, 2} なパターンだとTLEする

⇒ じゃあ同じ数字をまとめちゃおう(上の例だと、{1, 2} ⇒ {2, 1} ⇒ {2, 1, 1, ... , 1} とする)

⇒ {1, 1, 2, 2, 4, 4} みたいなパターンでWAする(正解は {1, 1, 4, 2, 2, 4} で、4が分離する形になる)

⇒ それじゃ同じ数字を1個とn-1個に分けてまとめよう

⇒ 通った


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

public class WeirdSort {

	int[] _ans;
	int len;
	
	public void dfs(int i, int prev, int[] now) throws Exception {
		if (i > 0) {
			_ans[i-1] = prev;
		}
		if (i == len) {
			throw new Exception();
		}
		for (int a = 0 ; a < len ; a++) {
			if (now[a] != -1 && now[a] != prev + 1) {
				int[] next = now.clone();
				next[a] = -1;
				dfs(i+1, now[a], next);
			}
		}
	}
	
	public int[] sortArray(int[] dat) {
		int[] cnt = new int[1001];
		List<Integer> nlist = new ArrayList<Integer>();
		for (int d : dat) {
			cnt[d]++;
			if (cnt[d] == 1) {
				nlist.add(d);
			}
			if (cnt[d] == 2) {
				nlist.add(d);
			}
		}
		len = nlist.size();
		int[] data = new int[len];
		for (int i = 0 ; i < len ; i++) {
			data[i] = nlist.get(i);
		}
		java.util.Arrays.sort(data);
		
		_ans = new int[len];
		try {
			dfs(0, -9999, data);
		} catch (Exception e) {
		}
		
		int[] ans = new int[dat.length];
		boolean[] hit = new boolean[1001];
		int ansidx = 0;
		for (int i = 0 ; i < len ; i++) {
			if (!hit[_ans[i]]) {
				hit[_ans[i]] = true;
				cnt[_ans[i]]--;
				ans[ansidx] = _ans[i];
				ansidx++;
			} else {
				for (int a = 0 ; a < cnt[_ans[i]] ; a++) {
					ans[ansidx] = _ans[i];
					ansidx++;
				}
			}
		}
		return ans;
	}
}