AOJ2004 Data Center on Fire

問題リンク Data Center on Fire

• 解法

エレベータのシミュレーション問題です。
まずはエレベータクラスの説明をします。
エレベータは[エレベータの識別ID, 容量, 停止時間, 現在のデバイス量, *状態*, 目標階, 現在位置の高さ, 速さ]のメンバを持ちます。
「状態」が肝になります。エレベータはシミュレーション中以下の状態と成り得ます。
NONE: 何もすることがない
GO: 積めるデバイスに空きがあるので目標階に向かっている途中
GET: 目標階に到着したので、ドアを開けてデバイスを積んでいる状態
BACK: 容量がMAX、もしくは2階以上に回収できるデバイスが残っていないので1階に向かっている
RELEASE: 1階に到着してドアを開けてデバイスを退避させている状態
これらは以下のような状態遷移図となります

状態遷移の条件を説明します。
GO→NONE: 目標階に向かっていたが2階以上に回収できるデバイスが無い且つ自身はデバイスを積んでいない
GO→GET: 目標階に到着
GO→BACK: 目標階に向かっていたが2階以上に回収できるデバイスが無い、しかし自身はデバイスを積んでいる
GET→BACK: デバイスをエレベータに積み終わった。その時に、容量がMAXである、もしくは2階以上に回収できるデバイスがない
GET→GO: デバイスをエレベータに積み終わった。その時に、容量に空きがある且つ2階以上に回収できるデバイスがある
BACK→RELEASE: 1Fに到着
RELEASE→NONE: 2階以上に回収できるデバイスが無い
RELEASE→GO: 2階以上に回収できるデバイスがある
さらに、階が焼失するFIREというイベントがあります。このイベントが起きたとき、GO状態のエレベータの目標階を更新する必要があります。
あとは、これを頑張って実装します。これらのイベントが起きたときに、GO状態になっているエレベータは発生したイベント間の時間の差分だけ、エレベータの位置を更新します。また、エレベータの状態の初期値は、回収できるデバイスがあるならGO, 無ければNONEです。
あと、問題文に明記されていないですが、1Fにおいてあるデバイスは既に回収済みと処理してしまってよさそうです。

• ソース

import java.util.PriorityQueue;
import java.util.Scanner;

//Data Center on Fire
public class AOJ2004 {

	final int NONE = 0, GO = 1, GET = 2, BACK = 3, FIRE = 4, RELEASE = 5;
	class E{
		int id, cap, stop, c, state, tar;
		double pos, v;
		public E(int id, int cap, int stop, double pos, double v) {
			this.id = id;
			this.cap = cap;
			this.stop = stop;
			this.pos = pos;
			this.v = v;
		}
	}
	class R implements Comparable<R>{
		int event, p;
		double t;
		public R(int event, int p, double t) {
			this.event = event;
			this.p = p;
			this.t = t;
		}
		public int compareTo(R o) {
			return (int)Math.signum(t-o.t);
		}
	}

	int N, M, target;
	double[] fh;
	int[] dev;
	E[] es;
	boolean ex;

	void next(){
		while(target>0&&dev[target]==0)target--;
	}
	boolean con(){
		if(target>1)return true;
		for(int i=0;i<M;i++)if(es[i].state!=NONE)return true;
		return false;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			N = sc.nextInt(); M = sc.nextInt();
			if((N|M)==0)break;
			target = N; ex = false;
			int H = sc.nextInt();
			fh = new double[N+1];
			for(int i=1;i<=N;i++)fh[i]=(i-1)*H;
			dev = new int[N+1];
			for(int i=1;i<=N;i++)dev[i]=sc.nextInt();
			next();
			es = new E[M];
			for(int i=0;i<M;i++){
				int c = sc.nextInt(), v = sc.nextInt(), stop = sc.nextInt(), x = sc.nextInt();
				es[i] = new E(i, c, stop, fh[x], v);
			}
			PriorityQueue<R> q = new PriorityQueue<R>();
			int[] fire = new int[N+1];
			int K = sc.nextInt(), tf = sc.nextInt(), tup = sc.nextInt(), tdn = sc.nextInt();
			for(int i=K-1;i>0;i--)fire[i]=fire[i+1]+tdn;
			for(int i=K+1;i<=N;i++)fire[i]=fire[i-1]+tup;
			for(int i=1;i<=N;i++)q.add(new R(FIRE, i, fire[i]+tf));
			for(int i=0;i<M;i++){
				if(target==1)es[i].state = NONE;
				else{
					es[i].state = GO; es[i].tar = target;
				}
			}
			int res = dev[1];
			dev[1] = 0;
			double t = 0, anst = 0;
			while(con()){
				int id = -1;
				double min = 1<<29;
				for(int i=0;i<M;i++){
					if(es[i].state!=GO)continue;
					double dt = t + Math.abs(fh[es[i].tar]-es[i].pos)/es[i].v;
					if(dt<min){
						min = dt; id = i;
					}
				}
				if(id!=-1&&(q.isEmpty()||!q.isEmpty()&&min<q.peek().t)){
					double dt = min-t;
					for(int i=0;i<M;i++){
						if(es[i].state!=GO)continue;
						if(fh[es[i].tar]<es[i].pos)es[i].pos-=es[i].v*dt;
						else es[i].pos+=es[i].v*dt;
					}
					int carry = Math.min(dev[es[id].tar], es[id].cap-es[id].c);
					es[id].c += carry;
					es[id].state = GET;
					q.add(new R(GET, id, min+es[id].stop));
					dev[es[id].tar] -= carry;
					if(es[id].tar>1)ex = true;
					if(dev[es[id].tar]==0){
						next();
						if(target>1){
							for(int i=0;i<M;i++){
								if(es[i].state!=GO)continue;
								es[i].tar = target;
							}
						}
						else{
							for(int i=0;i<M;i++){
								if(es[i].state!=GO)continue;
								if(es[i].c==0)es[i].state = NONE;
								else {
									es[i].state = BACK;
									q.add(new R(BACK, i, min+es[i].pos/es[i].v));
								}
							}
						}
					}
					t = min;
				}
				else{
					R r = q.poll();
					double dt = r.t-t;
					for(int i=0;i<M;i++){
						if(es[i].state!=GO)continue;
						if(fh[es[i].tar]<es[i].pos)es[i].pos-=es[i].v*dt;
						else es[i].pos+=es[i].v*dt;
					}
					if(r.event==GET){
						if(es[r.p].c==es[r.p].cap){
							es[r.p].state = BACK;
							es[r.p].tar = 1;
							q.add(new R(BACK, r.p, r.t+es[r.p].pos/es[r.p].v));
						}
						else{
							if(target>1){
								es[r.p].state = GO; es[r.p].tar = target;
							}
							else{
								es[r.p].state = BACK;
								es[r.p].tar = 1;
								q.add(new R(BACK, r.p, r.t+es[r.p].pos/es[r.p].v));
							}
						}
					}
					else if(r.event==BACK){
						es[r.p].pos = 0;
						es[r.p].state = RELEASE;
						q.add(new R(RELEASE, r.p, r.t+es[r.p].stop));
					}
					else if(r.event==RELEASE){
						anst = r.t;
						res += es[r.p].c; es[r.p].c = 0;
						if(target>1){
							es[r.p].state = GO; es[r.p].tar = target;
						}
						else es[r.p].state = NONE;
					}
					else if(r.event==FIRE){
						dev[r.p] = 0;
						next();
						for(int i=0;i<M;i++){
							if(es[i].state!=GO)continue;
							if(target>1)es[i].tar = target;
							else{
								if(es[i].c==0)es[i].state=NONE;
								else{
									es[i].state = BACK; es[i].tar = 1;
									q.add(new R(BACK, i, r.t+es[i].pos/es[i].v));
								}
							}
						}
					}
					t = r.t;
				}
			}
			System.out.printf("%d %.6f\n", res, ex?anst:0);
		}
	}

	public static void main(String[] args) {
		new AOJ2004().run();
	}
}