いつもと同じ死に方。成長が見られない。相変わらず注意力が灰底辺。
A | B | C | D | E | Place |
---|---|---|---|---|---|
00:48 (+1) | 00:35 (+4) | 01:59 (+1) | - | - | 59th |
A:
メモ化再帰するだけ。メモ化し忘れて1TLE。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; char in[11000]; int dp[11000][3]; set<string>S; char tmp[4]; int n; int solve(int a,int b){ if(~dp[a][b])return dp[a][b]; if(a==n)return dp[a][b]=1; int t=0; if(a<=n-2){ if(b!=0||in[a]!=in[a-2]||in[a+1]!=in[a-1]){ int res=solve(a+2,0); if(res){ t=res; tmp[2]=0;tmp[0]=in[a];tmp[1]=in[a+1];string tt=tmp;S.insert(tt); } } } if(a<=n-3){ if(b!=1||in[a]!=in[a-3]||in[a+1]!=in[a-2]||in[a+2]!=in[a-1]){ int res=solve(a+3,1); if(res){ t=res; tmp[3]=0;tmp[0]=in[a];tmp[1]=in[a+1];tmp[2]=in[a+2];string tt=tmp;S.insert(tt); } } } return dp[a][b]=t; } int main(){ scanf("%s",in); n=strlen(in); for(int i=0;i<11000;i++)for(int j=0;j<3;j++) dp[i][j]=-1; for(int i=5;i<=n;i++){ solve(i,2); } printf("%d\n",(int)(S.size())); for(set<string>::iterator it=S.begin();it!=S.end();it++)printf("%s\n",(*it).c_str()); }
B:
なにも変な要素がないのにひたすらWA。頭が悪すぎる。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; vector<int>g[3100]; int dist[3100][3100]; int L[3100][3]; int R[3100][3]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ int p,q;scanf("%d%d",&p,&q);p--;q--; g[p].push_back(q); } for(int i=0;i<a;i++){ for(int j=0;j<a;j++)dist[i][j]=-1; queue<int>Q; Q.push(i); dist[i][i]=0; while(Q.size()){ int at=Q.front();Q.pop(); for(int j=0;j<g[at].size();j++){ int to=g[at][j]; if(dist[i][to]==-1){ dist[i][to]=dist[i][at]+1; Q.push(to); } } } } for(int i=0;i<a;i++){ L[i][0]=L[i][1]=L[i][2]=-1; for(int j=0;j<a;j++){ if(i==j)continue; if(dist[j][i]==-1)continue; if(L[i][0]==-1||dist[j][i]>dist[L[i][0]][i]){ L[i][2]=L[i][1]; L[i][1]=L[i][0]; L[i][0]=j; }else if(L[i][1]==-1||dist[j][i]>dist[L[i][1]][i]){ L[i][2]=L[i][1]; L[i][1]=j; }else if(L[i][2]==-1||dist[j][i]>dist[L[i][2]][i]){ L[i][2]=j; } } } for(int i=0;i<a;i++){ R[i][0]=R[i][1]=R[i][2]=-1; for(int j=0;j<a;j++){ if(i==j)continue; if(dist[i][j]==-1)continue; if(R[i][0]==-1||dist[i][j]>dist[i][R[i][0]]){ R[i][2]=R[i][1]; R[i][1]=R[i][0]; R[i][0]=j; }else if(R[i][1]==-1||dist[i][j]>dist[i][R[i][1]]){ R[i][2]=R[i][1]; R[i][1]=j; }else if(R[i][2]==-1||dist[i][j]>dist[i][R[i][2]]){ R[i][2]=j; } } } int A,B,C,D; int bs=0; for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ for(int k=0;k<3;k++)for(int l=0;l<3;l++){ if(L[i][k]==-1||R[j][l]==-1||dist[i][j]==-1)continue; if(i==j||i==R[j][l]||j==L[i][k]||L[i][k]==R[j][l])continue; if(bs<dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]]){ bs=dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]]; A=L[i][k];B=i;C=j;D=R[j][l]; } } } } set<int>S; S.insert(A); S.insert(B); S.insert(C); S.insert(D); if(S.size()!=4){ while(1); } printf("%d %d %d %d\n",A+1,B+1,C+1,D+1); }
C:
nCkテーブルをsqrt(N)段ごとに作っておいて一行ずつ下がるやつに係数をつけただけ。一箇所-1し忘れ。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; char in[110000]; int n; int sz=0; pair<pair<int,int>,int>p[110000]; int ans[110000]; int SQ=300; long long fact[110000]; long long inv[110000]; long long finv[110000]; long long C(int a,int b){ return fact[a]*finv[b]%mod*finv[a-b]%mod; } long long val[110000]; long long sum[110000]; long long p26[110000]; long long p25[110000]; int main(){ fact[0]=finv[0]=1; p26[0]=1; p25[0]=1; inv[1]=1; for(int i=2;i<110000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod; for(int i=1;i<110000;i++){ fact[i]=fact[i-1]*i%mod; finv[i]=finv[i-1]*inv[i]%mod; p26[i]=p26[i-1]*26%mod; p25[i]=p25[i-1]*25%mod; } int a;scanf("%d",&a); scanf("%s",in); n=strlen(in); while(a--){ int t;scanf("%d",&t); if(t==1){ scanf("%s",in); n=strlen(in); }else{ int b;scanf("%d",&b); p[sz]=make_pair(make_pair(b,n),sz); sz++; } } std::sort(p,p+sz); int at=0; for(int i=0;i<340;i++){ long long ks=1; for(int j=i*SQ;j>=0;j--){ val[j]=C(i*SQ,j)*ks; ks=ks*25%mod; } for(int j=0;j<=i*SQ;j++){ sum[j]=val[j]; if(j)sum[j]=(sum[j]+sum[j-1])%mod; } while(at<sz&&p[at].first.first<(i+1)*SQ){ if(p[at].first.first<p[at].first.second){ at++;continue; } long long now=sum[min(i*SQ,p[at].first.second-1)]; int r=min(i*SQ,p[at].first.second-1); for(int j=0;j<p[at].first.first%SQ;j++){ if(r==p[at].first.second-1){ now=now*26%mod; now=(now+mod-C(i*SQ+j,r)*p25[i*SQ+j-r]%mod)%mod; }else{ now=now*26%mod; r++; } } ans[p[at].second]=(p26[p[at].first.first]+mod-now)%mod; at++; } } for(int i=0;i<sz;i++)printf("%d\n",ans[i]); }