Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-17SRM371, SRM372 (Practice)

SRM 372 RoadConstruction

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

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

  • 問題分の通りに愚直にシミュレーションする
    • それだけなのだが、20分もかかってしまった
import java.util.ArrayList;
import java.util.List;

public class RoadConstruction {
	class Car {
		int id;
		boolean yielded;
		boolean isd;
		Car(int i, char x) {
			id = i;
			yielded = false;
			isd = (x == 'D');
		}
	}
	
	public int getExitTime(String[] currentLanes) {
		int len = currentLanes.length;
		Car[] cars = new Car[2510];
		int caridx = 0;
		int[][] lanes = new int[52][52];
		int[] laneidx = new int[52];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < currentLanes[i].length() ; j++) {
				char c = currentLanes[i].charAt(j);
				cars[caridx] = new Car(caridx, c);
				lanes[i][j] = caridx;
				caridx++;
			}
			lanes[i][currentLanes[i].length()] = -1;
		}
		int turn = 0;
		while (true) {
			List<Integer> candidates = new ArrayList<Integer>();
			int willexit = -1;
			for (int i = 0 ; i < len ; i++) {
				int cid = lanes[i][laneidx[i]];
				if (cid >= 0) {
					if (cars[cid].yielded) {
						willexit = i;
						break;
					} else {
						candidates.add(i);
					}
				}
			}
			if (candidates.size() > 0) {
				if (willexit == -1) {
					willexit = candidates.get(candidates.size()-1);
					candidates.remove(candidates.size()-1);
				}
				for (int c : candidates) {
					cars[lanes[c][laneidx[c]]].yielded = true;
				}
			}
			if (willexit == -1) {
				break;
			} else {
				int exitid = lanes[willexit][laneidx[willexit]];
				if (cars[exitid].isd) {
					break;
				}
				laneidx[willexit]++;
			}
			turn++;
		}
		return turn;
	}
}