解ける問題がなくて暇なのでコンテスト中ですがブログを書いています。
A - バリケード
呼吸。
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a,b,c;scanf("%d%d%d",&a,&b,&c); int ret=0; for(int i=0;i<a;i++){ int p;scanf("%d",&p); if(p<b||p>=c)ret++; }printf("%d\n",ret); }
B - 作問委員会
呼吸。
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a,b,c;scanf("%d%d%d",&a,&b,&c); int ret=0; for(int i=0;i<a;i++){ int p;scanf("%d",&p); if(p<b||p>=c)ret++; }printf("%d\n",ret); }
C - クッキー☆増殖装置
どうせこうでしょ
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int T;scanf("%d",&T); while(T--){ int a,b;scanf("%d%d",&a,&b); int ret=127*(a-1); if(a%2==0)ret+=127-b; else ret+=b; printf("%d\n",ret); } }
D - 長い黒板
一列ずつ増やしていく。
#include<stdio.h> #include<algorithm> using namespace std; char str[2][200]; char in[3]; int main(){ int a;scanf("%d",&a); int dir=0; for(int i=0;i<a;i++){ if(dir==0){ str[0][i+1]=str[1][i+1]=0; bool ok=false; for(int j=0;j<4;j++){ for(int k=0;k<2;k++){ if(j&(1<<k))str[k][i]='#'; else str[k][i]='.'; } printf("%s\n",str[0]); printf("%s\n",str[1]); fflush(stdout); scanf("%s",in); if(in[0]=='T'){ ok=true; break; } } if(!ok)dir=1; } if(dir){ for(int j=i-1;j>=0;j--){ str[0][j+1]=str[0][j]; str[1][j+1]=str[1][j]; } str[0][i+1]=str[1][i+1]=0; for(int j=0;j<4;j++){ for(int k=0;k<2;k++){ if(j&(1<<k))str[k][0]='#'; else str[k][0]='.'; } printf("%s\n",str[0]); printf("%s\n",str[1]); fflush(stdout); scanf("%s",in); if(in[0]=='T'){ // ok=true; break; } } } } printf("%s\n%s\n",str[0],str[1]); }
E - 柵
定番の思考放棄。
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int D_MAX_V=20002; const int D_v_size=20002; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0;} D_wolf(int t1,int c1,int r1){ t=t1;c=c1;r=r1; } }; vector<D_wolf>D_G[D_MAX_V]; int D_level[D_MAX_V]; int D_iter[D_MAX_V]; void add_edge(int from,int to,int cap){ D_G[from].push_back(D_wolf(to,cap,D_G[to].size())); D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1)); } void D_bfs(int s){ for(int i=0;i<D_v_size;i++)D_level[i]=-1; queue<int> Q; D_level[s]=0; Q.push(s); while(Q.size()){ int v=Q.front(); Q.pop(); for(int i=0;i<D_G[v].size();i++){ if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){ D_level[D_G[v][i].t]=D_level[v]+1; Q.push(D_G[v][i].t); } } } } int D_dfs(int v,int t,int f){ if(v==t)return f; for(;D_iter[v]<D_G[v].size();D_iter[v]++){ int i=D_iter[v]; if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){ int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c)); if(d>0){ D_G[v][i].c-=d; D_G[D_G[v][i].t][D_G[v][i].r].c+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; for(;;){ D_bfs(s); if(D_level[t]<0)return flow; for(int i=0;i<D_v_size;i++)D_iter[i]=0; int f; while((f=D_dfs(s,t,99999999))>0){flow+=f;} } return 0; } char str[200][200]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%s",str[i]); int T=9999; int B=-1000; int L=9999; int R=-9999; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(str[i][j]=='X'){ T=min(T,i); B=max(B,i); L=min(L,j); R=max(R,j); } } if(T==0||B==a-1||L==0||R==b-1){ printf("-1\n");return 0; } int s=2*a*b; int t=2*a*b+1; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(str[i][j]=='X')add_edge(s,(i*b+j)*2+1,99999999); else add_edge((i*b+j)*2,(i*b+j)*2+1,1); if(i)add_edge((i*b+j)*2+1,(i*b+j-b)*2,99999999); else add_edge((i*b+j)*2+1,t,99999999); if(i<a-1)add_edge((i*b+j)*2+1,(i*b+j+b)*2,99999999); else add_edge((i*b+j)*2+1,t,99999999); if(j)add_edge((i*b+j)*2+1,(i*b+j-1)*2,99999999); else add_edge((i*b+j)*2+1,t,99999999); if(j<b-1)add_edge((i*b+j)*2+1,(i*b+j+1)*2,99999999); else add_edge((i*b+j)*2+1,t,99999999); } printf("%d\n",max_flow(s,t)); }
F - 早解き
慎重に条件をいろいろ持ちながら前から構文解析していく。
慎重さが難しいですね〜。
#include<stdio.h> #include<algorithm> using namespace std; char in[1100]; int at=0; pair<int,int>expr(int a,int b); pair<int,int>term(int a,int b){ if('0'<=in[at]&&in[at]<='9'){ if(in[at]=='0'){ at++; return make_pair(0,at-1); } pair<int,int>ret=make_pair(-2,0); if(in[at]-'0'>b){ ret=make_pair(b+1,at); } if((a>(in[at]-'0')*10+9)){ ret=make_pair(a-1,at); } int v=0; while('0'<=in[at]&&in[at]<='9'){ v*=10;v+=in[at]-'0'; at++; } if(ret.first==-2){ if(v>=10)ret=make_pair(v,at-1); else ret=make_pair(v,at); } return ret; }else{ return expr(a,b); } } pair<int,int>expr(int a,int b){ //printf("%d %d %d\n",at,a,b); if(in[at]!='^'&&in[at]!='_'){ return term(0,99); } int z=0; if(in[at]=='^'){ z=1; } at+=2; pair<int,int> tmp=term(a,b); pair<int,int>ret=make_pair(-2,-2); if(z==0&&tmp.first==0)ret=tmp; if(z==1&&tmp.first==99)ret=tmp; if(tmp.first!=-1&&z==0&&a>tmp.first)ret=tmp; if(tmp.first!=-1&&z==1&&b<tmp.first)ret=tmp; at++; int L=a;int R=b; if(z==0){if(tmp.first!=-1)R=min(R,tmp.first-1);} else {if(tmp.first!=-1)L=max(L,tmp.first+1);} pair<int,int> tmp2=term(L,R); if(tmp.first==-1&&z==0)tmp.first=110; if(tmp2.first==-1&&z==0)tmp2.first=110; if(ret.first==-2){ if(z==0)ret.first=min(tmp.first,tmp2.first); else ret.first=max(tmp.first,tmp2.first); ret.second=tmp2.second; } at++; return ret; } int main(){ int a;scanf("%d",&a); while(a--){ scanf("%s",in); at=0; pair<int,int> ret=expr(0,99); printf("%d %d\n",ret.first,ret.second+1); } }
G - 試験
Dilworthから察するにどうせ同じ長さの部分文字列の種類数の最大を答えればいいと思う
最近のコンパイラだと "rank" で落ちる？
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char c[110000]; int n; int sa_k; int Rank[110000]; int tmp[110000]; int sa[110000]; int lcp[110000]; bool compare_sa(int i,int j){ if(Rank[i]!=Rank[j])return Rank[i]<Rank[j]; else{ int ri=i+sa_k<=n?Rank[i+sa_k]:-1; int rj=j+sa_k<=n?Rank[j+sa_k]:-1; return ri<rj; } } void construct_sa(){ for(int i=0;i<=n;i++){ sa[i]=i; Rank[i]=i<n?c[i]:-1; } for(sa_k=1;sa_k<=n;sa_k*=2){ sort(sa,sa+n+1,compare_sa); tmp[sa[0]]=0; for(int i=1;i<=n;i++){ tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0); } for(int i=0;i<=n;i++){ Rank[i]=tmp[i]; } } } void construct_lcp(){ for(int i=0;i<=n;i++)Rank[sa[i]]=i; int h=0; lcp[0]=0; for(int i=0;i<n;i++){ int j=sa[Rank[i]-1]; if(h>0)h--; for(;j+h<n&&i+h<n;h++){ if(c[j+h]!=c[i+h])break; } lcp[Rank[i]-1]=h; } } int hd[110000]; int main(){ scanf("%s",c); n=strlen(c); construct_sa(); construct_lcp(); int ret=0; for(int i=0;i<n;i++)hd[lcp[i]]++; int cnt=0; for(int i=n;i>0;i--){ cnt++; cnt-=hd[i]; ret=max(ret,cnt); } printf("%d\n",ret); }
H - 壁壁壁壁壁壁壁
60点までは問題文にある通りにMCF。満点はどうせMCFのよくあるアルゴリズムの代わりにsegtreeで高速に見ていくんだと思う。
I - ティッシュ配り
Cの値はほぼ意味がないので、1だと思うことにすると、人iが残りj時間で何人に増え、合計いくつ処理できるか、みたいな感じのものを求めていくことになる。 人iの種類は高々 O(√N)。
10^7.5 定数倍改善。普通に後ろからDPしていくだけ。全部のテーブルを持っておくとTLEするし、直前だけ持ってても情報が足りないが、そこはまあ人iについてはi個前まで持っておくとかすればメモリ使用量は合計 O(N)になるわけで。
速度が足りないので途中から450個全部見ないようにして920ms/1000ms で無理やり通した。さすがに想定解ではないと思う。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; long long mod=1000000007; int N[110000]; int C[110000]; pair<int,int>p[110000]; long long ans[110000]; vector<int> dp1[450]; vector<int> dp2[450]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d%d",N+i,C+i); p[i]=make_pair(N[i]/C[i],i); } std::sort(p,p+a); for(int i=0;i<450;i++){ dp1[i]=vector<int>(i+1,0); dp2[i]=vector<int>(i+1,0); dp2[i][0]=1; } int at=0; for(int i=1;i<100010;i++){ int M=450; if(i>50000)M=330; for(int j=0;j<M;j++){ int tk=2*(j+1); int v=i%(j+1); if(j<449&&tk<=i){ dp1[j][v]=(dp1[j][v]+dp1[j+1][(i-tk/2)%(j+2)]); if(dp1[j][v]>=mod)dp1[j][v]-=mod; dp2[j][v]=(dp2[j][v]+dp2[j+1][(i-tk/2)%(j+2)]); if(dp2[j][v]>=mod)dp2[j][v]-=mod; }else{ dp1[j][v]=i; dp2[j][v]=1; } } while(at<a&&p[at].first==0)at++; while(at<a&&p[at].first==i){ // printf("%d: %lld %lld\n",p[at].second,dp1[0][0],dp2[0][0]); ans[p[at].second]=((long long)C[p[at].second]*dp1[0][0]+(long long)(N[p[at].second]%C[p[at].second])*dp2[0][0])%mod; at++; } } for(int i=0;i<a;i++)if(N[i]/C[i]==0)ans[i]=N[i]; for(int i=0;i<a;i++)printf("%lld\n",ans[i]); }
まとめ
典型実装重視型には解きやすいセット。
