Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-22SRM366 (Practice)

SRM 366 GuitarConcert

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

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

  • ギターの数が少ないので、全探索するだけに見える
    • 2^10 *10 * 50 = 500,000 ぐらい
  • ゴリゴリ書く。
    • サンプル通った。
    • 特に間違ってない気がするのでそのまま出した
  • WA
    • そうか、比べる前にソートしなきゃいけないのか
    • 直したら通った。
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class GuitarConcert {
	public boolean isGreater(String[] a, String[] b) {
		int al = a.length;
		int bl = b.length;
		int m = Math.min(al, bl);
		for (int i = 0 ; i < m ; i++) {
			int comp = a[i].compareTo(b[i]);
			if (comp <= -1) {
				return false;
			} else if (comp >= 1) {
				return true;
			}
		}
		return true;
	}
	
	public String[] buyGuitars(String[] gn, String[] gs) {
		int gl = gn.length;
		int sl = gs[0].length();
		boolean[][] graph = new boolean[gl][sl];
		for (int i = 0 ; i < gl ; i++) {
			for (int j = 0 ; j < sl ; j++) {
				if (gs[i].charAt(j) == 'Y') {
					graph[i][j] = true;
				}
			}
		}
		
		boolean[][] compgraph = new boolean[1<<gl][sl];
		int bnum = -1; 
		int bgnum = 0;
		String[] best = null;
		for (int i = 1 ; i < (1<<gl) ; i++) {
			for (int g = 0 ; g < gl ; g++) {
				if ((i & (1<<g)) >= 1) {
					for (int s = 0 ; s < sl ; s++) {
						if (graph[g][s]) {
							compgraph[i][s] = true;
						}
					}
				}
			}
			int cnt = 0;
			for (int s = 0 ; s < sl ; s++) {
				cnt += (compgraph[i][s]) ? 1 : 0;
			}
			if (bnum < cnt) {
				bnum = cnt;
				bgnum = Integer.bitCount(i);
				best = new String[bgnum];
				int idx = 0;
				for (int g = 0 ; g < gl ; g++) {
					if ((i & (1<<g)) >= 1) {
						best[idx] = gn[g];
						idx++;
					}
				}
				Arrays.sort(best);
			} else if (bnum == cnt) {
				int num = Integer.bitCount(i);
				String[] newset = new String[num];
				int idx = 0;
				for (int g = 0 ; g < gl ; g++) {
					if ((i & (1<<g)) >= 1) {
						newset[idx] = gn[g];
						idx++;
					}
				}
				Arrays.sort(newset);
				if (bgnum > num) {
					bgnum = num;
					best = newset.clone();
				} else if (bgnum == num) {
					if (!isGreater(newset, best)) {
						best = newset;
					}
				}
			}
		}

		if (bnum <= 0) {
			return new String[]{};
		}
		
		Arrays.sort(best);
		
		return best;
	}
}