JOI本選
JOI本選に参加してきました。
2年連続の10年に一度の大雪が降る中オリセンへ。いろいろあって競技へ。(気力がないので競技のことだけ書きます)
- 競技開始
- 1番を見る。簡単。やるだけ。書く。通る(15分くらい)
- 2番を見る。簡単。やるだけ。書く。なんかバグるけど適当に直して通る(20分くらい)
- 3番を見る。簡単。やるだけ。書く。あまりバグらずに通る(15分くらい)
- 4番を見る。ぱっと見わからない。
- 5番を見る。闇。見なかったことにする。
- 4番に戻って考える。部分点はすぐにわかるが満点がわからない。
- どうせ状態数が圧縮できるからそのグラフを構築してdijkstraしてくださいという問題なので圧縮を考える。初期位置からの遷移が面倒。
- 木の上下の端を含む経路は必要ですね
- のぼっておりることはないのでのぼらずに降りられるところまで降りた結果の場所を持っておけばOKなはず。
- 実装。dijkstra苦手なのでつらい。と思ったがdijkstraは大したことはなくてグラフを構築するのが闇。
- とりあえず適当に出す。MLEっぽいものがたくさん帰ってくる。
- こわい
- でもとりあえずMLEっぽくないのでREの線を疑う。
- RE定番のsubmitデバッグを行う。
- for(int i=0;i
- 直して出す。MLEしている。
- 配列は大丈夫だしなんでだろうとか思っていたがdijkstraをするのでpriority_queueのサイズがやばいことに気付く。
- そんなものはどれくらいの大きさかなんてわかるわけがないのでとりあえずintでいいとことをintにする。
- MLEが取れる。今度はTLEとWAが生えている。闇。
- まずちょっと嘘解法してるところを見つけたのでWAを直す。WAがとれる。
- あとは定数倍改善だ(つらい)
- 適当にいろいろいじってたら通った。dijkstraは闇。
- のこりが10分くらいである。
- 爆速で5番の5点を取りに行くが間に合わない。書きあげてろくにコンパイルもせずに出したらコンパイルエラーである。
- コンテスト終了。ちなみにコンパイルエラーなくても通ってないしまあいいや
4番で時間を使いまくったが5番は人間に解ける問題ではないのでよい。400点なので金か銀だと思う。
終了後インタビューを受けたが日本語が難しい。質問に答えるというの難易度が高い。日本語は4番レベルには難しいと思う。
ゆきだるま作りには参加せずに解散。
以下コード
1
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; char map[1002][1002]; char a[4]; bool isok(int x,int y) { if(map[x][y]==a[0]&&map[x][y+1]==a[1]&&map[x+1][y]==a[2]&&map[x+1][y+1]==a[3]) { return true; } return false; } int main() { int mx,my; scanf("%d%d",&mx,&my); for(int i=0;i<mx+2;i++) { for(int j=0;j<my+2;j++) { map[i][j]='X'; } } for(int i=0;i<mx;i++) { for(int j=0;j<my;j++) { char zan; scanf(" %c#",&zan); map[i+1][j+1]=zan; } } scanf(" %c %c %c %c",&a[0],&a[1],&a[2],&a[3]); int ans=0; for(int i=0;i<mx+1;i++) { for(int j=0;j<my+1;j++) { if(isok(i,j)) { ans++; } } } int maxi=0; for(int i=1;i<mx+1;i++) { for(int j=1;j<my+1;j++) { int now=int(isok(i-1,j-1))+int(isok(i-1,j))+int(isok(i,j-1))+int(isok(i,j)); char t=map[i][j]; map[i][j]='J'; maxi=max(int(isok(i-1,j-1))+int(isok(i-1,j))+int(isok(i,j-1))+int(isok(i,j))-now,maxi); map[i][j]='O'; maxi=max(int(isok(i-1,j-1))+int(isok(i-1,j))+int(isok(i,j-1))+int(isok(i,j))-now,maxi); map[i][j]='I'; maxi=max(int(isok(i-1,j-1))+int(isok(i-1,j))+int(isok(i,j-1))+int(isok(i,j))-now,maxi); map[i][j]=t; } } printf("%d\n",maxi+ans); }
2
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; int dp[501][20001]; typedef pair<int,int>pii; int main() { int nm,nb; scanf("%d%d",&nm,&nb); vector<int>dat; for(int i=0;i<nm;i++) { int zan; scanf("%d",&zan); dat.push_back(zan); } sort(dat.begin(),dat.end()); reverse(dat.begin(),dat.end()); vector<pii>vec; for(int i=0;i<nb;i++) { int za,zb; scanf("%d%d",&za,&zb); vec.push_back(make_pair(za,zb)); } for(int i=0;i<=nb;i++) { for(int j=0;j<=20000;j++) { dp[i][j]=1000000000; } } dp[0][0]=0; for(int i=0;i<nb;i++) { for(int j=0;j<=20000;j++) { dp[i+1][j]=min(dp[i+1][j],dp[i][j]); if(j+vec[i].first<=20000) { dp[i+1][j+vec[i].first]=min(dp[i+1][j+vec[i].first],dp[i][j]+vec[i].second); } } } for(int i=19999;i>=0;i--) { dp[nb][i]=min(dp[nb][i],dp[nb][i+1]); } int maxi=0; int now=0; for(int i=0;i<nm;i++) { now+=dat[i]; maxi=max(maxi,now-dp[nb][i+1]); } printf("%d\n",maxi); }
3
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll rui[300001]; int main() { int num; scanf("%d",&num); vector<ll>vec; for(int i=0;i<num;i++) { int zan; scanf("%d",&zan); vec.push_back(zan); } for(int i=0;i<num;i++) { rui[i+1]=vec[i]+rui[i]; } for(int i=num;i<num+num;i++) { rui[i+1]=vec[i-num]+rui[i]; } for(int i=num+num;i<num+num+num;i++) { rui[i+1]=vec[i-num-num]+rui[i]; } ll maxi=0; for(int i=0;i<num;i++) { ll beg=0,end=1000000000000000000LL; for(;;) { ll med=(beg+end)/2+1; int low1=lower_bound(rui+i,rui+num+num+i,rui[i]+med)-rui; int low2=lower_bound(rui+low1,rui+num+num+i,rui[low1]+med)-rui; //int low3=lower_bound(rui+low2,rui+num+num+i,rui[low2]+med)-rui; //printf("%lld %lld %lld %d %d\n",beg,end,med,low1,low2); if(rui[i+num]-rui[low2]>=med) { beg=med; } else { end=med-1; } if(beg==end) { maxi=max(maxi,beg); break; } } } printf("%lld\n",maxi); }
4
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> #include<math.h> #include<stdlib.h> using namespace std; #define INF 1000000000000000000LL typedef long long ll; typedef pair<ll,ll>pii; ll hig[100000]; vector<pii>zpat[100000]; bool zflag[100000]; ll zdist[100000]; vector<pair<int,int> >pat[4800002]; bool flag[4800002]; ll dist[4800002]; ll cur[100000]; vector<pii>kou[100000]; int main() { int cit,way,beg; scanf("%d%d%d",&cit,&way,&beg); for(int i=0;i<cit;i++) { scanf("%lld",&hig[i]); } for(int i=0;i<way;i++) { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); za--; zb--; zpat[za].push_back(make_pair(zb,zc)); zpat[zb].push_back(make_pair(za,zc)); } priority_queue<pii>zque; fill(zflag,zflag+cit,false); fill(zdist,zdist+cit,INF); zdist[0]=0; zque.push(make_pair(0,0)); for(;;) { if(zque.empty()) { break; } pii zan=zque.top(); zque.pop(); if(zflag[zan.second]) { continue; } zflag[zan.second]=true; for(int i=0;i<zpat[zan.second].size();i++) { if(zdist[zpat[zan.second][i].first]>zdist[zan.second]+zpat[zan.second][i].second&&hig[zpat[zan.second][i].first]>=beg-zdist[zan.second]-zpat[zan.second][i].second&&beg-zdist[zan.second]-zpat[zan.second][i].second>=0) { zdist[zpat[zan.second][i].first]=zdist[zan.second]+zpat[zan.second][i].second; zque.push(make_pair(-zdist[zpat[zan.second][i].first],zpat[zan.second][i].first)); } else { if(zdist[zpat[zan.second][i].first]>beg-hig[zpat[zan.second][i].first]&&hig[zpat[zan.second][i].first]<beg-zdist[zan.second]-zpat[zan.second][i].second) { zdist[zpat[zan.second][i].first]=beg-hig[zpat[zan.second][i].first]; zque.push(make_pair(-zdist[zpat[zan.second][i].first],zpat[zan.second][i].first)); } } } } fill(cur,cur+100000,-1); for(int i=0;i<cit;i++) { if(zdist[i]<INF) { cur[i]=beg-zdist[i]; } } int pt=2; kou[0].push_back(make_pair(beg,0)); kou[cit-1].push_back(make_pair(hig[cit-1],1)); priority_queue<pair<ll,int> >que; for(int i=0;i<cit;i++) { for(int j=0;j<zpat[i].size();j++) { ll a=i,b=zpat[i][j].first,c=zpat[i][j].second; if(c<=hig[a]) { pat[pt+0].push_back(make_pair(pt+1,c)); kou[a].push_back(make_pair(c,pt+0)); kou[b].push_back(make_pair(0,pt+1)); } if(hig[b]+c<=hig[a]) { pat[pt+2].push_back(make_pair(pt+3,c)); kou[a].push_back(make_pair(hig[b]+c,pt+2)); kou[b].push_back(make_pair(hig[b],pt+3)); } if(cur[a]>=0) { pat[pt+4].push_back(make_pair(pt+5,c)); kou[a].push_back(make_pair(cur[a],pt+4)); //que.push(make_pair(-cur[a],pt+4)); kou[b].push_back(make_pair(cur[a]-c,pt+5)); } pt+=6; } } for(int i=0;i<cit;i++) { if(kou[i].size()<=1) { continue; } sort(kou[i].begin(),kou[i].end()); for(int j=0;j<int(kou[i].size())-1;j++) { pat[kou[i][j].second].push_back(make_pair(kou[i][j+1].second,kou[i][j+1].first-kou[i][j].first)); pat[kou[i][j+1].second].push_back(make_pair(kou[i][j].second,kou[i][j+1].first-kou[i][j].first)); } } fill(flag,flag+3600002,false); fill(dist,dist+3600002,INF); que.push(make_pair(0,0)); dist[0]=0; for(;;) { if(que.empty()) { printf("-1\n"); break; } pii zan=que.top(); que.pop(); if(flag[zan.second]) { continue; } flag[zan.second]=true; if(zan.second==1) { printf("%lld\n",dist[zan.second]); break; } for(int i=0;i<pat[zan.second].size();i++) { if(dist[pat[zan.second][i].first]>dist[zan.second]+pat[zan.second][i].second) { dist[pat[zan.second][i].first]=dist[zan.second]+pat[zan.second][i].second; que.push(make_pair(-dist[pat[zan.second][i].first],pat[zan.second][i].first)); } } } }
