Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-07SRM387 (Practice)

SRM 387 MarblesRegroupingEasy

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

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

  • 方針を検討
    • joker boxを決め打ちして探索
    • joker box以外で2種類以上のmarbleが入っていたらjoker boxに突っ込む
    • marbleが1種類だけならその種類ごとにカウント
    • カウントが2以上なら(カウント - 1)をjoker boxに突っ込む

public class MarblesRegroupingEasy {

	public int minMoves(String[] boxes) {
		int bl = boxes.length;
		int cl = boxes[0].length();
		int minMove = Integer.MAX_VALUE;
		for (int jb = 0 ; jb < bl ; jb++) {
			int mustMove = 0;
			int[] coltomove = new int[cl];
			for (int b = 0 ; b < bl ; b++) {
				if (b == jb) {
					continue;
				}
				int cnt = 0;
				int col = -1;
				for (int c = 0 ; c < cl ; c++) {
					if (boxes[b].charAt(c) >= '1')  {
						cnt++;
						col = c;
					}
				}
				if (cnt >= 2) {
					mustMove++;
				} else if (cnt == 1) {
					coltomove[col]++;
				}
			}
			for (int c = 0 ; c < cl ; c++) {
				if (coltomove[c] >= 2) {
					mustMove += coltomove[c] - 1;
				}
			}
			minMove = Math.min(minMove, mustMove);
		}
		return minMove;
	}
}