TopCoder SRM 631 Div2 Medium CatsOnTheLineDiv2

Div1 Mediumを簡略化した問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13392

問題

1次元に並んだセルがある。
初期状態でN箇所の座標P[i]のセル、それぞれC[i]匹ずつの猫がいる。
時間が１経つごとに、各猫は左右隣接マスに移動することができる(移動せずとどまっても良い)。

時間がTだけ経過したとき、各セルに2匹以上猫がいないようにできるか。

解法

まず入力値をP[i]が昇順となるようソートする。

後はiの小さい順に、P[i]にいる猫を左から詰めてセルに配置していくことを考える。
P[i-1]のセルから移動した一番右の猫の座標をAとすると、P[i]のセルにいる猫は一番左でB=max(A+1, P[i]-T)にとどまることができる。
するとP[i]にいるC[i]匹の猫はB～B+C[i]-1の座標に散らばるので、B+C[i]-1<=P[i]+TならP[i]にいた猫は異なるセルに移動することができる。
また、その際A=B+C[i]-1で更新していく。

class CatsOnTheLineDiv2 {
	public:
	string getAnswer(vector <int> position, vector <int> count, int time) {
		int N=position.size(),i;
		vector<pair<ll,ll> > P;
		FOR(i,N) P.push_back(make_pair(position[i],count[i]));
		sort(P.begin(),P.end());
		
		ll po=-1LL<<60;
		
		FOR(i,N) {
			ll hoge=max(po+1,P[i].first-time)-1+P[i].second;
			if(hoge>P[i].first+time) return "Impossible";
			po=hoge;
		}
		return "Possible";
		
	}
}

まとめ

端から詰めるのは定番ネタだね。
GCJでもホットドッグ屋を展開する似た問題が出たことがある。