2012-05-12

TCO2012 Round2B - 300 BlurredDartboard

03:43 |

p[i] には 1～N(<= 50) のどれかが重複なく入っていたが、いくつか 0 になっている。適当な p[i] を選んで加算するのを K 回行う。同じのを複数回選んでいい。合計が確実に P(<= 10**9) 以上になるような最小の K を求める問題。

0 のやつを全部加算すると、隠れてる数の合計が確実に加算されることになる
なので、まずできるだけ max(0 のやつの合計, 0 じゃないやつの最大値) を使う。
残りは, 0 じゃないやつの最大値を使うか、0 のやつで最悪の選び方をしたとして小さい方から順に使うかのどちらか。

class BlurredDartboard {
	public:
	int minThrows(vector <int> p, int P) {
		int N=p.size();
		
		VI vis(N, 0);
		int ma=-1;
		REP(i, N) {
			if(p[i]>0) {
				vis[p[i]-1]=1;
				ma=max(ma, p[i]);
			}
		}
		VI hid;
		REP(i, N) if(vis[i]==0) hid.PB(i+1);
		int hidsum = accumulate(ALL(hid), 0);
		sort(ALL(hid));
		
		int ans=0;
		if(ma==-1 || hidsum > ma*hid.size()) {
			ans += P/hidsum*hid.size();
			P -= P/hidsum*hidsum;
		} else {
			ans += P/ma;
			P -= P/ma*ma;
		}
		cout<<ans<<" "<<P<<endl;
		if(P==0) return ans;
		
		int lans=0;
		int PP=P;
		REP(i, hid.size()) {
			PP-=hid[i];
			lans++;
			if(PP<=0) break;
		}
		if(PP>0) lans = 10000;
		cout<<lans<<endl;
		if(ma!=-1) lans = min(lans, (P+ma-1)/ma);
		cout<<lans<<" "<<ma<<endl;
		
		return ans+lans;
	}
};

TCO2012 Round2B - 550 HeavyBooks

03:43 |

ICPC world final の時事ネタｗ
本(50冊まで)とその重さが与えられる。TがM[0]冊選んで W にあげて、その中からWがM[1]冊をWからTに移して、TがM[2]冊をTからWに移して...を交互に繰り返す。最大M[50]まで。
Tは重さW-Tを最大化したい。Wは重さT-Wを最大化したい。最適に行動した場合の最終的な T, W の本の重さを求める問題。ただし複数同じだったら重さ T+W を最大化する。

残り40分くらい。
選び方は 50 C M[0] あるので賢くやる必要がある
最初に M[0] 個選んでしまえば、あとはお互いに一番重いものから M[i] 個渡せばいい。
なので、最初に選んだ本の重さをソートして番号をつけたとして、最後にどっちが何番目の本を持ってることになるかシミュレートできる。
という状況下で、W-T が最大になるようにソート済みの本とソート済みのM[0]冊の本を対応付ければいい。
どっちもソートしてあるので、M[0] 個を左から順に見ていって「今の本と対応付ける場合」と「次の本と対応付ける場合」で都合の良い方を再帰的に選ぶ。
対応は最初の本の数 * M[0] 通りなのでメモ化再帰でOK
値は、W-T, W+T のペアにすれば max で自然にいける。W-T, W+T が揃ってるので値の復元も足したり引いたりすればいい。

という方針で書いたけどサンプルが通らなくて直してるうちに終了。

（あとで）
方針は合ってたけど invalid を表す充分に小さな値が充分小さくなかったり終了条件が１コずれてたり値の復元の正負が逆だったりして良くない。最初に書く時に正確に書くべし。

↓あとで通したやつ

vector <int> BB;
VI w;

map<PII, PII> memo;
PII f(int bi, int wi) {
	PII key = MP(bi, wi);
	if(memo.count(key)) return memo[key];
	
	if(wi==w.size()) return MP(0, 0);
	if(bi==BB.size()) return MP(-100000000, -100000000);
	
	PII rest = f(bi+1, wi+1);
	if(w[wi]==0) rest.first-=BB[bi];
	else         rest.first+=BB[bi];
	rest.second+=BB[bi];
	
	PII restB = f(bi+1, wi);
	//cout<<bi<<" "<<wi<<" "<<rest<<" "<<restB<<endl;
	return memo[key] = max(rest, restB);
}

class HeavyBooks {
	public:
	vector <int> findWeight(vector <int> B, vector <int> M) {
		memo = map<PII, PII>();
		sort(ALL(B));
		
		w = VI(M[0], 1);
		int to=0;
		REP(i, M.size()-1) {
			int mo = M[i+1];
			for(int j=M[0]-1;j>=0;j--) {
				if(w[j]==1-to) {
					w[j]=to;
					mo--;
					if(mo==0) break;
				}
			}
			to=1-to;
		}
		cout<<w<<endl;
		BB=B;
		PII r = f(0, 0);
		cout<<r<<endl;
		vector<int> ans(2);
		ans[0]=-(r.first-r.second)/2;
		ans[1]=(r.first+r.second)/2;
		return ans;
	}
};

kojingharangの日記

2012-05-12

TCO2012 Round2B - 300 BlurredDartboard

TCO2012 Round2B - 550 HeavyBooks