読者です 読者をやめる 読者になる 読者になる

GCJ2014 Round1A

満点で45位でした。

A:
実は全探索で枝刈りもすれば2^40も見なくてすむことが分かる(らしい)。探索むずすぎィ!
何でこんなの7分くらいで解けるんですか…

#include<stdio.h>
#include<algorithm>
using namespace std;
char c[200][100];
char d[200][100];
long long e[200];
long long f[200];
int val[200];
int ans[200];
long long s[200];
long long t[200];
int ret=99999999;
int n,m;
void solve(int a,long long now){
	if(a==m){
		ret=min(ret,__builtin_popcountll(now));
		return;
	}
	for(int i=0;i<n;i++)s[i]=(e[i]^now)%(1LL<<(a+1));
	for(int i=0;i<n;i++)t[i]=f[i]%(1LL<<(a+1));
	std::sort(s,s+n);std::sort(t,t+n);
	bool ok=true;
	for(int i=0;i<n;i++)if(s[i]!=t[i])ok=false;
	if(ok)solve(a+1,now);
	
	for(int i=0;i<n;i++)s[i]=(e[i]^(now+(1LL<<a)))%(1LL<<(a+1));
	for(int i=0;i<n;i++)t[i]=f[i]%(1LL<<(a+1));
	std::sort(s,s+n);std::sort(t,t+n);
	ok=true;
	for(int i=0;i<n;i++)if(s[i]!=t[i])ok=false;
	if(ok)solve(a+1,now+(1LL<<a));
}
int main(){
	int T;
	scanf("%d",&T);
	for(int t=0;t<T;t++){
		int a,b;
		
		scanf("%d%d",&a,&b);
		n=a;m=b;
		for(int i=0;i<a;i++)scanf("%s",c[i]);
		for(int i=0;i<a;i++)scanf("%s",d[i]);
		for(int i=0;i<a;i++){
			e[i]=f[i]=0LL;
			for(int j=0;j<b;j++){
				e[i]*=2;
				if(c[i][j]=='1')e[i]++;
				f[i]*=2;
				if(d[i][j]=='1')f[i]++;
			}
		}
		std::sort(e,e+a);
		std::sort(f,f+a);
		ret=99999999;
		solve(0,0);

		printf("Case #%d: ",t+1);
		if(ret==99999999)printf("NOT POSSIBLE\n");
		else printf("%d\n",ret);
	}
}

B:
典型木DP。やるだけ。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> g[2000];
int sz[2000];
int solve(int a,int b){
	int ch=0;
	int v1=0;
	int v2=0;
	sz[a]=1;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		ch++;
		int q=solve(g[a][i],a);
		sz[a]+=sz[g[a][i]];
		if(v1<q){
			v2=v1;
			v1=q;
		}else if(v2<q){
			v2=q;
		}
	}
	if(ch==0)return 1;
	if(ch==1)return 1;
	else return v1+v2+1;
}
int main(){
	int T;
	scanf("%d",&T);
	for(int t=0;t<T;t++){
		int a;
		scanf("%d",&a);
		for(int i=0;i<a;i++)g[i].clear();
		for(int i=0;i<a-1;i++){
			int b,c;
			scanf("%d%d",&b,&c);
			b--;c--;
			g[b].push_back(c);
			g[c].push_back(b);
		}
		int ret=999999999;
		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++)sz[j]=0;
			int dat=solve(i,-1);
		//	printf("%d: %d\n",i,a-dat);
			ret=min(ret,a-dat);
		}
		printf("Case #%d: %d\n",t+1,ret);
	}
}

C:
(これは別解らしい)
まず、長さ30の順列でbad algorithmを使うとどういう分布にあるのか調べてみた。

#include<stdio.h>
#include<algorithm>
using namespace std;
int time[30][30];
int perm[30];
int main(){
	int t=1000000000;
	while(t--){
		for(int i=0;i<30;i++){
			perm[i]=i;
		}
		for(int i=0;i<30;i++){
			int p=rand()%30;
			swap(perm[p],perm[i]);
		}
		for(int i=0;i<30;i++)time[i][perm[i]]++;
	}
	for(int i=0;i<30;i++){
		for(int j=0;j<30;j++)printf("%9d ",time[i][j]);
		printf("\n");
	}
}

出てきた値で評価点決めてある程度評価点が高かったらBADじゃね?

#include<stdio.h>
#include<algorithm>
using namespace std;
int data[30][30]=
{{33334612,44693419,43633610,42586441,41570504,40601075,39657083,38756004,
37890660,37047771,36218100,35435674,34665264,33914813,33210992,32520321,
31838936,31200998,30566759,29975424,29395560,28838060,28279184,27753433,
27257311,26761717,26281587,25813095,25364480,24937113},{
33337285,32651572,44050610,43011073,42013588,41028989,40086869,39196911,
38310237,37469085,36639048,35857048,35096805,34365292,33633298,32944809,
32283337,31637958,31011254,30406710,29818783,29246142,28715116,28194205,
27677448,27187480,26712039,26236162,25807795,25373052},{
33331934,32659622,32016511,43458881,42457472,41473656,40545211,39635288,
38758285,37912354,37100630,36301712,35537736,34802589,34091667,33392287,
32719253,32078025,31451632,30848237,30260897,29709422,29158355,28624344,
28126038,27630793,27150253,26697930,26250142,25818844},{
33327772,32677891,32052434,31434179,42923440,41940746,41015192,40101231,
39224818,38375338,37553043,36762665,36000141,35251790,34542502,33855051,
33194712,32529964,31907141,31301440,30724873,30165190,29618318,29096764,
28580790,28088856,27607474,27161803,26709642,26274800},{
33337799,32694432,32080325,31487740,30915795,42429364,41476973,40573636,
39699457,38844091,38032911,37236545,36464328,35733235,35023033,34338601,
33668212,33009368,32387884,31786986,31190298,30643878,30096611,29573312,
29060504,28562817,28085267,27628884,27183141,26754573},{
33332124,32711339,32116885,31530216,30981306,30446299,41958389,41069508,
40201150,39342540,38520689,37732219,36966759,36222746,35506076,34821665,
34155221,33503195,32880968,32271655,31708311,31135807,30585760,30057909,
29547898,29069062,28584557,28112914,27678370,27248463},{
33335073,32731912,32146688,31583121,31040419,30514010,30005975,41577575,
40701178,39868378,39035993,38235780,37477156,36726898,36021034,35330780,
34659841,34020115,33393526,32788364,32209538,31643163,31090843,30569703,
30049660,29573389,29091602,28631370,28186642,27760274},{
33336575,32756136,32180192,31644082,31105236,30595786,30106617,29627355,
41228146,40387217,39553650,38772487,38003222,37259684,36548723,35860767,
35187161,34533891,33921967,33315701,32737082,32168562,31616451,31092689,
30588423,30090416,29624708,29160157,28721177,28275740},{
33325652,32765753,32227148,31699999,31180908,30691921,30220080,29743272,
29299600,40924692,40101551,39320697,38549503,37803173,37097150,36397366,
35738185,35091683,34457961,33851323,33280139,32704897,32166943,31637008,
31128478,30640362,30166667,29706574,29256911,28824404},{
33343891,32788733,32254384,31753984,31248981,30771577,30308765,29852310,
29431080,29011258,40675218,39885390,39118216,38378707,37652948,36969594,
36302886,35649158,35032589,34428879,33831705,33272458,32732027,32202699,
31692352,31200609,30728746,30265690,29821374,29393792},{
33332232,32817266,32296720,31805505,31318058,30862902,30415214,29997403,
29568087,29173441,28782124,40447638,39690956,38961681,38243118,37548299,
36885151,36218665,35612579,35022234,34430890,33856370,33319486,32781768,
32282812,31791137,31311198,30853857,30397826,29975383},{
33330003,32818241,32329639,31863510,31411185,30958303,30532189,30113616,
29710512,29325157,28959580,28597338,40310825,39557693,38849022,38145904,
37483622,36841058,36214809,35607484,35021910,34461615,33928034,33388390,
32885303,32388894,31916249,31462500,31009822,30577593},{
33332339,32856155,32376073,31923179,31485719,31054332,30645044,30252961,
29868406,29486559,29133637,28782355,28459570,40185291,39470234,38783484,
38107384,37463028,36842759,36231260,35657392,35092541,34538641,34015065,
33501961,33005051,32541407,32074667,31635668,31197838},{
33329226,32870007,32420457,31983729,31562841,31158176,30769018,30393715,
30020964,29659735,29318098,28988747,28667607,28358457,40113880,39431790,
38757470,38116186,37479551,36897826,36293727,35741736,35177578,34664632,
34153797,33653878,33177434,32718856,32270716,31850166},{
33333274,32893461,32463732,32042900,31644675,31262779,30894404,30523949,
30171885,29847632,29518990,29195444,28886056,28599552,28323661,40082593,
39429014,38786084,38165019,37541833,36966147,36395693,35859845,35337467,
34815176,34311525,33860582,33394175,32937551,32514902},{
33338876,32910152,32506165,32109532,31739987,31365093,31016175,30672762,
30350646,30020562,29707866,29411325,29125063,28844423,28573907,28314113,
40119570,39473981,38853808,38243892,37647485,37091385,36555755,36018118,
35502039,35008661,34536089,34083820,33654663,33204087},{
33331958,32936501,32550195,32178249,31828647,31479272,31151912,30828157,
30520247,30198846,29912294,29637200,29355922,29097645,28834436,28598030,
28361485,40191521,39556592,38956372,38372896,37818850,37275220,36732881,
36226502,35732465,35256938,34798962,34350350,33929455},{
33327581,32959241,32606395,32246387,31912271,31594925,31280134,30984219,
30684503,30402471,30132477,29867745,29607204,29368632,29128024,28895563,
28670373,28452929,40302086,39697513,39110548,38540617,38001678,37476244,
36975358,36475236,36008095,35537219,35092824,34661508},{
33329076,33000099,32650929,32317450,32015642,31718087,31421968,31136493,
30865742,30606091,30349314,30097799,29863250,29638442,29420505,29199744,
28985873,28784586,28602810,40456318,39875991,39318828,38769214,38242718,
37731265,37237150,36770166,36300761,35870905,35422784},{
33329801,33015801,32703124,32414706,32111986,31841160,31576487,31300578,
31055300,30814216,30582090,30358631,30131872,29920526,29701196,29501522,
29329971,29141704,28951830,28778560,40673766,40098548,39555341,39023234,
38526713,38032787,37560245,37097742,36644506,36226057},{
33335912,33032484,32768050,32489017,32224884,31967816,31723397,31480836,
31247428,31018462,30815647,30606652,30398681,30211833,30023932,29831895,
29665114,29494692,29336593,29168771,29031825,40926135,40358523,39855513,
39339000,38855419,38367772,37911521,37467394,37044802},{
33337358,33064394,32812714,32576024,32332807,32097815,31875813,31663412,
31442345,31253388,31051414,30869068,30676931,30515557,30335452,30184428,
30016131,29860288,29724895,29583157,29432304,29298736,41229081,40714801,
40185462,39698787,39217053,38754273,38303472,37892640},{
33328388,33098772,32873498,32652850,32434028,32238016,32043521,31851953,
31650469,31487683,31307745,31139138,30986783,30824793,30676076,30520980,
30381208,30249204,30101463,29993446,29864966,29743324,29634751,41567749,
41073554,40571172,40092112,39641633,39202805,38767920},{
33337751,33123352,32923390,32736096,32561701,32392566,32201351,32035702,
31875316,31729970,31580512,31423451,31285098,31144742,31015965,30885859,
30750205,30650623,30525207,30417149,30315092,30206742,30105522,30008054,
41987343,41475342,40988305,40542702,40096013,39678879},{
33345367,33158587,32995716,32833744,32671417,32522301,32375351,32236442,
32099829,31962434,31824366,31721794,31604755,31477526,31372767,31258393,
31155051,31056576,30955825,30860637,30773969,30686878,30607996,30515408,
30446182,42423213,41946864,41479743,41033309,40597560},{
33333960,33189131,33061407,32917395,32803418,32678370,32553005,32433388,
32338872,32214206,32120414,32014463,31918783,31840629,31745898,31643090,
31557981,31481598,31401607,31322882,31248386,31179902,31111350,31047740,
30970142,30925016,42898982,42451942,42014282,41581761},{
33328226,33231599,33122051,33018690,32921578,32828087,32745963,32651279,
32566338,32488593,32412592,32323248,32264248,32180514,32115072,32059704,
31977170,31929478,31861450,31807627,31740329,31695124,31638736,31586785,
31532379,31488228,31446989,43453980,43007388,42576555},{
33340221,33264371,33184248,33122309,33045173,32997124,32934661,32880341,
32815186,32759472,32705024,32654855,32602185,32551937,32501185,32462247,
32420041,32377433,32329248,32302623,32258154,32217844,32185198,32145443,
32113734,32088440,32054948,32019537,44048719,43618099},{
33332757,33292357,33268358,33240908,33198690,33154593,33132523,33096823,
33070963,33031327,33016356,32995658,32958607,32933948,32903348,32888689,
32868526,32840756,32827574,32799961,32790896,32771074,32755693,32737407,
32712155,32696071,32677810,32670199,32645785,44690188},{
33322977,33337220,33328352,33338104,33337644,33334860,33330716,33332881,
33332351,33337031,33338627,33327234,33326474,33327252,33324899,33332432,
33330916,33335255,33342614,33335736,33336141,33330479,33332750,33338517,
33330221,33336027,33337862,33337332,33336328,33330768}};
int b[1000];
int main(){
	int T;
	scanf("%d",&T);
	for(int t=0;t<T;t++){
		int a;scanf("%d",&a);
		for(int i=0;i<a;i++){
			scanf("%d",b+i);
		}
		long long val=0;
		for(int i=0;i<a;i++)val+=data[(int)((double)i/1000*30)][(int)((double)b[i]/1000*30)];
		printf("Case #%d: ",t+1);
		//printf("%lld ",val);
		if(val>33600000000LL)printf("BAD\n");
		else printf("GOOD\n");
	}
}

よーし投げるか。





Correct!


やったぜ。