AOJ1297 Swimming Jam - nanikakaのAOJ航海日誌

概要

2レーンからなるプールがあり、それぞれ一方通行で往路と復路である。N人の水泳者がいて常にそれぞれ決められたスピードで泳ぐ。レーン内で人を抜く泳ぎ方は禁止されている。レーンに入るときに同時に入る人が複数いた場合、飛び込む順序を泳ぐのが早い人順に変えることができる。N人はそれぞれ、1レーンを泳ぐのにかかる時間と、何往復泳ぎたいかを申請する。最初は全員同じレーンから同時に泳ぐ。全ての水泳者が申請した分の往復分泳ぎきるのにかかる時間を答えよ。
1 <= N <= 50
1 <= 1レーン泳ぐのにかかる時間 <= 300
1 <= 往復回数 <= 250

解法

面倒なシミュレーションです。
N人それぞれについて、申請回数分往復するのにかかる時間を求め、その最大値を答えとします。
ある人について考えるとき、その人より速く泳ぐ人は無視して構わないため、その人より泳ぐのが遅い人のみを考慮します。
lane[i][j]: 人物iが時刻jにどのレーンにいるか
を使います。ただし、1往復目の往路を1, 復路を2, 2往復目の往路を3, 復路を4...という風にしています。奇数なら往路、偶数なら復路にいることを表します。
begin[i][j]: 人物iがjのコースに入った時間
を表します。begin[0][2]なら、人物0が、1往復目の復路に入った時間が入っています。
ある人が時刻tにレーンに入り、その人の1レーンにかかる時間kだけ泳ぐと、時刻t+kに次のレーンに入るのですが、遅い人がいると、その人がレーンの端につくまでの分を待たないといけません。自分より遅い人が時刻t+k-1に、「別のレーンにいる」もしくは「同じレーンにいるが、泳ぎ始めたのが同じか、自分の方が早い」ときは待たずに次のレーンに行けます。これらを満たさない場合は待たなくてはなりません。

ソース

import java.util.Arrays;
import java.util.Scanner;

//Swimming Jam
public class AOJ1297 {

	class R implements Comparable<R>{
		int speed, lap, now;
		public R(int speed, int lap) {
			this.speed = speed;
			this.lap = lap;
		}
		public int compareTo(R o) {
			return o.speed-speed;
		}
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			R[] r = new R[n];
			for(int i=0;i<n;i++)r[i]=new R(sc.nextInt(), sc.nextInt()*2);
			Arrays.sort(r);
			int[][] lane = new int[n][150001];
			int[][] begin = new int[n][501];
			int t = 0, res = 0;
			for(int i=1;i<=r[0].lap;i++){
				begin[0][i] = t;
				for(int j=0;j<r[0].speed;j++){
					lane[0][t++] = i;
				}
				res = Math.max(res, t);
			}
			for(int i=1;i<n;i++){
				t = 0;
				for(int j=1;j<=r[i].lap;j++){
					begin[i][j] = t;
					for(int k=0;k<r[i].speed;k++){
						lane[i][t++] = j;
					}
					int max = t;
					for(int k=0;k<i;k++){
						if(lane[k][t-1]==0)continue;
						if(j%2!=lane[k][t-1]%2)continue;
						int x = lane[k][t-1];
						if(begin[i][j]<=begin[k][x])continue;
						int pos = t;
						while(lane[k][pos]==x)pos++;
						max = Math.max(max, pos);
					}
					while(t<max)lane[i][t++] = j;
					res = Math.max(res, t);
				}
			}
			System.out.println(res);
		}
	}

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