今日解いた問題たち⑩

ICPCからの現実逃避のためにCodeforcesのcombinatoricsをまたやってみました。前回からしばらく空いていたので、そのあいだに埋めていないsolvedの多い問題も増えていました。

353B: Two Heaps
Greedyつらい。

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[200];
int c[200];
int d[100];
int e[100];
pair<int,int> dat[100];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<2*a;i++){
		scanf("%d",b+i);
	}
	int now=0;
	for(int i=10;i<=99;i++){
		int v=0;
		for(int j=0;j<2*a;j++){
			if(i==b[j]){
				v++;
			}
		}
		dat[i-10]=make_pair(v,i);
	}
	std::sort(dat,dat+90);
	for(int i=0;i<90;i++){
		int T=dat[i].second;
		for(int j=0;j<2*a;j++){
			if(T==b[j]){
				c[j]=(++now)%2;
				if(now%2==0)d[T]=1;
				else e[T]=1;
			}
		}
	}
	int A=0;
	int B=0;
	for(int i=0;i<100;i++){
		if(d[i])A++;
		if(e[i])B++;
	}
	printf("%d\n",A*B);
	for(int i=0;i<2*a;i++){
		if(i)printf(" ");
		printf("%d",c[i]+1);
	}
	printf("\n");
}

340B: Maximal Area Quadrilateral
これはcombinatoricsじゃないけど。三角形の符号付面積。最高に頭が悪く、無駄にlogをつけてしまい時間が危ない。

#include<stdio.h>
#include<algorithm>
using namespace std;
double x[500];
double y[500];
double s[500];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%lf%lf",x+i,y+i);
	}
	double ret=0;
	for(int i=0;i<a;i++){
		for(int j=i+1;j<a;j++){
			int N=0;
			for(int k=0;k<a;k++){
				if(k==i)continue;
				if(k==j)continue;
				s[N++]=(x[k]-x[i])*(y[j]-y[i])-(x[j]-x[i])*(y[k]-y[i]);
			}
			std::sort(s,s+a-2);
			ret=max(ret,s[a-3]-s[0]);
		}
	}
	printf("%.12f\n",ret/2);
}

151D
同じ問題を2回も解いちゃったじゃないか！！

145C: Lucky Subsequence
Lucky Numberは少ないので、それだけについてDPしてからほかのと合わせる。こういうのはluckynumber系そのものになれる必要がある気がする…

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[100010];
int mod=1000000007;
long long dp[2501][2501];
int S[2500];
long long inv[300000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
	}
	inv[1]=1;
	for(int i=2;i<300000;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	std::sort(c,c+a);
	int ind=0;
	int d=0;
	for(int i=0;i<a;i++){
		bool ok=true;
		int p=c[i];
		while(p){
			if(p%10!=4&&p%10!=7)ok=false;
			p/=10;
		}
		if(ok){
			if(i==0||c[i]!=c[i-1]){
				ind++;
				S[ind-1]++;
			}else{
				S[ind-1]++;
			}
		}else d++;
	}
	dp[0][0]=1;
	for(int i=0;i<ind;i++){
		for(int j=0;j<ind;j++){
			dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
			dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*S[i])%mod;
		}
	}
	long long ret=0;
	long long now=1;
	for(int i=0;i<=b;i++){
		ret=(ret+now*dp[ind][b-i]%mod)%mod;
		if(d==i)break;
		now=now*(d-i)%mod*inv[i+1]%mod;
//		printf("%lld ",now);
	}
	printf("%lld\n",ret);
}

lldを適宜I64dに直してください。コメント内のも直してください。