kojingharangの日記

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;
	}
};

ツイートする