kmjp's blog

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

TopCoder SRM 631 Div1 Medium CatsOnTheLineDiv1

DPじゃなく貪欲で解けるのか…。
http://community.topcoder.com/stat?c=problem_statement&pm=13279

問題

基本的な条件はDiv2 Mediumと同じ。
TopCoder SRM 631 Div2 Medium CatsOnTheLineDiv2 - kmjp's blog

Div2では今回は2匹以上猫がいるセルの有無が求められたが、今度はどうしても2匹以上猫がいるセルが必要であれば、そのセル数の最小値を求めよ。

解法

基本的に左から詰めていくのはDiv2と同じ。
ただどうしても猫が2匹以上いるマスが出てきてしまう場合、そのマスをできるだけ右に寄せる。
例えばP[i]にいた猫を1匹ずつ配置できない場合、あきらめてP[i]+Tに全部集める(この際、2匹以上猫がいるセルが1個増加する)。
そうすると、P[i]以降の猫でP[i]+T>=P[j]-Tを満たすP[j]の猫は、皆P[i]+Tに集めてしまえば2匹以上いるセルは増えない。
また、P[j]の猫を左から1匹ずつ配置するより、P[j]の猫の右端が左端に来る。

ということで、まとめると以下の貪欲で行ける。

  • すでに2匹以上いるマスに到達可能な猫はそこに集める。
  • 到達不可な場合、2匹以上いるセルを作らずに済むならDiv2同様に左から猫を詰める。
  • 上記処理で2匹以上いるセルを作らざるを得ない場合、できるだけ右側に作る。
class CatsOnTheLineDiv1 {
	public:
	int getNumber(vector <int> position, vector <int> count, int time) {
		int N=position.size();
		int i,j,x,y;
		
		vector<pair<ll,ll> > P;
		FOR(i,N) P.push_back(make_pair(position[i],count[i]));
		sort(P.begin(),P.end());
		int ret=0;
		ll po=-1LL<<60,lm=-1LL<<60;
		
		FOR(i,N) {
			if(lm>=P[i].first-time) continue;
			ll hoge=max(po+1,P[i].first-time)-1+P[i].second;
			if(hoge>P[i].first+time) {
				lm=P[i].first+time;
				ret++;
			}
			else {
				po=hoge;
			}
		}
		return ret;
	}
}

まとめ

本番はガリガリDPやったんだけど、なぜかSystestで落ちてしまった。