TopCoder SRM 739 Div1 Medium HungryCowsMedium

なんかすぐ方針が見えて最多得点だった。
http://community.topcoder.com/stat?c=problem_statement&pm=15100

問題

１次元の座標軸で表せる牧場がある。
N頭の牛がいずれも初期状態で原点におり、それぞれC[i]の量の牧草を食べたがっている。
牧場ではM箇所に納屋があり、その座標はP[j]である。

納屋には無限の牧草があるが、1度に1頭の牛しか牧草を食べることができない。
牛は時間１ごとにそれぞれ以下の行動をとることができる。

• 座標軸上を１移動する
• 納屋にいるとき、牧草を1食べる(上記のとおり、1つの納屋では同時に1頭しかこの行動をとれない)

各牛を最適に行動させたとき、全牛が所望の量の牧草を食べきる最短時間はいくつか。

解法

前に進んだ牛が後ろに戻ることが有効なケースはない(あとで戻るような牛がいたら、先にそいつに草を食べさせた方が移動時間が無駄にならない)ので、牛は前にしか進まないものとする。
あとは時刻で二分探索する。
時刻が求まれば、各納屋への移動時間を引くことでその納屋で供給できる牧草の量が確定する。
ただ、全体でどれだけ牧草があっても、各牛は１度に１か所の納屋でしか牧草を食べられない。
よって、各牛が牧草を食べる納屋を探索するとき、残供給量が最大の納屋の分しか食べることができない。

これを踏まえ、各納屋の残共有量に対し条件を満たすか判定する。
自分は以下の手順で判定した。

• 各牛をC[i]の降順に並べ、以下判定する。
  • C[i]を超える残供給量の納屋があるか判定。なければ条件は満たせない。
  • 条件を満たす場合、手前の納屋から順に計C[i]食べていく。

class HungryCowsMedium {
	int N,M;
	vector<int> C,P;
	public:
	
	int ok(ll v) {
		vector<ll> T;
		FORR(p,P) if(v>p) T.push_back(v-p);
		
		FORR(c,C) {
			int ok=0;
			FORR(t,T) if(t>=c) ok=1;
			if(ok==0) return 0;
			
			ll a=c;
			FORR(t,T) {
				ll d=min(t,a);
				t-=d;
				a-=d;
			}
		}
		return 1;
	}
	
	
	long long getWellFedTime(vector <int> A, vector <int> B) {
		C=A;
		P=B;
		sort(ALL(C));
		reverse(ALL(C));
		sort(ALL(P));
		
		ll ret=(1LL<<50)-1;
		for(int i=49;i>=0;i--) if(ok(ret-(1LL<<i))) ret-=1LL<<i;
		return ret;
	}
}

まとめ

このMediumはシンプルな問題設定でいいね。
EasyとHardがなんか微妙な問題なので、今回の自分の中での評価はあまり高くなかったり。
自己最高順位を取れたのはいいんだけどさ。