SRM 634 Div1 250 ShoppingSurveyDiv1

2014-09-26

18:37 |

商品がM個、N人がそれぞれの商品を最大１コ買った。i番目の商品がs[i]個売れた場合、商品をK種類以上買った人の最小値を求めよ。
1≦N≦500, 1≦M≦500, 0≦s[i]≦N, 1≦K≦M

考察
K種類買う人にはすべての種類の商品を買ってもらおう

貪欲でやってみよう
sを逆順ソートして, K種類以上の人→種類数が少ない人という順で貪欲にs[i]を配分していく
提出

貪欲じゃだめなパターンかもしれん。固い方法はないかしら
答えを決め打ちしたらどうか
そしたら→ s'[i] = max(0, s[i]-答え) としたときに全員が K 種類未満にできるかという問題に帰着する
最初のより良い答えが出る場合がある →まずい!!
答えを N 通りためしたら 500^3 になってしまう→まずい
答えで二分探索に変更
再提出

終了間際
4 4 {4 3 3 3 3 2 2} で 2 って答えがでるけど最初のコードが出した 3 が正しいんじゃねえの。(→間違い
最初のを提出
終了

4 4 {4 3 3 3 3 2 2} は 1 2 が 7 種類, 3 4 が 3 種類にできるので 2 でいいんじゃねぇかよ

challenge phase
がんばって2撃墜
自分のは生き延びる

Failed system test

(あとで)
やはり２回目の提出のやつが正しかった。しょんぼり。

↓passed in practice room

class ShoppingSurveyDiv1 {
	public:
	int minValue(int N, int K, vector <int> s) {
		int M=s.size();
		ll lo=-1,hi=N; // hi -> OK
		while(lo+1<hi) {
			ll ans=(lo+hi)/2;
//		REP(ans, N+1) {
			map<ll, ll> co;
			co[0]=N-ans;
			REP(i, M) {
				map<ll, ll> add;
				ll rest = max<ll>(0, s[i]-ans);
				FOR(e, co) {
					if(rest==0) break;
					ll use = min<ll>(e->second, rest);
	//				cout<<"use "<<use<<" for "<<e->first<<endl;
					e->second -= use;
					add[e->first+1] += use;
					rest-=use;
				}
				FOR(e, add) co[e->first]+=e->second;
	//			cout<<i<<" "<<s[i]<<" "<<co<<endl;
				assert(rest==0);
			}
			int ok=1;
			FOR(e, co) if(e->first>=K) ok=0;
			if(ok) hi=ans; else lo=ans;
		}
		return hi;
	}
};