kmjp's blog

競技プログラミング参加記です

Google Code Jam 2017 Round 2 : B. Roller Coaster Scheduling

なんとか気づいてよかった。
https://code.google.com/codejam/contest/5314486/dashboard#s=p1

問題

遊園地に1~NのN個の席があるジェットコースターがある。
遊園地にはC人の来訪者がおり、すでにM枚のチケットが発行されている。
各チケットは、だれがどの席に乗れるかが書かれている。

ジェットコースターを何回か動かし、全チケットを利用させることを考える。
この時、1人は1回で1つのチケットしか消費できないし、1の席は当然1人しか利用できない。

各人が何回目のジェットコースターでどのチケットを使うかを任意に設定できるとき、ジェットコースターを動かす回数を最小化したい。
この時、チケットの昇格ができる。チケットを昇格すると、より番号の小さい席に利用者を移動させることができる。

ジェットコースターの動かす回数の最小値を答えよ。
また、その時に必要なチケットの昇格回数を求めよ。

解法

1人で最大A枚のチケットを持つ人がいたとすると、最低A回はジェットコースターを動かさなければならない。

ここで、重要な知見として、逆にB回(B≧A)ジェットコースターを動かすならば、だれが何回目のジェットコースターに乗るかを考える必要はなく、各席最大B回までチケットを割り当てられるということがある。
まず、何回目に乗るかを無視して、各席にどの人が何回乗るかだけを考える。
もしかしたら同じ回の複数の席に同じ人が割当たってしまうかもしてないが、その場合その人はどちらかの席を別の回の人と交換すればよい。
これを繰り返せば、必ず1人が同じ回に2回以上乗らない組み合わせができる。

ここまでわかれば後は簡単である。
回数BをAから順にインクリメントしていき、条件を満たせる最小のBを求めよう。
人と順番は無視していいので、f(x) := x番の席の発行済みチケット枚数 とする。
1番の席から順に、x番の席にf(x)回のチケットを割り当てることを考える。
f(x)<Bならx番の席はB-f(x)個余るし、f(x)>Bならf(x)-B個不足する。
不足した分は、チケットの昇格により1~(x-1)番のあまり席に移動しよう。
ただしあまりが十分にない場合、B回では条件を満たさないので、Bをインクリメントする。

int N,C,M;
int P[1010],B[1010];
vector<int> PP[1010];
vector<int> E;
int num[1010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>C>>M;
	FOR(i,C) PP[i].clear();
	ZERO(num);
	FOR(i,M) {
		cin>>P[i]>>B[i];
		PP[B[i]-1].push_back(P[i]-1);
		num[P[i]-1]++;
	}
	
	int ma=0;
	FOR(i,C) ma=max(ma,(int)PP[i].size());
	int hoge;
	while(1) {
		int lef=0;
		int ok=1;
		hoge=0;
		FOR(i,N) {
			if(num[i]<=ma) {
				lef+=ma-num[i];
			}
			else {
				lef -= num[i]-ma;
				hoge += num[i]-ma;
				if(lef<0) {
					ok=0;
					break;
				}
			}
		}
		
		if(ok==1) break;
		ma++;
	}
	
	_P("Case #%d: %d %d\n",_loop,ma,hoge);
}

まとめ

幸い本番そこそこの時間でこの知見に気が付けたのでよかった。