ABBYY-hard
このごろコンテスト続きでつかれるにゃー。
問題みる。とりあえずAみる。やるだけ。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; typedef long long ll; int main() { int num; scanf("%d",&num); vector<ll>vec; for(int i=0;i<num;i++) { ll zan; scanf("%I64d",&zan); vec.push_back(zan); } vector<ll>rui; ll now=1; for(int j=0;j<60;j++) { rui.push_back(now); now*=2; } ll ret=0; for(int k=0;k<num-1;k++) { int low=upper_bound(rui.begin(),rui.end(),num-k-1)-rui.begin()-1; ret+=vec[k]; vec[k+rui[low]]+=vec[k]; vec[k]=0; printf("%I64d\n",ret); } }
Bみる。むずそう。
どうせ二重辺連結成分分解+LCAなんだろうなと思う。そんなの実装できない。後回し。（想定解っぽかった）
Cみる。やばげなデータ構造使いそうなにおい。あとまわし。
Dみる。20点だけ通してる人がやたら多い。20点とかnext_permutationするだけ。
取り合えず100点はガチで枝狩りすれば行けそう。8マスの値を決めればあとは必然的に決まるが、これは16*15*...*9くらいの計算量がかかりそうなので、愚直に枝を刈る。
コードひどすぎ。15重ループとか初めて書いた。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int main() { int num; vector<int>vec; scanf("%d",&num); int sum=0; for(int i=0;i<num*num;i++) { int zan; scanf("%d",&zan); sum+=zan; vec.push_back(zan); } sum/=num; printf("%d\n",sum); random_shuffle(vec.begin(),vec.end()); if(num==1) { printf("%d\n",vec[0]); } if(num==2) { printf("%d %d\n%d %d\n",vec[0],vec[1],vec[2],vec[3]); } if(num==3) { for(;;) { if(vec[0]+vec[1]+vec[2]==sum&&vec[3]+vec[4]+vec[5]==sum&&vec[0]+vec[3]+vec[6]==sum&&vec[1]+vec[4]+vec[7]==sum&&vec[0]+vec[4]+vec[8]==sum&&vec[2]+vec[4]+vec[6]==sum) { printf("%d %d %d\n%d %d %d\n%d %d %d\n",vec[0],vec[1],vec[2],vec[3],vec[4],vec[5],vec[6],vec[7],vec[8]); break; } next_permutation(vec.begin(),vec.end()); } } if(num==4) { for(int j=0;j<16;j++) { for(int k=0;k<16;k++) { if(j==k) { continue; } for(int l=0;l<16;l++) { if(j==l||k==l) { continue; } for(int m=0;m<16;m++) { if(j==m||k==m||l==m) { continue; } if(vec[j]+vec[k]+vec[l]+vec[m]!=sum) { continue; } vector<int>vec2; for(int aa=0;aa<16;aa++) { if(aa==j||aa==k||aa==l||aa==m) { continue; } vec2.push_back(vec[aa]); } for(int n=0;n<12;n++) { for(int o=0;o<12;o++) { if(n==o) { continue; } for(int p=0;p<12;p++) { if(n==p||o==p) { continue; } for(int q=0;q<12;q++) { if(n==q||o==q||p==q) { continue; } if(vec2[n]+vec2[o]+vec2[p]+vec2[q]!=sum) { continue; } vector<int>vec3; for(int aa=0;aa<12;aa++) { if(aa==n||aa==o||aa==p||aa==q) { continue; } vec3.push_back(vec2[aa]); } for(int r=0;r<8;r++) { for(int s=0;s<8;s++) { if(r==s) { continue; } if(vec[j]+vec2[n]+vec3[r]+vec3[s]!=sum) { continue; } for(int t=0;t<8;t++) { if(r==t||s==t) { continue; } if(vec[m]+vec2[p]+vec3[t]+vec3[s]!=sum) { continue; } for(int u=0;u<8;u++) { if(r==u||s==u||t==u) { continue; } if(vec[k]+vec2[o]+vec3[t]+vec3[u]!=sum) { continue; } vector<int>vec4; for(int aa=0;aa<8;aa++) { if(aa==r||aa==s||aa==t||aa==u) { continue; } vec4.push_back(vec3[aa]); } for(int v=0;v<4;v++) { for(int x=0;x<4;x++) { if(v==x) { continue; } if(vec[l]+vec2[p]+vec4[v]+vec4[x]!=sum) { continue; } for(int y=0;y<4;y++) { if(v==y||x==y) { continue; } if(vec3[r]+vec3[t]+vec4[v]+vec4[y]!=sum) { continue; } int z=6-v-x-y; if(vec[j]+vec2[o]+vec4[v]+vec4[z]==sum) { printf("%d %d %d %d\n%d %d %d %d\n%d %d %d %d\n%d %d %d %d\n",vec[j],vec[k],vec[l],vec[m],vec2[n],vec2[o],vec2[p],vec2[q],vec3[r],vec3[t],vec4[v],vec4[y],vec3[s],vec3[u],vec4[x],vec4[z]); goto l01; } } } } } } } } } } } } } } } } } l01:; }
Eみる。変わった感じの問題。画像の入力をすると勘違いする。へぇ、標準入力から画像が読めるんだ〜（爆笑）
入力できないので捨てる。
Fみる。最大全域木かなとか思う。それじゃいけないことに気付く。UF書いた時間返せ。
DPかなとも思う。dp[使う区間][その区間で選ぶ数]でDPするのかなとか思ったが、何を選ぶかによって変わってきそう。実は辺をソートしておけばこれでできる、らしい。思いついてスルーしてしまっただけに痛い。
とりあえずもう解けそうな問題がないので、部分点回収に走る。
Fを2^nくらいで実装。20点。なぜvectorを2か所普通の配列に直しただけで時間が[TLE]->[170msくらい]になるの。サーバーおかしいだろ。
#include<stdio.h> #include<string> #include<iostream> #include<algorithm> #include<vector> using namespace std; int map[2000][2000]; int par[2000]; int ran[2000]; int ren[2000]; void init() { for(int i=0;i<2000;i++) { par[i]=i; ran[i]=0; ren[i]=1; } } int find(int a) { if(par[a]==a) { return a; } else { return par[a]=find(par[a]); } } void unite(int a,int b) { a=find(a); b=find(b); if(a==b) { return; } if(ran[a]>ran[b]) { par[b]=a; ren[a]+=ren[b]; } else { par[a]=b; ren[b]+=ren[a]; } if(ran[a]==ran[b]) { ran[b]++; } } int main() { int num,gen; scanf("%d%d",&num,&gen); vector<string>vec; for(int i=0;i<num;i++) { string str; cin>>str; vec.push_back(str); } for(int j=0;j<num;j++) { for(int k=0;k<num;k++) { if(j!=k) { int ret=0; for(int l=0;l<min(vec[j].size(),vec[k].size());l++) { if(vec[j][l]!=vec[k][l]) { break; } ret++; } map[j][k]=ret; } } } int ko=1; for(int l=0;l<num;l++) { ko*=2; } int maxi=0; for(int m=0;m<ko;m++) { int bit[20]; int mon=m; int kos=0; int zan[20]; for(int n=0;n<num;n++) { bit[n]=mon%2; if(mon%2==1) { zan[kos]=n; kos++; } mon/=2; } if(kos!=gen) { continue; } int sum=0; for(int o=0;o<gen;o++) { for(int p=0;p<gen;p++) { sum+=map[zan[o]][zan[p]]; } } maxi=max(maxi,sum); } printf("%d\n",maxi/2); }
UF書いてあるのは名残。20点獲得。
Cの部分点をとりに行く。愚直にシュミレーション。20点。
#include<stdio.h> #include<algorithm> using namespace std; int main() { int hash,plu,query; scanf("%d%d%d",&hash,&plu,&query); int map[5000]; fill(map,map+5000,0); int ret=0; for(int i=0;i<query;i++) { char zc; int ha; scanf(" %c%d",&zc,&ha); if(zc=='+') { int num; scanf("%d",&num); for(;;) { if(map[num]==0) { map[num]=ha; break; } ret++; num=(num+plu)%hash; } } else { for(int j=0;j<hash;j++) { if(map[j]==ha) { map[j]=0; break; } } } } printf("%d\n",ret); }
Bの部分点をとりに行く、、、って、部分点もわからなくなった。
すべての辺を1こずつつぶしていって、その都度連結判定すればいいのか→さっきFで書いたUFが活躍。
とりあえずこれでO(E^2Qalpha(E))で20点取れる。
クエリ先読みしちゃえばO(E^2alpha(E)+EQ)でいける。50点。
#include<stdio.h> #include<queue> #include<algorithm> #include<vector> using namespace std; int par[2000]; int ran[2000]; void init() { for(int i=0;i<2000;i++) { par[i]=i; ran[i]=0; } } int find(int a) { if(par[a]==a) { return a; } else { return par[a]=find(par[a]); } } void unite(int a,int b) { a=find(a); b=find(b); if(a==b) { return; } if(ran[a]>ran[b]) { par[b]=a; } else { par[a]=b; } if(ran[a]==ran[b]) { ran[b]++; } } int main() { int cit,way; scanf("%d%d",&cit,&way); vector<pair<int,int> >road; for(int j=0;j<way;j++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; road.push_back(make_pair(za,zb)); } int query; scanf("%d",&query); vector<pair<int,int> >que; vector<int>ans; for(int k=0;k<query;k++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; que.push_back(make_pair(za,zb)); ans.push_back(0); } for(int l=0;l<way;l++) { init(); for(int m=0;m<way;m++) { if(l!=m) { unite(road[m].first,road[m].second); } } for(int n=0;n<query;n++) { if(find(que[n].first)!=find(que[n].second)) { ans[n]++; } } } for(int o=0;o<query;o++) { printf("%d\n",ans[o]); } }
各辺をつぶす場合に対して、だいたい同じUFをしてるから、なんか頑張ればうまくいきそうとか思ったけど、よくわからなかった。永続UFとかかな。
結果290点（ひどすぎ）
なのにratingは微増。このレートだとよほどのことをしなければ下がらないみたいだ。
rating:1779->1793(+14)rank:155
