2013-08-18 - HIR180's diary

■ CF196(Div1)とかCodechefとかSRM584D1Mとか 04:03

CF:

A:死(絶望)

B~E:死

結果:死

Rating 1794->1726(-68)

Div2へ一直線...

Codechef:

自明問を2WAしたあと1問も解けず終了。

これはひどい。

SRM584D1M:

掘り出せる深さを50通り下から試していくと

前回までに数えられなかった組み合わせは

前回も掘り出せた建物だけでは条件を満たすことができないもの*その他

なので前回のDP結果をもって適当にほげ。

明らかに公式の解法の方が楽。

//E? Nandatte?
//世界一TopCoderができない
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
long long C[55][55]={};
class Excavations{
public:
long long count(vector <int> kind, vector <int> depth, vector <int> found, int K)
{
	for(int i=0;i<=50;i++){
		for(int j=0;j<=i;j++){
			if(!j || j==i){ C[i][j]=1LL;}
			else{C[i][j]=C[i-1][j]+C[i-1][j-1];}
		}
	}
	bool find[51]={};
	for(int i=0;itrue;

	vector<int>exc;
	for(int i=0;iint num[55];
	fill(num,num+55,INF);
	for(int j=0;jint val=0;
	for(int i=1;i<=50;i++)
	{
		if(num[i]!=INF && find[i]) val=max(val,num[i]);
	}
	int s=lower_bound(exc.begin(),exc.end(),val)-exc.begin();
	
	long long ret=0LL;
	
	
	long long dpprev[51]={};
	
	for(int i=s;iint findok[51]={};
		int other=0;
		int checker[51]={};
		int exp=0;
		for(int j=0;jif(find[kind[j]] && depth[j]<=exc[i])
			{
				findok[kind[j]]++;
				checker[kind[j]]++;
				if(i==s || (i!=s && depth[j]>exc[i-1]))
				{
					exp++;
				}
			}
			else if(find[kind[j]] && depth[j]>exc[i])
			{
				other++;
			}
			else if(!find[kind[j]] && depth[j]>exc[i])
			{
				other++;
			}
		}
		long long dp[51][51]={};
		dp[0][0]=1LL;
		int prev=0;
		for(int j=1;j<=50;j++)
		{
			if(!find[j])
			{
				 continue;
			}
			
			for(int k=1;k<=findok[j];k++)
			{
				for(int l=k;l<=K;l++)
				{
					dp[l][j]+=dp[l-k][prev]*C[findok[j]][k];
					//cout <
				}
			}
			prev=j;
			
		}
		
		for(int f=1;f<=K;f++)
		{
			long long s=dp[f][prev];
			for(int g=0;g<=min(exp,f);g++)
			{
				s-=dpprev[f-g]*C[exp][g];
			}
			s*=C[other][K-f];
			cout << i << "f " << other << " " << f << " " << s << endl;
			ret+=s;
		}
		
		for(int f=1;f<=50;f++)
		{
			dpprev[f]=dp[f][prev];
			cout << dpprev[f] << "ss " << f << endl;
		}
		//fail:;
	}
	return ret;
	}
};