まとめ
とりあえず、ジャッジで正解を確認したものが増えました。なので適当にソースと解法の概要を上げておきます。
2011 Bookshelf
いろいろ考えると重みつき最長増加部分列になります。適当にSegtreeに入れて処理。
#include<stdio.h> #include<algorithm> using namespace std; int b[100000]; int c[100000]; long long dp[100000]; long long segtree[262144]; void set(int a,long long b){ a+=131072; while(a){ segtree[a]=max(segtree[a],b); a/=2; } } long long query(int a,int b,int c,int d,int e){ if(b<c||d<a)return 0; if(c<=a&&b<=d)return segtree[e]; return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1)); } pair<int,int> dat[100000]; int m[100000]; int main(){ int a; scanf("%d",&a); long long sum=0; for(int i=0;i<a;i++){ scanf("%d",b+i); sum+=b[i]; } for(int i=0;i<a;i++){ scanf("%d",c+i); } for(int i=0;i<a;i++)dat[i]=make_pair(c[i],i); std::sort(dat,dat+a); for(int i=0;i<a;i++){ long long val=query(0,131071,0,dat[i].second,1); dp[dat[i].second]=val+b[i]; set(dat[i].second,dp[dat[i].second]); } printf("%lld\n",(sum-query(0,131071,0,131071,1))*2); }
2008 Fraction
適当にpriority_queueで処理。
#include<stdio.h> #include<algorithm> #include<queue> using namespace std; bool so(int a,int b){ while(a){ b%=a; int c=b; b=a; a=c; } if(b-1)return false; else return true; } int main(){ int a,b; scanf("%d%d",&a,&b); priority_queue<pair<double, pair<int,int> > >Q; for(int i=2;i<=a;i++)Q.push(make_pair(-(double)1/(double)i,make_pair(1,i))); for(int i=0;i<b-1;i++){ if(Q.size()==0){ printf("-1\n"); return 0; } int bunshi=Q.top().second.first; int bunbo=Q.top().second.second; Q.pop(); bunshi++; while(!so(bunshi,bunbo))bunshi++; if(bunshi<bunbo)Q.push(make_pair(-(double)bunshi/(double)bunbo,make_pair(bunshi,bunbo))); } if(Q.size()) printf("%d %d\n",Q.top().second.first,Q.top().second.second); else printf("-1\n"); }
2009 Abduction
縦と横に分けて考えて後はかけるだけ。オーバーフローとかそういう難しさ。
#include<stdio.h> char str[10010]; int dpX[1010]; int dpY[1010]; int MOD=10000000; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); a++; b++; scanf("%s",str); int dir=0; if(str[0]=='L'){ dir=1; for(int i=1;i<a;i++){ dpX[i]=1; } dpY[0]=1; }else{ for(int i=1;i<b;i++)dpY[i]=1; dpX[0]=1; } for(int i=0;i<c;i++){ if(str[i]=='L')dir+=3; else dir++; if(dir%4==0){ int now=0; for(int j=0;j<b;j++){ int m=dpY[j]; dpY[j]=now; now=(now+m)%MOD; } } if(dir%4==1){ int now=0; for(int j=0;j<a;j++){ int m=dpX[j]; dpX[j]=now; now=(now+m)%MOD; } } if(dir%4==2){ int now=0; for(int j=b-1;j>=0;j--){ int m=dpY[j]; dpY[j]=now; now=(now+m)%MOD; } } if(dir%4==3){ int now=0; for(int j=a-1;j>=0;j--){ int m=dpX[j]; dpX[j]=now; now=(now+m)%MOD; } } } printf("%lld\n",(long long)dpX[a-1]*dpY[b-1]%MOD); }
2008 Typhoon
座標圧縮してイベントもソートしてそれからSegTree。こういうのはどうでもいいところを間違えやすい。(今回はSegTreeのサイズを誤った)
#include<stdio.h> #include<algorithm> using namespace std; int SEGTREE[1048576]; pair<pair<int,int>,pair<int,int> > q[200000]; pair<int,int> taihuu[100000]; pair<int,pair<int,int> >Qval[100000]; pair<int,int> pressed[100000]; int ans[100000]; int zahyou[300000]; int V[300000]; int pd[200000]; void query(int begin,int end,int a,int b,int index){ if(begin<=a&&end>=b){ SEGTREE[index]++; //printf("%d %d\n",index,SEGTREE[index]); } else if(begin>b||end<a); else { query(begin,end,a,(a+b)/2,index*2); query(begin,end,(a+b)/2+1,b,index*2+1); } return ; } int search(int at){ int ret=0; at+=524288; while(at){ ret+=SEGTREE[at]; at/=2; } //printf("%d\n",ret); return ret; } int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++){ scanf("%d%d",&taihuu[i].first,&taihuu[i].second); V[i*2]=taihuu[i].first; V[i*2+1]=taihuu[i].second; } for(int i=0;i<b;i++){ int d,e,f; scanf("%d%d%d",&d,&e,&f); V[a*2+i]=d; Qval[i]=make_pair(d,make_pair(e-1,f)); } std::sort(V,V+a*2+b); int wolf=0; zahyou[wolf++]=V[0]; for(int i=1;i<a*2+b;i++){ if(V[i]!=V[i-1])zahyou[wolf++]=V[i]; } std::sort(zahyou,zahyou+wolf); //for(int i=0;i<a*2+b;i++)printf("%d ",zahyou[i]); //printf("\n"); for(int i=0;i<a;i++){ pressed[i]=make_pair(lower_bound(zahyou,zahyou+wolf,taihuu[i].first)-zahyou,lower_bound(zahyou,zahyou+wolf,taihuu[i].second)-zahyou); } for(int i=0;i<b;i++){ pd[i]=lower_bound(zahyou,zahyou+wolf,Qval[i].first)-zahyou; } for(int i=0;i<b;i++){ q[i*2]=make_pair(make_pair(Qval[i].second.first,1),make_pair(pd[i],i)); q[i*2+1]=make_pair(make_pair(Qval[i].second.second,2),make_pair(pd[i],i)); } std::sort(q,q+b*2); int now=0; for(int i=0;i<b*2;i++){ int go=q[i].first.first; while(now<go){ //printf("%d %d\n",pressed[now].first,pressed[now].second); query(pressed[now].first,pressed[now].second,0,524287,1); now++; //for(int j=0;j<10;j++)printf("%d ",search(j)); } if(q[i].first.second==1){ ans[q[i].second.second]-=search(q[i].second.first); }else{ ans[q[i].second.second]+=search(q[i].second.first); } } //for(int i=0;i<32;i++)printf("%d ",search(i)); for(int i=0;i<b;i++)printf("%d\n",ans[i]); }
2008 Committee
それっぽい木DPで通る。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int> t[100000]; int v[100000]; bool visited[100000]; int dp[100000]; int solve(int a){ if(visited[a])return dp[a]; int ret=v[a]; for(int i=0;i<t[a].size();i++)if(solve(t[a][i])>0)ret+=solve(t[a][i]); visited[a]=true; return dp[a]=ret; } int main(){ int a; for(int i=0;i<100000;i++){ visited[i]=false; v[i]=0; dp[i]=0; } scanf("%d",&a); int s=0; int m=-99999999; for(int i=0;i<a;i++){ int b,c; scanf("%d%d",&b,&c); if(b!=0)t[b-1].push_back(i); else s=i; v[i]=c; m=max(m,c); } int ret=m; for(int i=0;i<a;i++)ret=max(ret,solve(i)); printf("%d\n",ret); }
2009 Pyramid
よくみんな変な4方向からDPと言うけど、BFSするだけでも解ける。イベントを持っておく。
#include<stdio.h> #include<queue> #include<algorithm> using namespace std; pair<int,pair<int,int> > dat[10000]; int bfs[3000][3000]; int dx[]={1,0,0,-1,1,1,-1,-1}; int dy[]={0,1,-1,0,1,-1,1,-1}; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++) for(int j=0;j<b;j++) bfs[i][j]=-1; for(int i=0;i<c;i++){ int d,e,f; scanf("%d%d%d",&d,&e,&f); dat[i]=make_pair(-f,make_pair(d,e)); } std::sort(dat,dat+c); queue<pair<int,int> >Q; bfs[dat[0].second.first][dat[0].second.second]=-dat[0].first; Q.push(make_pair(dat[0].second.first,dat[0].second.second)); int now=1; while(Q.size()){ int row=Q.front().first; int col=Q.front().second; Q.pop(); while(-dat[now].first==bfs[row][col]){ if(bfs[dat[now].second.first][dat[now].second.second]==-1){ bfs[dat[now].second.first][dat[now].second.second]=-dat[now].first; Q.push(make_pair(dat[now].second.first,dat[now].second.second)); } now++; } for(int i=0;i<8;i++){ if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&bfs[row+dx[i]][col+dy[i]]==-1&&bfs[row][col]>0){ bfs[row+dx[i]][col+dy[i]]=bfs[row][col]-1; Q.push(make_pair(row+dx[i],col+dy[i])); } } } long long ret=0; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ ret+=(bfs[i][j]==-1)?0:bfs[i][j]; // printf("%d ",bfs[i][j]); } //printf("\n"); } printf("%lld\n",ret); }
2010 Stairs
累積和をもちつつDP。
#include<stdio.h> int dat[500001]; int dp1[500001]; int dp2[500001]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=1;i<=a;i++)scanf("%d",dat+i); for(int i=1;i<=a;i++)dat[i]+=dat[i-1]; dp1[0]=1; dp2[0]=1; int at=0; for(int i=1;i<=a;i++){ while(dat[i]-dat[at]>b)at++; dp1[i]=(dp2[i-1]-((at>0)?dp2[at-1]:0)+1234567)%1234567; dp2[i]=(dp2[i-1]+dp1[i])%1234567; } printf("%d\n",dp1[a]); }
2011 Orienteering
トポロジカルソートとDPとDijkstraを使った印象がある。実際は複合するだけ。
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> using namespace std; vector<int> ts; int dist[1001][1001]; int ans[1001][1001]; int ijk[1001][1001]; bool v[1001][1001]; int check[1001]; int color[1001]; int list[1001]; vector<pair<int,int> > g[1001]; void dfs(int a){ color[a]=1; for(int i=0;i<g[a].size();i++){ if(!color[g[a][i].first]){ dfs(g[a][i].first); } } ts.push_back(a); color[a]=2; } int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%d",check+i); for(int i=0;i<b;i++){ int c,d,e; scanf("%d%d%d",&c,&d,&e); c--; d--; g[c].push_back(make_pair(d,e)); } for(int i=0;i<a;i++){ if(!color[i]){ dfs(i); } } reverse(ts.begin(),ts.end()); for(int i=0;i<a;i++) for(int j=0;j<a;j++) dist[i][j]=999999999; for(int i=0;i<a;i++){ dist[ts[i]][ts[i]]=0; for(int j=i;j<a;j++){ for(int k=0;k<g[ts[j]].size();k++) dist[ts[i]][g[ts[j]][k].first]=min(dist[ts[i]][g[ts[j]][k].first],dist[ts[i]][ts[j]]+g[ts[j]][k].second); } } int now=1; for(int i=0;i<a;i++){ if(check[ts[i]])list[now++]=ts[i]; } list[now++]=a-1; for(int i=0;i<a;i++) for(int j=0;j<a;j++) ans[i][j]=999999999; ans[0][0]=0; for(int i=0;i<now;i++){ for(int j=0;j<now;j++){ ans[i][max(i,j)+1]=min(ans[i][max(i,j)+1],ans[i][j]+dist[list[j]][list[max(i,j)+1]]); ans[max(i,j)+1][j]=min(ans[max(i,j)+1][j],ans[i][j]+dist[list[i]][list[max(i,j)+1]]); } } int ret=999999999; for(int i=0;i<now;i++) ret=min(ret,min(ans[i][now-1]+dist[list[i]][list[now-1]],ans[now-1][i]+dist[list[i]][list[now-1]])); printf("%d\n",ret); }
2011 Report
うまくDFSするとよくある問題になる。BIT使っていたらしい。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int bit[131072]; vector<int> rev[131072]; int sum(int a,int b){ if(a)return sum(0,b)-sum(0,a-1); int ret=0; for(;b>=0;b=(b&(b+1))-1)ret+=bit[b]; return ret; } void add(int a,int b){ for(;a<131072;a|=a+1)bit[a]+=b; } int c[100000]; int v[100000]; int num[100000]; int now; int left[100000]; int right[100000]; int at; vector<int> g[100000]; void dfs(int a){ v[a]=1; if(v[c[a]]<0)dfs(c[a]); num[now++]=a; } void DFS(int a){ v[a]=now; for(int i=0;i<rev[a].size();i++){ if(v[rev[a][i]]==-1)DFS(rev[a][i]); } } void dfs2(int a){ left[a]=at++; for(int i=0;i<g[a].size();i++){ dfs2(g[a][i]); } right[a]=at-1; } int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",c+i); for(int i=0;i<a;i++){ c[i]--; rev[c[i]].push_back(i); } for(int i=0;i<a;i++)v[i]=-1; for(int i=0;i<a;i++){ if(v[i]<0){ dfs(i); } } for(int i=0;i<a;i++)v[i]=-1; now=0; for(int i=a-1;i>=0;i--){ if(v[num[i]]<0){ DFS(num[i]); now++; } } for(int i=0;i<a;i++){ if(v[i]!=v[c[i]]){ g[v[c[i]]].push_back(v[i]); num[v[i]]=-1; } } for(int i=0;i<now;i++){ if(~num[i]){ dfs2(i); } } for(int i=0;i<a;i++){ // printf("%d %d %d ",v[i],left[v[i]],right[v[i]]); printf("%d\n",sum(left[v[i]],right[v[i]])); add(left[v[i]],1); } }
2011 Keycards
数学する。適当にコンビネーションの計算をがんばる。逆元は拡張ほげを導き出すのに時間がかかるのでp-2乗した。ちなみにこれは毎回同じ定数1つになるので正直言ってTLE気にするならマジックナンバー化してしまったほうが安心できる。O(N)でいけることがわかる。オーバーフローに注意
#include<stdio.h> long long mod=1000000007; long long left[1000002]; long long right[1000002]; long long rj[1000002]; long long C[1000002]; int main(){ int a,b; scanf("%d%d",&a,&b); left[0]=1; for(int i=1;i<1000002;i++){ left[i]=(left[i-1]*i)%mod; } right[1000001]=1000001; for(int i=1000000;i>0;i--){ right[i]=(right[i+1]*i)%mod; } long long s=left[1000001]; long long t=1; int c=mod-2; while(c){ if(c&1)t=t*s%mod; c/=2; s=s*s%mod; } long long at=1; long long val=1; for(int i=0;i<=a-b;i++){ C[i]=at; // printf("%lld\n",C[i]); at=at*(a-b-i)%mod; at=at*left[i]%mod*right[i+2]%mod*t%mod; } for(int i=1;i<=b;i++){ val=val*(1+a-i)%mod; val=val*(left[i-1])%mod*right[i+1]%mod*t%mod; } rj[0]=2; for(int i=1;i<1000001;i++)rj[i]=rj[i-1]*rj[i-1]%mod; long long ret=0; for(int i=0;i<=(a-b);i++){ ret=(ret+rj[i]*C[i]*(((a-b-i)&1)?-1:1))%mod; while(ret<0)ret+=mod; } if(a==b)ret=(ret+mod-1)%mod; printf("%lld\n",ret*val%mod); }
2010 Plugs
いもす法してから1つ1つ決めていく。
#include<stdio.h> #include<algorithm> using namespace std; int dat[3001][3001]; int p[3001]; int ans[3001]; bool use[3001]; bool v[3001]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ int c,d,e,f; scanf("%d%d%d%d",&c,&e,&d,&f); dat[c-1][d-1]++; dat[c-1][f]--; dat[e][d-1]--; dat[e][f]++; } for(int i=0;i<a;i++){ int val=0; for(int j=0;j<a;j++){ dat[i][j]=(val+=dat[i][j]); } } for(int i=0;i<a;i++){ int val=0; for(int j=0;j<a;j++){ dat[j][i]=(val+=dat[j][i]); } } for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(dat[i][j])p[i]++; } } //for(int i=0;i<a;printf("\n"),i++) // for(int j=0;j<a;printf("%d ",dat[i][j++])); int now=a; for(int i=0;i<a;i++){ int at=0; for(int j=0;j<a;j++){ if(!v[j]&&p[j]==now-1){ for(int k=0;k<a;k++){ if(!use[k]&&!dat[j][k]){ at=k; break; } } ans[j]=at; // printf("%d\n",at); v[j]=true; break; } } use[at]=true; for(int j=0;j<a;j++)if(dat[j][at])p[j]--; now--; } for(int i=0;i<a;i++)printf("%d\n",ans[i]+1); }
2010 Lake
DP。複雑なDPを書いていたが絶対もっと簡単に書ける。こういう座標の管理苦手。
#include<stdio.h> #include<algorithm> using namespace std; int x[4000]; pair<int,int>b[2000]; int dp[4000][4000]; int other[4000]; int n; int solve(int a,int b){ if(a>=n)a-=n; if(b>=n)b-=n; if(a<0)a+=n; if(b<0)b+=n; // printf("%d %d\n",a,b); if(a==b)return 0; if(~dp[a][b])return dp[a][b]; int p=other[a]; int ret=0; ret=solve(a+1,b); if(a<b){ if(a<p&&p<=b){ int s=a+1; int t=p-1; int u=p+1; int v=b; if(s>=n)s-=n; if(u>=n)u-=n; if(t<0)t+=n; if((a+1)%n==p)s=t; if(p==b)u=v; ret=max(ret,solve(s,t)+solve(u,v)+1); } }else{ if((!(b+1<=p&&p<=a-1))&&(a<p||p<=b)){ int s=a+1; int t=p-1; int u=p+1; int v=b; if(s>=n)s-=n; if(u>=n)u-=n; if(t<0)t+=n; if((a+1)%n==p)s=t; if(p==b)u=v; ret=max(ret,solve(s,t)+solve(u,v)+1); } } return dp[a][b]=ret; } int main(){ int a; scanf("%d",&a); n=a*2; for(int i=0;i<a;i++)scanf("%d%d",&b[i].first,&b[i].second); for(int i=0;i<a;i++){ x[i*2]=b[i].first; x[i*2+1]=b[i].second; } std::sort(x,x+a*2); for(int i=0;i<a;i++){ b[i].first=lower_bound(x,x+a*2,b[i].first)-x; b[i].second=lower_bound(x,x+a*2,b[i].second)-x; if(b[i].first>b[i].second)swap(b[i].first,b[i].second); } for(int i=0;i<a;i++){ other[b[i].first]=b[i].second; other[b[i].second]=b[i].first; } for(int i=0;i<a*2;i++) for(int j=0;j<a*2;j++) dp[i][j]=-1; int ret=0; for(int i=0;i<a;i++){ ret=max(ret,(b[i].first+1>b[i].second-1)?0:solve(b[i].first+1,b[i].second-1)+(b[i].first+n-b[i].second<2)?0:solve(b[i].second+1,b[i].first-1)+1); // printf("\n"); } printf("%d\n",ret); }
2010 Highway
ずいぶん昔に書いたらしく。本気を出して解いている。今やったらもっとまともなソースになりそうである。LCAとBITを使う。今ならLCAは10分ちょいでかけるようになってるので合宿の中では楽なほう?
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; int st1[262144];//木の下から上に行くのにかかる時間(dfs順は大→小) int st2[262144];//木の上から下に行くのにかかる時間(dfs順は小→大) int lca[1048576];//SEGTREE.nearest common共通祖先 int node[100000];//DFS順 なかに点のもとの番号を入れる int nodeleft[100000];//↑を使うために必要な各ノードの左側のnowlca順 いれるものは点の番号(DFS順ではないらしい!) bool visited[100000];//DFS用 vector<int> g[100000];//グラフ。途中からいらない int right[100000];//直上のノードまでの変更があったとき、どこまで影響するか (n)./(1) この/のノードの話である。DFS順 int nowlca;//LCA用 int Count;//DFS順 pair<int,int> edge[100000];//辺の両端 int cost1[100000];//↑のDFS順大→小 int cost2[100000];//↑↑のDFS順小→大 char str[2]; int S; int LCA(int a,int b,int s,int t,int u){ if(a>t||s>b)return 99999999; if(a<=s&&t<=b)return lca[u]; return min(LCA(a,b,s,(s+t)/2,2*u),LCA(a,b,(s+t)/2+1,t,2*u+1)); } void INIT_LCA(int a,int b){ a+=524288; lca[a]=b; a/=2; while(a){ lca[a]=min(lca[a*2],lca[a*2+1]); a/=2; } } void CHG(int a,int b,int c,int d,int e,int f,int g){ if(a==1){ if(b>e||c<d)return; if(b<=d&&e<=c){ st1[f]+=g; return; } CHG(a,b,c,d,(d+e)/2,f*2,g); CHG(a,b,c,(d+e)/2+1,e,f*2+1,g); }else{ if(b>e||c<d)return; if(b<=d&&e<=c){ st2[f]+=g; return; } CHG(a,b,c,d,(d+e)/2,f*2,g); CHG(a,b,c,(d+e)/2+1,e,f*2+1,g); } } int query(int a,int b){ int ret=0; b+=131072; while(b){ if(a==1)ret+=st1[b]; if(a==2)ret+=st2[b]; b/=2; } return ret; } int dfs(int a){ int p=Count++; visited[a]=true; node[a]=p; INIT_LCA(nowlca++,p); st1[node[a]+131072]=st2[node[a]+131072]=S; nodeleft[a]=nowlca-1; for(int i=0;i<g[a].size();i++){ if(!visited[g[a][i]]){ S++; dfs(g[a][i]); S--; INIT_LCA(nowlca++,p); } } right[p]=Count-1; } int main(){ int a,b; for(int i=0;i<1048576;i++)lca[i]=99999999; scanf("%d%d",&a,&b); for(int i=0;i<a-1;i++){ int c,d; scanf("%d%d",&c,&d); edge[i]=make_pair(c-1,d-1); g[c-1].push_back(d-1); g[d-1].push_back(c-1); cost1[i]=cost2[i]=1; } INIT_LCA(nowlca++,0); dfs(0); // for(int i=0;i<a;i++)printf("%d ",node[i]); // printf("\n"); // for(int i=0;i<nowlca;i++)printf("%d ",lca[i+524288]); // printf("\n"); for(int i=0;i<b;i++){ scanf("%s",str); if(str[0]=='I'){ int c,d,e; scanf("%d%d%d",&c,&d,&e); if((edge[c-1].first<edge[c-1].second&&node[edge[c-1].first]<node[edge[c-1].second])||(edge[c-1].first>edge[c-1].second&&node[edge[c-1].first]>node[edge[c-1].second])){ //のぼりが下向き // printf("%d %d\n",max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])]); CHG(1,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,e-cost1[c-1]); CHG(2,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,d-cost2[c-1]); cost1[c-1]=e; cost2[c-1]=d; } else{ //のぼりが上向き // printf("%d %d\n",max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])]); CHG(1,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,d-cost1[c-1]); CHG(2,max(node[edge[c-1].first],node[edge[c-1].second]),right[max(node[edge[c-1].first],node[edge[c-1].second])],0,131071,1,e-cost2[c-1]); cost1[c-1]=d; cost2[c-1]=e; } }else{ int c,d; scanf("%d%d",&c,&d); int root=LCA(min(nodeleft[c-1],nodeleft[d-1]),max(nodeleft[c-1],nodeleft[d-1]),0,524287,1); int rootdist=query(1,root)+query(2,root); // printf("%d\n",root); // printf("%d %d %d\n",query(1,node[c-1]),query(2,node[d-1]),rootdist); printf("%d\n",query(1,node[c-1])+query(2,node[d-1])-rootdist); } } }
2010 Contest
くそげ〜
#include<stdio.h> #include<algorithm> using namespace std; int score[10]; char type[20]; int res[1000]; int time[1000][10]; int wa[1000][10]; int main(){ int a,b,c,d,e; scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); for(int i=0;i<b;i++)scanf("%d",score+i); for(int i=0;i<e;i++){ int f,g,h; scanf("%d%d%d%s",&f,&g,&h,type); if(type[0]=='o'){ time[g-1][h-1]=f; }else if(type[0]=='i'){ wa[g-1][h-1]++; }else{ res[g-1]+=max(d,score[h-1]-(f-time[g-1][h-1])-120*wa[g-1][h-1]); } } for(int i=0;i<a;i++)printf("%d\n",res[i]); return 0; }
2010 Hide and seek
Starry Sky Treeをやる。イベント処理するだけ。
#include<stdio.h> #include<algorithm> using namespace std; int segtree[262144]; int query(int a,int b,int c,int d,int e){ if(d==e)return d; if(b+segtree[a*2]>=c){ return query(a*2,b+segtree[a*2],c,d,(d+e)/2); }else return query(a*2+1,b+segtree[a*2+1],c,(d+e)/2,e); } void add(int a,int b,int c,int d,int e,int f){ if(d<a||b<c)return; if(c<=a&&b<=d){ segtree[e]+=f; }else{ add(a,(a+b)/2,c,d,e*2,f); add((a+b)/2+1,b,c,d,e*2+1,f); } if(e!=1){ if(segtree[e]>0||segtree[e^1]>0){ int P=max(segtree[e],segtree[e^1]); segtree[e]-=P; segtree[e^1]-=P; segtree[e/2]+=P; } } } pair<int,pair<int,int> > p[50000]; pair<int,int>event[50000]; int x[50000]; int y[50000]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d%d%d",&p[i].second.first,&p[i].first,&p[i].second.second); p[i].second.second+=p[i].second.first-1; } for(int i=0;i<b;i++){ scanf("%d",&event[i].first); event[i].first++; event[i].second=i; } std::sort(p,p+a); std::sort(event,event+b); int at=0; for(int i=0;i<b;i++){ bool dame=false; while(segtree[1]<event[i].first){ if(at<a){ add(0,131071,p[at].second.first,p[at].second.second,1,1); at++; }else{ dame=true; break; } } if(dame){ x[event[i].second]=-2; y[event[i].second]=-1; }else{ y[event[i].second]=p[at-1].first; x[event[i].second]=query(1,segtree[1],event[i].first,0,131071); } } for(int i=0;i<b;i++)printf("%d %d\n",x[i]+1,y[i]); }
2010 Finals
誰でも解けると思う。
#include<stdio.h> #include<algorithm> using namespace std; int UF[100000]; pair<int,pair<int,int> > e[100000]; int FIND(int a){ if(UF[a]<0)return a; return UF[a]=FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a); b=FIND(b); if(a==b)return; UF[a]+=UF[b]; UF[b]=a; return; } int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++)UF[i]=-1; for(int i=0;i<b;i++){ int p,q,r; scanf("%d%d%d",&p,&q,&r); e[i]=make_pair(r,make_pair(p-1,q-1)); } std::sort(e,e+b); int nokori=a-c; int ret=0; int at=0; while(nokori){ int s=e[at].second.first; int t=e[at].second.second; if(FIND(s)!=FIND(t)){ UNION(s,t); ret+=e[at].first; nokori--; } at++; } printf("%d\n",ret); }
2010 Regions
二分探索して葉からどんどん切っていく。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<pair<int,int> > G[30000]; vector<pair<int,int> > g[30000]; int size[30000]; int t[30000]; int M; int now; void cut(int a){ for(int i=0;i<g[a].size();i++)cut(g[a][i].first); if(g[a].size()==0){ size[a]=0; return; } if(g[a].size()==1){ int R=size[g[a][0].first]+g[a][0].second; if(R>M){ size[a]=0; now++; return; }else{ size[a]=R; return; } } if(g[a].size()>1){ for(int i=0;i<g[a].size();i++){ t[i]=size[g[a][i].first]+g[a][i].second; } std::sort(t,t+g[a].size()); if(t[0]>M){ size[a]=0; now+=g[a].size(); return; } for(int i=1;i<g[a].size();i++){ if(t[i]+t[i-1]>M){ size[a]=t[i-1]; now+=(g[a].size()-i); return; } } size[a]=t[g[a].size()-1]; } } void init(int a,int b){ for(int i=0;i<G[a].size();i++){ if(b!=G[a][i].first){ g[a].push_back(G[a][i]); init(G[a][i].first,a); } } } int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a-1;i++){ int c,d,e; scanf("%d%d%d",&c,&d,&e); c--; d--; G[c].push_back(make_pair(d,e)); G[d].push_back(make_pair(c,e)); } init(0,-1); int left=-1; int right=99999999; while(left+1<right){ M=(left+right)/2; now=0; cut(0); now++; // printf("%d %d\n",M,now); if(now<=b){ right=M; }else left=M; } printf("%d\n",right); }
2010 DNA Synthesizer
Trieすれば簡単な問題になる。Aho-Corasickでもいける。
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using namespace std; char goal[150001]; char sa[50000][21]; int dp[150021]; struct Trie{ bool mark; int A; int T; int G; int C; Trie(){ mark=false; A=-1; T=-1; G=-1; C=-1; } }; vector<Trie> v; int main(){ int a; scanf("%d",&a); scanf("%s",goal); v.push_back(Trie()); for(int i=0;i<a;i++)scanf("%s",sa[i]); for(int i=0;i<a;i++){ int now=0; int len=strlen(sa[i]); for(int j=0;j<len;j++){ switch(sa[i][j]){ case 'A': if(v[now].A==-1){ v[now].A=v.size(); v.push_back(Trie()); now=v[now].A; }else now=v[now].A; break; case 'T': if(v[now].T==-1){ v[now].T=v.size(); v.push_back(Trie()); now=v[now].T; }else now=v[now].T; break; case 'G': if(v[now].G==-1){ v[now].G=v.size(); v.push_back(Trie()); now=v[now].G; }else now=v[now].G; break; case 'C': if(v[now].C==-1){ v[now].C=v.size(); v.push_back(Trie()); now=v[now].C; }else now=v[now].C; } if(j==len-1)v[now].mark=true; } } for(int i=1;i<150021;i++)dp[i]=99999999; int length=strlen(goal); for(int i=0;i<length;i++){ int now=0; for(int j=0;j<20;j++){ if(i+j>length)break; switch(goal[i+j]){ case 'A': now=v[now].A; break; case 'T': now=v[now].T; break; case 'G': now=v[now].G; break; case 'C': now=v[now].C; } if(now==-1)break; if(v[now].mark){ for(int k=i+j;k>i;k--) dp[k]=min(dp[k],dp[i]+1); } } } printf("%d\n",dp[length-1]); }
2010 A+B Problem
座標圧縮してうめていって足し算した。みんなどうやってやってるのだろう
#include<stdio.h> #include<algorithm> using namespace std; pair<int,int>A[20001]; pair<int,int>B[20001]; long long temp[200000]; long long zahyou[200000]; int val[200000]; int S[200000]; int T[200000]; int U[200000]; pair<int,long long> out[200000]; int main(){ int a; scanf("%d",&a); long long p=0,q=0; for(int i=0;i<a;i++){ scanf("%d%d",&A[i].first,&A[i].second); p+=A[i].second; } int b; scanf("%d",&b); for(int i=0;i<b;i++){ scanf("%d%d",&B[i].first,&B[i].second); q+=B[i].second; } int at=0; for(int i=0;i<a;i++){ temp[at++]=p+1; temp[at++]=p; p-=A[i].second; } for(int i=0;i<b;i++){ temp[at++]=q+1; temp[at++]=q; q-=B[i].second; } temp[at++]=1; std::sort(temp,temp+at); int now=0; zahyou[now++]=temp[0]; for(int i=1;i<at;i++){ if(temp[i]!=temp[i-1])zahyou[now++]=temp[i]; } int K=a-1; long long V=A[K].second; for(int i=0;i<now;i++){ while(K>0&&V<zahyou[i]){ V+=A[K-1].second; K--; } if(K==0&&V<zahyou[i])K--; if(K>=0)S[i]=A[K].first; } K=b-1; V=B[K].second; for(int i=0;i<now;i++){ while(K>0&&V<zahyou[i]){ V+=B[K-1].second; K--; } if(K==0&&V<zahyou[i])K--; if(K>=0)T[i]=B[K].first; } bool up=false; for(int i=0;i<now;i++){ int m=S[i]+T[i]; if(up)m++; if(m>9){ up=true; m-=10; }else up=false; U[i]=m; } int ret=0; int P=0; long long ren=0; for(int i=now-1;i>=0;i--){ if(P!=U[i]){ if(ret==0&&P==0); else out[ret++]=make_pair(P,ren); P=U[i]; ren=zahyou[i]-(i?zahyou[i-1]:0); }else ren+=zahyou[i]-(i?zahyou[i-1]:0);; } out[ret++]=make_pair(P,ren); printf("%d\n",ret); for(int i=0;i<ret;i++)printf("%d %lld\n",out[i].first,out[i].second); }
2010 Sengoku
うまいぐあいに二分探索する。
#include<stdio.h> #include<algorithm> #include<set> using namespace std; pair<int,int> A[100000]; int ay[100000]; pair<int,int> B[100000]; int by[100000]; int sy[100000]; int a; int b; set<int> Y; int main(){ int c,n; scanf("%d%d",&c,&n); for(int i=0;i<n;i++){ int d,e; scanf("%d%d",&d,&e); if((d+e)%2)A[a++]=make_pair(d+e,d-e); else B[b++]=make_pair(d+e,d-e); } std::sort(A,A+a); std::sort(B,B+b); long long ret=0; int p=0; int q=0; for(int i=0;i<a;i++)sy[i]=A[i].second; std::sort(sy,sy+a); for(int i=0;i<a;i++){ if(i==0||sy[i]!=sy[i-1])ay[p++]=sy[i]; } for(int i=0;i<b;i++)sy[i]=B[i].second; std::sort(sy,sy+b); for(int i=0;i<b;i++){ if(i==0||sy[i]!=sy[i-1])by[q++]=sy[i]; } std::sort(ay,ay+p); std::sort(by,by+q); // for(int i=0;i<q;i++)printf("%d ",by[i]); for(int i=0;i<a;i++){ int yoko=min(A[i].first+1,c+c-A[i].first-1); int tate=min(c-A[i].second,c+A[i].second); if(i==0||A[i].first!=A[i-1].first)ret+=yoko; if(!Y.count(A[i].second)){ ret+=tate; Y.insert(A[i].second); } if(i==0||A[i].first!=A[i-1].first)ret-=upper_bound(ay,ay+p,yoko)-lower_bound(ay,ay+p,-yoko); // printf("%d %d %d\n",(yoko+2)/2,(-yoko-2)/2,upper_bound(ay,ay+p,(yoko+2)/2)-lower_bound(ay,ay+p,(-yoko-2)/2)); // printf("%lld\n",ret); } // printf("\n"); Y.clear(); for(int i=0;i<b;i++){ int yoko=min(B[i].first+1,c+c-B[i].first-1); int tate=min(c-B[i].second,c+B[i].second); if(i==0||B[i].first!=B[i-1].first)ret+=yoko; if(!Y.count(B[i].second)){ ret+=tate; Y.insert(B[i].second); } if(i==0||B[i].first!=B[i-1].first)ret-=upper_bound(by,by+q,yoko)-lower_bound(by,by+q,-yoko); // printf("%d %d %d\n",(yoko+3)/2,(-yoko-3)/2,upper_bound(by,by+q,(yoko+3)/2)-lower_bound(by,by+q,(-yoko-3)/2)); // printf("%lld\n",ret); } printf("%lld\n",ret); }
2009 Distribution
Greedyっぽいことをなんどもやるだけで解ける。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int> g[10000]; int rev[10000]; int dat[10000]; int val[10000]; void dfs(int a,int b){ val[a]=b+dat[a]; for(int i=0;i<g[a].size();i++){ dfs(g[a][i],b+dat[a]); } } void del(int a){ if(a<0)return; dat[a]=0; del(rev[a]); } int main(){ int a,b; scanf("%d%d",&a,&b); int par=0; for(int i=0;i<a;i++){ int c,d; scanf("%d%d",&c,&d); if(c==0) par=i; else{ g[c-1].push_back(i); } rev[i]=c-1; dat[i]=d; } int ret=0; for(int i=0;i<b;i++){ dfs(par,0); int at=0; int M=0; for(int j=0;j<a;j++){ if(val[j]>M){ M=val[j]; at=j; } } ret+=M; del(at); } printf("%d\n",ret); }
2009 Ski
二分探索とDPをした
#include<stdio.h> #include<queue> #include<algorithm> #include<vector> using namespace std; struct wolf{ int to,spd,dist; wolf(){} wolf(int a,int b,int c){ to=a; spd=c; dist=b; } }; vector<wolf>g[10000]; bool start[10000]; double dp[10000]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<b;i++){ int d; scanf("%d",&d); start[d-1]=true; } for(int i=0;i<c;i++){ int p,q,r,s; scanf("%d%d%d%d",&p,&q,&r,&s); g[p-1].push_back(wolf(q-1,r,s)); } double left=0; double right=100000; for(int i=0;i<50;i++){ double M=(left+right)/2; for(int j=0;j<a;j++){ if(start[j])dp[j]=0; else dp[j]=99999999; } for(int j=0;j<a;j++){ for(int k=0;k<g[j].size();k++){ dp[g[j][k].to]=min(dp[g[j][k].to],dp[j]+((double)g[j][k].dist-M*g[j][k].dist/g[j][k].spd)); } } if(dp[a-1]<0)right=M; else left=M; } printf("%.0f\n",left); }
2009 Advertisement
昔強連結成分分解知らないときに書いたソース。今はみんな書けるらしい。
#include<stdio.h> #include<algorithm> #include<vector> #include<stack> using namespace std; vector<int> g[100000]; vector<vector<int> > scc; int num[100000]; int low[100000]; int ireji[100000]; stack<int> S; bool inS[100000]; int time; int type[100000]; void visit(int v){ time++; low[v]=time; num[v]=time; S.push(v); inS[v]=true; for(int i=0;i<g[v].size();i++){ int w=g[v][i]; if(num[w]==0){ visit(w); low[v]=min(low[v],low[w]); }else if(inS[w]){ low[v]=min(low[v],num[w]); } } if(low[v]==num[v]){ scc.push_back(vector<int>()); while(1){ int w=S.top(); S.pop(); inS[w]=false; scc.back().push_back(w); if(v==w)break; } } } int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ int c,d; scanf("%d%d",&c,&d); g[c-1].push_back(d-1); } for(int i=0;i<a;i++){ if(num[i]==0)visit(i); } for(int i=0;i<scc.size();i++){ for(int j=0;j<scc[i].size();j++){ type[scc[i][j]]=i; } } for(int i=0;i<a;i++){ for(int j=0;j<g[i].size();j++){ if(type[i]!=type[g[i][j]]){ ireji[type[g[i][j]]]++; } } } int ret=0; for(int i=0;i<scc.size();i++)if(ireji[i]==0)ret++; printf("%d\n",ret); }
2009 Stamps
あぶなっかしいDPで通った。
#include<stdio.h> #include<algorithm> using namespace std; char str[1048576]; pair<int,int> dp1[1048576]; pair<int,int> dp2[1048576]; int main(){ int a; scanf("%d%s",&a,str); for(int i=0;i<a;i++){ dp1[i]=make_pair(999999999,999999999); dp2[i]=make_pair(999999999,999999999); } if(str[0]=='I'){ dp1[0]=make_pair(0,1); dp2[0]=make_pair(1,0); }else{ dp1[0]=make_pair(1,1); dp2[0]=make_pair(1,0); } for(int i=1;i<a;i++){ dp1[i]=make_pair(dp1[i-1].first+1,dp1[i-1].second); dp2[i]=make_pair(dp2[i-1].first+1,dp2[i-1].second); if(str[i]=='I'){ dp1[i]=min(dp1[i],make_pair(dp2[i-1].first,dp2[i-1].second+1)); dp2[i]=min(dp2[i],make_pair(dp1[i-1].first+1,dp1[i-1].second+1)); }else{ dp1[i]=min(dp1[i],make_pair(dp2[i-1].first+1,dp2[i-1].second+1)); dp2[i]=min(dp2[i],make_pair(dp1[i-1].first,dp1[i-1].second+1)); } // printf("%d %d %d %d\n",dp1[i].first,dp1[i].second,dp2[i].first,dp2[i].second); } int ans=dp1[a-1].first; int p=dp1[a-1].second; if(ans>dp2[a-1].first+1||(ans==dp2[a-1].first+1&&p>dp2[a-1].second+1)){ ans=dp2[a-1].first+1; p=dp2[a-1].second+1; } if(p==0)p=1; printf("%d\n%d\n",ans,p); }
2009 Sequence
メモリ制限をみてソースを長くした。24個だし見た感じビット演算っぽいよね。
#include<stdio.h> bool mark[1<<24]; int dat[25]; int main(){ int a; long long b,c; scanf("%d%lld%lld",&a,&b,&c); int val=0; for(int i=0;i<a;i++){ scanf("%d",dat+i); dat[i]%=2; val+=dat[i]*(1<<i); } int S=val; int T=val; int at=val; int now=a; mark[val]=true; int C=0; int D=0; while(1){ now++; if(((val&1)^(val>>(a-1))))C++; val=val/2+(((val&1)^(val>>(a-1)))<<(a-1)); // printf("%d\n",val); if(mark[val]){ break; }else mark[val]=true; } int begin=a; while(1){ if(val==at){ break; } if(((at&1)^(at>>(a-1))))D++; at=at/2+(((at&1)^(at>>(a-1)))<<(a-1)); begin++; } b--; long long P=0; long long Q=0; if(b>=now){ P+=(b-begin)/(now-begin)*(C-D); b=begin+(b-begin)%(now-begin); } if(c>=now){ Q+=(c-begin)/(now-begin)*(C-D); c=begin+(c-begin)%(now-begin); } for(int i=0;i<b;i++){ if(i<a)P+=dat[i]; else{ if(((S&1)^(S>>(a-1))))P++; S=S/2+(((S&1)^(S>>(a-1)))<<(a-1)); } } S=T; for(int i=0;i<c;i++){ if(i<a)Q+=dat[i]; else{ if(((S&1)^(S>>(a-1))))Q++; S=S/2+(((S&1)^(S>>(a-1)))<<(a-1)); } } printf("%lld\n",Q-P); }
2008 Origami
別に平面走査とかしなくても解ける。
#include<stdio.h> #include<algorithm> using namespace std; pair<int,int> dat[4000000]; int main(){ int now=0; int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++){ int d,e,f,g; scanf("%d%d%d%d",&d,&e,&f,&g); for(int j=d;j<=f;j++) for(int k=e;k<=g;k++) dat[now++]=make_pair(j,k); } std::sort(dat,dat+now); int ans=1; int val=1; for(int i=1;i<now;i++){ if(dat[i].first==dat[i-1].first&&dat[i].second==dat[i-1].second){ val++; }else val=1; ans=max(ans,val); } printf("%d\n",ans); int ret=0; if(ans==1)ret++; val=1; for(int i=1;i<now;i++){ if(dat[i].first==dat[i-1].first&&dat[i].second==dat[i-1].second){ val++; }else val=1; if(val==ans)ret++; } printf("%d\n",ret); }
2008 Cheeting
二分探査した。
#include<stdio.h> #include<algorithm> using namespace std; int x[100000]; int y[100000]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ scanf("%d%d",x+i,y+i); } std::sort(x,x+b); std::sort(y,y+b); int left=0; int right=1000000000; while(left-right){ int M=(left+right)/2; int first=0; int use=2; for(int i=0;i<b;i++){ if(x[i]-x[first]>M){ use++; first=i; } } first=0; for(int i=0;i<b;i++){ if(y[i]-y[first]>M){ use++; first=i; } } if(use<=a){ right=M; }else{ if(left+1==right)break; left=M; } } printf("%d\n",right); }
2008 Nile.com
DPやるだけ
#include<stdio.h> #include<algorithm> using namespace std; int dp1[3000][365]; int dp2[3000][365]; int dp3[3000][365]; int dat[3000][365]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ for(int j=0;j<a;j++){ scanf("%d",&dat[j][i]); } } for(int i=0;i<3000;i++) for(int j=0;j<365;j++) dp1[i][j]=dp2[i][j]=dp3[i][j]=99999999; for(int i=0;i<a;i++){ dp1[i][0]=dat[i][0]; } for(int i=1;i<b;i++){ int nowmin=99999999; for(int j=0;j<a;j++){ nowmin=min(nowmin,dp1[j][i-1]); nowmin=min(nowmin,dp2[j][i-1]); nowmin=min(nowmin,dp3[j][i-1]); } for(int j=0;j<a;j++){ dp1[j][i]=nowmin+dat[j][i]; } for(int j=0;j<a;j++){ dp2[j][i]=dp1[j][i-1]+dat[j][i]/10*9; } for(int j=0;j<a;j++){ dp3[j][i]=min(dp2[j][i-1],dp3[j][i-1])+dat[j][i]/10*7; } } int ret=999999999; for(int i=0;i<a;i++){ ret=min(ret,dp1[i][b-1]); ret=min(ret,dp2[i][b-1]); ret=min(ret,dp3[i][b-1]); } printf("%d\n",ret); }
2008 Flu
バケット法。こういうのは計算量に自信がもてない。
#include<stdio.h> #include<algorithm> #include<queue> #include<vector> using namespace std; pair<int,int> p[100000]; vector<int>w[1000][1000]; int bfs[100000]; int dx[]={1,1,1,0,0,-1,-1,-1,0}; int dy[]={1,0,-1,1,-1,1,0,-1,0}; int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); for(int i=0;i<a;i++)scanf("%d%d",&p[i].first,&p[i].second); for(int i=0;i<a;i++){ w[p[i].first/c][p[i].second/c].push_back(i); } for(int i=0;i<a;i++){ bfs[i]=99999999; } bfs[0]=0; queue<int> Q; Q.push(0); while(Q.size()){ int at=Q.front(); Q.pop(); int row=p[at].first/c; int col=p[at].second/c; for(int i=0;i<9;i++){ if(0<=row+dx[i]&&row+dx[i]<1000&&0<=col+dy[i]&&col+dy[i]<1000){ for(int j=0;j<w[row+dx[i]][col+dy[i]].size();j++){ int q=w[row+dx[i]][col+dy[i]][j]; if(bfs[q]==99999999&&(p[q].first-p[at].first)*(p[q].first-p[at].first)+(p[q].second-p[at].second)*(p[q].second-p[at].second)<=c*c){ bfs[q]=bfs[at]+1; Q.push(q); } } } } } int ret=0; for(int i=0;i<a;i++){ if(d-b<bfs[i]&&bfs[i]<=d)ret++; // printf("%d ",bfs[i]); } printf("%d\n",ret); }
2008 Committee
木DPするだけ
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int> t[100000]; int v[100000]; bool visited[100000]; int dp[100000]; int solve(int a){ if(visited[a])return dp[a]; int ret=v[a]; for(int i=0;i<t[a].size();i++)if(solve(t[a][i])>0)ret+=solve(t[a][i]); visited[a]=true; return dp[a]=ret; } int main(){ int a; for(int i=0;i<100000;i++){ visited[i]=false; v[i]=0; dp[i]=0; } scanf("%d",&a); int s=0; int m=-99999999; for(int i=0;i<a;i++){ int b,c; scanf("%d%d",&b,&c); if(b!=0)t[b-1].push_back(i); else s=i; v[i]=c; m=max(m,c); } int ret=m; for(int i=0;i<a;i++)ret=max(ret,solve(i)); printf("%d\n",ret); }
2007 Lines
幾何と規則性
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; int X1[1000],Y1[1000],X2[1000],Y2[1000]; bool v[1000]; double A[1000]; double B[1000]; double C[1000]; pair<double,double>P[1000000]; pair<long long,long long >Q[1000000]; double Abs(double a){return a<0.0?-a:a;} //ax+by=c //y=-(a/b)x+(c/b) int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d%d%d%d",X1+i,Y1+i,X2+i,Y2+i); A[i]=Y1[i]-Y2[i]; B[i]=X2[i]-X1[i]; C[i]=A[i]*X1[i]+B[i]*Y1[i]; } int n=a; for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++){ if(v[i]||v[j])continue; if((Y2[i]-Y1[i])*(X2[j]-X1[j])==(Y2[j]-Y1[j])*(X2[i]-X1[i])){ if(X1[i]==X2[i]){ if(X1[i]==X1[j]){ v[j]=true; n--; } }else if((Y1[j]-Y1[i])*(X2[i]-X1[i])==(Y2[i]-Y1[i])*(X1[j]-X1[i])){ v[j]=true; n--; } } } } //printf("%d\n",n); int ret=n+1; int now=0; for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++){ if(!v[i]&&!v[j]){ if((Y2[i]-Y1[i])*(X2[j]-X1[j])==(Y2[j]-Y1[j])*(X2[i]-X1[i])); else{ double X=(double)(C[i]*B[j]-B[i]*C[j])/(A[i]*B[j]-B[i]*A[j]); if(Abs(B[i])>0.00001)P[now++]=make_pair(X,(double)(C[i]-X*A[i])/B[i]); else P[now++]=make_pair(X,(double)(C[j]-X*A[j])/B[j]); Q[now-1].first=(long long)(P[now-1].first*1000000000LL+0.000001); Q[now-1].second=(long long)(P[now-1].second*1000000000LL+0.000001); } } } } std::sort(Q,Q+now); // printf("%d\n",ret); int val=1; for(int i=1;i<now;i++){ // printf("%lld %lld\n",Q[i].first,Q[i].second); if(Q[i].first==Q[i-1].first&&Q[i].second==Q[i-1].second)val++; else{ int k=(int)sqrt(val*2)+1; ret+=k-1; val=1; } } if(now==0)val=0; int k=(int)sqrt(val*2)+1; ret+=k-1; val=1; printf("%d\n",ret); }
2007 Fiber
どうかんがえてもUnionFindするだけ。
#include<stdio.h> int UF[10000]; int FIND(int a){ if(UF[a]<0)return a; return UF[a]=FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a); b=FIND(b); if(a==b)return; UF[a]+=UF[b]; UF[b]=a; return; } int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++)UF[i]=-1; for(int i=0;i<b;i++){ int c,d; scanf("%d%d",&c,&d); UNION(c-1,d-1); } int ret=0; for(int i=0;i<a;i++)ret+=UF[i]<0?1:0; printf("%d\n",ret-1); }
2007 Route
ここからここまで〜みたいなものを頂点だとおもってDijkstra
#include<stdio.h> #include<algorithm> #include<queue> #include<vector> using namespace std; int x[100]; int y[100]; vector<pair<int,int> > g[100]; int ijk[100][100]; bool v[100][100]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i); for(int i=0;i<b;i++){ int c,d,e; scanf("%d%d%d",&c,&d,&e); c--; d--; g[c].push_back(make_pair(d,e)); g[d].push_back(make_pair(c,e)); } priority_queue<pair<int,pair<int,int> > >Q; for(int i=0;i<100;i++) for(int j=0;j<100;j++) ijk[i][j]=-1; for(int i=0;i<g[0].size();i++){ ijk[0][g[0][i].first]=g[0][i].second; Q.push(make_pair(-ijk[0][g[0][i].first],make_pair(0,g[0][i].first))); } while(Q.size()){ int cost=-Q.top().first; int at1=Q.top().second.first; int at2=Q.top().second.second; Q.pop(); if(v[at1][at2])continue; v[at1][at2]=true; for(int i=0;i<g[at2].size();i++){ if(!v[at2][g[at2][i].first]&&!(~ijk[at2][g[at2][i].first]&&ijk[at2][g[at2][i].first]<=cost+g[at2][i].second)&&(x[at1]-x[at2])*(x[g[at2][i].first]-x[at2])+(y[at1]-y[at2])*(y[g[at2][i].first]-y[at2])<=0){ ijk[at2][g[at2][i].first]=cost+g[at2][i].second; Q.push(make_pair(-ijk[at2][g[at2][i].first],make_pair(at2,g[at2][i].first))); } } } int ret=999999999; for(int i=0;i<a;i++){ if(~ijk[i][1])ret=min(ret,ijk[i][1]); } if(ret!=999999999)printf("%d\n",ret); else printf("-1\n"); }
2007 Anagram
very simple 数学
#include<stdio.h> char str[21]; int use[26]; long long C(int a,int b){ long long ret=1; for(int i=0;i<b;i++){ ret*=a-i; ret/=(i+1); } return ret; } long long calc(){ long long ret=1; int sum=0; for(int i=0;i<26;i++){ sum+=use[i]; } for(int i=0;i<26;i++){ ret*=C(sum,use[i]); sum-=use[i]; } return ret; } int main(){ scanf("%s",str); for(int i=0;str[i];i++)use[str[i]-'A']++; long long ret=0; for(int i=0;str[i];i++){ for(int j=0;j+'A'<str[i];j++){ if(use[j]){ use[j]--; ret+=calc(); use[j]++; } } use[str[i]-'A']--; } printf("%lld\n",ret+1); }
2007 Fermat
数学
#include<stdio.h> int rj[10000]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ int now=1; int val=i; int c=b; while(c){ if(c%2)now=now*val%a; val=val*val%a; c/=2; } // printf("%d ",now); rj[now]++; } long long ret=0; for(int i=0;i<a;i++){ ret+=rj[i]*rj[(i+1)%a]; } ret*=a-1; for(int i=0;i<a;i++){ ret+=rj[i]*rj[i]; } printf("%lld\n",ret); }
2007 Building
いまや常識レベルのDP
#include<stdio.h> #include<algorithm> using namespace std; int dat[1000]; int dp[1000]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",dat+i); dp[0]=1; int ret=1; for(int i=1;i<a;i++){ dp[i]=1; for(int j=0;j<i;j++){ if(dat[j]<dat[i])dp[i]=max(dp[i],dp[j]+1); } ret=max(ret,dp[i]); } printf("%d\n",ret); }
2007 Mall
よくある問題 解法を忘れるレベルの昔といた
#include<stdio.h> long long t[1000][1000]; long long p[1001][1001]; int main(){ int a,b,c,d; scanf("%d%d%d%d",&b,&a,&d,&c); for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ scanf("%lld",&t[i][j]); if(t[i][j]==-1)t[i][j]=100000000LL; } } for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ p[i+1][j+1]=p[i][j+1]+p[i+1][j]-p[i][j]+t[i][j]; } } long long ret=1000000000LL; for(int i=c-1;i<a;i++){ for(int j=d-1;j<b;j++){ if(ret>p[i+1][j+1]-p[i+1][j+1-d]-p[i+1-c][j+1]+p[i+1-c][j+1-d])ret=p[i+1][j+1]-p[i+1][j+1-d]-p[i+1-c][j+1]+p[i+1-c][j+1-d]; } } printf("%lld\n",ret); }
2007 Factorial
数学ってほどでもない
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a; scanf("%d",&a); int b=a; int now=2; int ret=0; while(a-1&&now*now<=a){ int val=0; while(a%now==0){ a/=now; val++; } if(val)ret=max(ret,val*now); now++; } if(a==1)printf("%d\n",ret); else printf("%d\n",max(ret,a)); }
2007 Score
クソゲー
#include<stdio.h> #include<algorithm> #include<functional> using namespace std; int score[100000]; int val[100000]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d",score+i); val[i]=score[i]; } std::sort(val,val+a,greater<int>()); for(int i=0;i<a;i++){ int t=lower_bound(val,val+a,score[i],greater<int>())-val; printf("%d\n",t+1); } }
途中からブログの編集窓がどんどん重くなっていった。こわすぎる