Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-30SRM339 (Practice)

SRM 339 BusTrip

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

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

  • 問題文のとおりにシミュレーションするだけ。
import java.util.Arrays;

public class BusTrip {
	class Bus {
		int total;
		int id;
		int[] begins;
		int[] next;
		Bus(String input, int i) {
			String[] strs = input.split(" ");
			begins = new int[101];
			next = new int[101];
			Arrays.fill(begins, -1);
			Arrays.fill(next, -1);
			int len = strs.length;
			
			total = 0;

			// total distance
			int prev =  Integer.valueOf(strs[0]);
			for (int j = 0 ; j < len ; j++) {
				int dg = Integer.valueOf(strs[j]);
				int diff = Math.abs(prev - dg);
				total += diff;
				begins[dg] = total;
				prev = dg;
			}
			total += Math.abs(prev - Integer.valueOf(strs[0]));

			// next
			for (int j = 0 ; j < len - 1 ; j++) {
				int from = Integer.valueOf(strs[j]);
				int to = Integer.valueOf(strs[j+1]);
				next[from] = to;
			}
			next[Integer.valueOf(strs[len-1])] = Integer.valueOf(strs[0]);
			
			id = i;
		}
	}

	public int returnTime(int N, String[] buses) {
		int bl = buses.length;
		Bus[] b = new Bus[bl];
		for (int i = 0 ; i < bl ; i++) {
			b[i] = new Bus(buses[i], i);
		}
		
		int time = -1;
		int now = 0;
		while (time <= 1000) {
			int bestbus = -1;
			int besttime = 100000;
			for (int i = 0 ; i < bl ; i++) {
				if (b[i].begins[now] == -1) {
					continue;
				}
				for (int c = 0 ; c < 1000 ; c++) {
					int cometime = b[i].begins[now] + b[i].total * c;
					if (cometime > time) {
						if (besttime > cometime) {
							besttime = cometime;
							bestbus = i;
						}
						break;
					}
				}
			}
			if (bestbus == -1) {
				System.out.println("err");
			}
			
			int go = b[bestbus].next[now];
			time = besttime + Math.abs(go - now);
			now = go;
			if (now == 0) {
				break;
			}
		}
		return (time >= 1001) ? -1 : time;
	}
}