2014-02-07

■ SRM 608 03:22

懲りずにMed開けしました。

Medium:

O()...??????

無理。

Easy:

ある部分集合Sにふくまれるキャンデーの数の下界は

Sの補集合をTとすると

max(sum(low[ S[i] ]),C-sum(High[ T[i] ]))なので

順番に足していくだけ。

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
class MysticAndCandies
{
	public:
	int minBoxes(int C, int X, vector <int> low, vector <int> high)
	{
		sort(high.begin(),high.end());
		int ret=INF;
		for(int i=0;i<=high.size();i++)
		{
			int sum=0;
			for(int j=0;jif(C-sum>=X) ret=min(ret,(int)high.size()-i);
		}
		sort(low.begin(),low.end(),greater<int>());
		for(int i=0;i<=low.size();i++)
		{
			int sum=0;
			for(int j=0;jif(sum>=X) ret=min(ret,i);
		}	
		return ret;
	}
};

Hard:

尺取りっぽくやるのかなあとか思ったけど自明に無理

Challenge: C=Xの時の処理をミスしてる人を撃墜。調子に乗ってもう一人やったら-1でデデドン(絶望)

Systest: 通る。68位。大勝利

Rating: 1912->1998(+86)

チャレンジミスしなければ2000行ったんじゃないのか...?まあ次回頑張ります。

ツイートする