満点で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!
やったぜ。
