Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/09/28

SRM 483 Sheep

| 03:36

http://www.topcoder.com/stat?c=problem_statement&pm=10920&rd=14236

問題

重さのある羊がたくさんいる.これを重量の容量がある船に乗せて川を渡らせる.乗せる羊の選び方は,残り容量以下で重い方から選んでいく.与えられた回数以下で全ての羊を渡らせるときに,船の最小の容量を求める.

アプローチ

ぱっと見,何の変哲もない二分探索の問題であるが落とし穴がある.

ある容量で回数内に運べるからといって,それより大きい容量で運べるとは限らないからである.chokudai 氏がテストケースを挙げている

900のチャレンジケース 14,3,"100 60 50 39 35 30 30 30 25 25 24 20 9"less than a minute ago via P3:PeraPeraPrv

すげえwwwどうやって見つけたんだwww出典

容量 159 で成立するけど 160 では成立しないケースのようである.

というわけで二分探索で求めた後,前を 2000 個ほど探索している.この 2000 という値には全く根拠がないのだが(しいて言えば羊の重さの上限),本当にこれでいいんだろうか・・・?

※追記:wata さんによれば,(羊の重さの合計)/(運べる最大回数)から(羊の重さの合計)/(運べる最大回数)+(羊の最大の重さ)までに必ず解があると証明できるとのこと.

昨日の900の証明って別に簡単だよね 全部の和/回数+最大重みがあれば、極大サイズが全部の和/回数以上になるので絶対可能 よって全部の和/回数から+2000調べればよいless than a minute ago via HootSuite

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

#define sz(a) int((a).size())
#define All(a)  (a).begin(),(a).end()

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)
#define Each(i,c)     for(typeof((c).begin()) i=(c).begin();i!=(c).end();++i)

bool judge(multiset<int> s, int c, int maxRuns)
{
	int runs = 0;
	multiset<int>::iterator it;
	while(sz(s))
	{
		int cc = c;
		while(cc>0&&sz(s))
		{
			it = s.upper_bound(cc);
			if(it==s.begin()) break;
			it--;
			cc -= *it;
			s.erase(it);
		}
		if(++runs>maxRuns)
			return false;
	}
	
	return true;
}

int minCapacity(int numSheep, int maxRuns, vector <string> part1, vector <string> part2, vector <string> part3, vector <string> part4)
{
	multiset<int> msi;
	string str;
	int n;
	Each(s,part1) str+=*s;
	Each(s,part2) str+=*s;
	Each(s,part3) str+=*s;
	Each(s,part4) str+=*s;
	istringstream iss(str); while(iss>>n) msi.insert(n);
	int sum = accumulate(All(msi),0);
	int max = *max_element(All(msi));
	
	for(int capasity=sum/maxRuns; capasity<=sum/maxRuns+max+1; capasity++)
		if(judge(msi,capasity,maxRuns)) return capasity;
	return -1;
/*
	// binary search version
	int min = *max_element(All(msi));
	int max = accumulate(All(msi),0);
	
	while(max-min>1)
	{
		int mid = (min+max)/2;
		if(bs(msi,mid,maxRuns))
			max = mid;
		else
			min = mid;
	}
	
	For(c,min-2000,max)
		if(bs(msi,c,maxRuns)) return c;
	
	return max;
*/
}

ttvijfyomttvijfyom2011/02/27 18:44XXnJye <a href="http://idnbvnetymog.com/">idnbvnetymog</a>, [url=http://ftuabcqbiduw.com/]ftuabcqbiduw[/url], [link=http://gwxepxsaficy.com/]gwxepxsaficy[/link], http://judtzquinqwh.com/