2014-08-30

SRM 631 Div1 500 CatsOnTheLineDiv1

04:16 |

猫が数直線上の整数位置 p[i] のとこに c[i] 匹いる。各自１ターンで-1,0,+1 動ける。Tターン後に猫が２匹以上いる位置の数の最小値を求めよ。
1≦猫の数≦1000, |p[i]|≦10^8, c[i]≦10^8, 1≦T≦10^8

かたまりが１コの場合、c[i]/2 ターンあればそいつらは厚さ1に展開できる。
展開できないならどっちみち２匹以上の場所が１個以上できるので、余計に散らばらない分だけ塊のままでいる方が良い。
猫は [p[i]-T, p[i]+T] まで行けるので, 展開後の一番左の猫がいる範囲は [ p[i]-T, p[i]+T-c[i]+1 ]
一番左のかたまりは、展開できるならば一番左に展開するのが良い。
次のかたまりも、前のと重ならない範囲で展開できるならば一番左に展開する
... 結局左寄せ貪欲でいいんでは
だめならかたまりのまま可能な限り右に置く
みたいな

Failed system test

(あとで)

展開できて前のと重ならないかどうかチェックするまえに、直近塊で置いたやつのとこにマージできるかを最初に見るべきだったようだ。
展開して最後に置いた位置が右に移動しちゃうより塊にマージして最後に置いた位置変わらず　の方がいい。

安全にDP(など微妙な貪欲より計算量は悪いけど十分解ける時間だしより安全な方法)で...という解き方が課題である。。

passed in practice room

class CatsOnTheLineDiv1 {
	public:
	int getNumber(vector <int> P, vector <int> C, int T) {
		int N=P.size();
		vector<pair<int, int> > w(N);
		REP(i, N) w[i] = MP(P[i], C[i]);
		sort(ALL(w));
		REP(i, N) P[i]=w[i].first, C[i]=w[i].second;
		int ans = 0;
		ll next = -(1LL<<60);
		ll m = -(1LL<<60);
		REP(i, N) {
			ll hl = P[i]-T;
			ll hr = P[i]-C[i]+1+T;
			if(P[i]-T<=m && m<=P[i]+T) continue; // これを最初にチェックすべき
			if(hr<next || C[i]/2 > T) {
				ans++;
				m = P[i]+T;
			} else {
				next = max(next, hl) + C[i];
			}
		}
		return ans;
	}
};

kojingharangの日記

2014-08-30

SRM 631 Div1 500 CatsOnTheLineDiv1