Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 337 CardStraights

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

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

  • し、しまった・・・(無能)
    • ジョーカーが余るパターンで、左に配置するパターンを考慮してなかった
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CardStraights {

	public int longestStraight(int[] cards) {
		Arrays.sort(cards);
		
		int len = cards.length;
		int js = 0;
		List<Integer> normals = new ArrayList<Integer>();
		for (int i  = 0 ; i < len ; i++) {
			if (cards[i] == 0) {
				js++;
			} else {
				if (!normals.contains(cards[i])) {
					normals.add(cards[i]);
				}
			}
		}
		
		int cl = normals.size();
		
		int max = js;
		for (int i = 0 ; i < cl ; i++) {
			int left = js;
			int cont = 1;
			int from = normals.get(i);
			for (int j = i ; j < cl - 1 ; j++) {
				int x = normals.get(j+1) - normals.get(j) - 1;
				if (x <= left) {
					left -= x;
					cont += x + 1; 
				} else {
					cont += left;
					left = 0;
					break;
				}
			}
			
			if (i == 0 && from >= 2) {
				cont += Math.min(from - 1, left);
				left -= Math.min(from - 1, left);
			} else if (i >= 1 && left >= 1) {
				int d = normals.get(i) - normals.get(i-1) - 1;
				cont += Math.min(d, left);
				left -= Math.min(d, left);
			}
			if (left >= 1) {
				int yetanother = 1000000 - normals.get(cl-1);
				cont += Math.min(yetanother, left);
			}
			max = Math.max(max, cont);
		}
		return max;
	}
}