AOJ 2372,2361,2356,2386,2241,1250,1181,2340,2243,2232,2175,1316
4日間で気がついたら結構解いていました。
2372
紙に書いて法則を発見するとか。フィボナッチ数列で行列累乗もするし、いろいろと面倒な問題。
#include<stdio.h> #include<algorithm> using namespace std; long long mat[2][2]; long long now[2][2]; long long tmp[2][2]; int mod=1000000007; long long fib(long long a){ now[0][0]=now[1][0]=now[0][1]=1; now[1][1]=0; mat[0][0]=mat[1][1]=1; mat[0][1]=mat[1][0]=0; while(a){ if(a%2){ tmp[0][0]=now[0][0]*mat[0][0]+now[0][1]*mat[1][0]; tmp[0][1]=now[0][0]*mat[0][1]+now[0][1]*mat[1][1]; tmp[1][0]=now[1][0]*mat[0][0]+now[1][1]*mat[1][0]; tmp[1][1]=now[1][0]*mat[0][1]+now[1][1]*mat[1][1]; mat[0][0]=tmp[0][0]%mod;mat[0][1]=tmp[0][1]%mod;mat[1][0]=tmp[1][0]%mod;mat[1][1]=tmp[1][1]%mod; } tmp[0][0]=now[0][0]*now[0][0]+now[0][1]*now[1][0]; tmp[0][1]=now[0][0]*now[0][1]+now[0][1]*now[1][1]; tmp[1][0]=now[1][0]*now[0][0]+now[1][1]*now[1][0]; tmp[1][1]=now[1][0]*now[0][1]+now[1][1]*now[1][1]; now[0][0]=tmp[0][0]%mod;now[0][1]=tmp[0][1]%mod;now[1][0]=tmp[1][0]%mod;now[1][1]=tmp[1][1]%mod; a/=2; } //printf("%lld\n",mat[0][0]); return mat[0][0]; } int main(){ long long a; scanf("%lld",&a); long long left=0; long long right=2100000000LL; while(left+1<right){ long long M=(left+right)/2; long long t=(M-1)/2*((M-1)/2+1); if(M%2==0)t+=M/2; //printf("%lld %lld\n",M,t); if(t>=a){ right=M; }else{ left=M; } } long long t=(left-1)/2*((left-1)/2+1); if(left%2==0)t+=left/2; long long v=a-t; //printf("%lld %lld\n",left,v); if(v<=(right/2+1)/2){ long long p=v*2-1; long long q=right-p; // printf("%lld %lld\n",p,q); printf("%d\n",fib(p)*fib(q)%mod); }else{ long long p=(right/2-v+1)*2; long long q=right-p; // printf("%lld %lld\n",p,q); printf("%d\n",fib(p)*fib(q)%mod); } }
2361
8!頂点でDijkstraしても十分間に合う。
#include<stdio.h> #include<algorithm> #include<map> #include<queue> using namespace std; int c[8][8]; struct wolf{ int v[8]; }; inline bool operator<(const wolf&a,const wolf&b){ for(int i=0;i<8;i++)if(a.v[i]!=b.v[i])return a.v[i]<b.v[i]; return false; } map<wolf,int>ijk; priority_queue<pair<int,wolf> > Q; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++) for(int j=0;j<a;j++) scanf("%d",&c[i][j]); wolf s; for(int i=0;i<a;i++)s.v[i]=i; Q.push(make_pair(0,s)); int ret=0; while(Q.size()){ int cost=-Q.top().first; wolf now=Q.top().second; Q.pop(); if(ijk.count(now))continue; ijk[now]=cost; ret=max(ret,cost); for(int i=0;i<a;i++) for(int j=i+1;j<a;j++){ int w=now.v[i]; now.v[i]=now.v[j]; now.v[j]=w; if(!ijk.count(now)){ Q.push(make_pair(-cost-c[i][j],now)); } w=now.v[i]; now.v[i]=now.v[j]; now.v[j]=w; } } printf("%d\n",ret); }
2356
左右対称なので半分だけ見る。まず奇数回使われる文字が2つ以上あったら作れない。他の場合は2で割ってから組み合わせ計算。
#include<stdio.h> int d[26]; char str[42]; int main(){ scanf("%s",str); for(int i=0;str[i];i++)d[str[i]-'a']++; int v=0; for(int i=0;i<26;i++)if(d[i]%2)v++; if(v>1)printf("0\n"); else{ int n=0; for(int i=0;i<26;i++){ d[i]/=2; n+=d[i]; } long long ret=1; for(int i=0;i<n;i++)ret*=i+1; for(int i=0;i<26;i++){ //long long val=1; for(int j=1;j<=d[i];j++)ret/=j; } printf("%lld\n",ret); } }
2386
実は、完全グラフなら向きをどのように限定してもハミルトン閉路があります(未証明)
#include<stdio.h> #include<algorithm> using namespace std; int d[1000][1000]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++) for(int j=0;j<a;j++) scanf("%d",&d[i][j]); long long ret=0; for(int i=0;i<a;i++) for(int j=i+1;j<a;j++) ret+=min(d[i][j],d[j][i]); printf("%lld\n",ret); }
2241
シミュレーションをするだけ。n=1に注意。
#include<stdio.h> #include<algorithm> using namespace std; pair<int,int> unagi[1000000]; pair<int,int> wolf[1000000]; int u_row[500]; int u_col[500]; int w_row[500]; int w_col[500]; int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); for(int i=0;i<1000000;i++){ unagi[i]=make_pair(-1,-1); wolf[i]=make_pair(-1,-1); } for(int i=0;i<a;i++) for(int j=0;j<a;j++){ int p; scanf("%d",&p); unagi[p-1]=make_pair(i,j); } for(int i=0;i<a;i++) for(int j=0;j<a;j++){ int p; scanf("%d",&p); wolf[p-1]=make_pair(i,j); } int UL=0; int UR=0; int WL=0; int WR=0; int u=0;int w=0; if(a==1){ for(int i=0;i<d;i++){ int e; scanf("%d",&e);e--; if(~unagi[e].first)u++; if(~wolf[e].first)w++; if(u>=b&&w>=c){ printf("DRAW\n"); return 0; } if(u>=b){ printf("USAGI\n"); return 0; } if(w>=c){ printf("NEKO\n"); return 0; } } printf("DRAW\n"); return 0; } for(int i=0;i<d;i++){ int e; scanf("%d",&e);e--; if(~unagi[e].first){ u_row[unagi[e].first]++; if(u_row[unagi[e].first]==a)u++; u_col[unagi[e].second]++; if(u_col[unagi[e].second]==a)u++; if(unagi[e].first==unagi[e].second){ UL++; if(UL==a)u++; } if(unagi[e].first+unagi[e].second==a-1){ UR++; if(UR==a)u++; } } if(~wolf[e].first){ w_row[wolf[e].first]++; if(w_row[wolf[e].first]==a)w++; w_col[wolf[e].second]++; if(w_col[wolf[e].second]==a)w++; if(wolf[e].first==wolf[e].second){ WL++; if(WL==a)w++; } if(wolf[e].first+wolf[e].second==a-1){ WR++; if(WR==a)w++; } } if(u>=b&&w>=c){ printf("DRAW\n"); return 0; } if(u>=b){ printf("USAGI\n"); return 0; } if(w>=c){ printf("NEKO\n"); return 0; } } printf("DRAW\n"); }
1250
下位ビットから決めていく。繰り上がりとかが面倒なのでこれは別の変数にもっておくとよい。
#include<stdio.h> #include<algorithm> typedef unsigned int wolf; char set[]="0123456789abcdef"; wolf b[9]; char str[9]; char out[9]; int main(){ int a; scanf("%d",&a); while(a--){ for(int i=0;i<9;i++)b[i]=0; for(int i=0;i<9;i++){ scanf("%s",str); for(int j=0;str[j];j++){ b[i]*=16; for(int k=0;k<16;k++)if(set[k]==str[j])b[i]+=k; } } wolf ans=0; //int c=0; int d=0; for(int i=0;i<32;i++){ int c=0; //int d=0; for(int j=0;j<8;j++){ if(b[j]&(1<<i))c++; } int e=0; if(b[8]&(1<<i))e++; if((c+d+e)%2){ ans+=(1<<i); d=(8-c+d)/2; } else d=(c+d)/2; } int now=0; if(ans==0){ printf("0\n"); continue; } while(ans){ out[now++]=set[ans%16]; ans/=16; } for(int i=now-1;i>=0;i--)printf("%c",out[i]); printf("\n"); } }
1181
シミュレーションするだけ。ポインタ分かりません(大嘘)
#include<stdio.h> #include<algorithm> using namespace std; int h[100][100]; int t[100][100]; int c[6][4]={{4,2,3,5},{1,3,6,4},{5,6,2,1},{6,2,1,5},{3,6,4,1},{5,4,2,3}}; int d[6][4]={{5,4,2,3},{3,6,4,1},{6,2,1,5},{5,6,2,1},{1,3,6,4},{4,2,3,5}}; struct dice{ int U,D,F,B,L,R; dice(int a,int b){ U=a; F=b; D=7-a; B=7-b; for(int i=0;i<6;i++) for(int j=0;j<4;j++)if(a==c[i][j]&&b==d[i][j])L=i+1; R=7-L; } }; void N(dice &a){ int q=a.U;a.U=a.F;a.F=a.D;a.D=a.B;a.B=q; } void E(dice &a){ int q=a.U;a.U=a.L;a.L=a.D;a.D=a.R;a.R=q; } void W(dice &a){ int q=a.U;a.U=a.R;a.R=a.D;a.D=a.L;a.L=q; } void S(dice &a){ int q=a.U;a.U=a.B;a.B=a.D;a.D=a.F;a.F=q; } int main(){ int a; while(scanf("%d",&a),a){ for(int i=0;i<100;i++) for(int j=0;j<100;j++) h[i][j]=t[i][j]=0; for(int i=0;i<a;i++){ int x,y; scanf("%d%d",&x,&y); dice s=dice(x,y); int row=50; int col=50; bool ok=false; do{ ok=false; for(int j=6;j>=4&&!ok;j--){ if(h[row][col]>h[row-1][col]&&s.B==j){ row--; N(s); ok=true; }else if(h[row][col]>h[row+1][col]&&s.F==j){ row++; S(s);ok=true; }else if(h[row][col]>h[row][col-1]&&s.L==j){ col--; W(s);ok=true; }else if(h[row][col]>h[row][col+1]&&s.R==j){ col++; E(s);ok=true; } } }while(ok); h[row][col]++; t[row][col]=s.U; } for(int i=1;i<=6;i++){ int ret=0; for(int j=0;j<100;j++) for(int k=0;k<100;k++)if(t[j][k]==i)ret++; printf("%d",ret); if(i<6)printf(" "); else printf("\n"); } } }
2340
個数が一致していれば必ず作れる。
#include<stdio.h> char str[2]; int main(){ int a; scanf("%d",&a); long long v=0; for(int i=0;i<a;i++){ int b,c; scanf("%d%s%d",&b,str,&c); if(str[0]=='(')v+=c; else v-=c; if(v==0)printf("Yes\n"); else printf("No\n"); } }
2243
譜面の場所と足のcol座標2つと最後に使った足でDP
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; char str[100001]; int v[100000]; int dp[100001][3][3][2]; int main(){ while(1){ scanf("%s",str); if(str[0]=='#')return 0; int len=strlen(str); if(len<=2){ printf("0\n"); continue; } for(int i=0;i<len;i++)v[i]=str[i]-'0'; for(int i=0;i<=len;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) dp[i][j][k][0]=dp[i][j][k][1]=99999999; for(int i=0;i<3;i++) for(int j=i;j<3;j++) dp[0][i][j][0]=dp[0][i][j][1]=0; for(int i=0;i<len;i++){ for(int j=0;j<3;j++){ for(int k=j;k<3;k++){ if((v[i]+2)%3<j){ dp[i+1][(v[i]+2)%3][k][0]=min(dp[i+1][(v[i]+2)%3][k][0],min(dp[i][j][k][0]+1,dp[i][j][k][1])); } else if((v[i]+2)%3>k){ dp[i+1][j][(v[i]+2)%3][1]=min(dp[i+1][j][(v[i]+2)%3][1],min(dp[i][j][k][0],dp[i][j][k][1]+1)); }else{ dp[i+1][(v[i]+2)%3][k][0]=min(dp[i+1][(v[i]+2)%3][k][0],min(dp[i][j][k][0]+1,dp[i][j][k][1])); dp[i+1][j][(v[i]+2)%3][1]=min(dp[i+1][j][(v[i]+2)%3][1],min(dp[i][j][k][0],dp[i][j][k][1]+1)); } } } } int ret=9999999; for(int i=0;i<3;i++) for(int j=0;j<3;j++) ret=min(ret,min(dp[len][i][j][0],dp[len][i][j][1])); printf("%d\n",ret); } }
2232
要はパネルでポン。面倒なシミュレーション。はぁ～。パネポンガチ勢だったので変なケース見つけられたのが幸いだが…
#include<stdio.h> #include<algorithm> using namespace std; char str[30][31]; char val[30][31]; bool kie[30][31]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++)scanf("%s",str[i]); for(int i=0;i<a;i++){ for(int j=0;j<b-1;j++){ if(str[i][j]=='.'&&str[i][j+1]=='.')continue; for(int k=0;k<a;k++) for(int l=0;l<b;l++){ val[k][l]=str[k][l]; } char S=val[i][j]; val[i][j]=val[i][j+1]; val[i][j+1]=S; bool ok=true; //bool ze=true; for(int k=0;k<b;k++){ int V=a-1; for(int l=a-1;l>=0;l--){ if(val[l][k]!='.')val[V--][k]=val[l][k]; } for(int l=V;l>=0;l--)val[l][k]='.'; } do{ //ze=ok; for(int k=0;k<a;k++) for(int l=0;l<b;l++) kie[k][l]=false; ok=false; for(int k=0;k<a;k++){ char now=val[k][0]; int ren=val[k][0]!='.'?1:0; for(int l=1;l<b;l++){ if(val[k][l]=='.'){ if(ren>=c){ for(int m=l-ren;m<l;m++)kie[k][m]=true; } now=val[k][l]; ren=0; }else{ if(val[k][l]!=now){ now=val[k][l]; if(ren>=c){ for(int m=l-ren;m<l;m++)kie[k][m]=true; } ren=1; }else ren++; } } if(ren>=c){ for(int m=b-ren;m<b;m++)kie[k][m]=true; } } for(int k=0;k<b;k++){ char now=val[0][k]; int ren=val[0][k]!='.'?1:0; for(int l=1;l<a;l++){ if(val[l][k]=='.'){ if(ren>=c){ for(int m=l-ren;m<l;m++)kie[m][k]=true; } now=val[l][k]; ren=0; }else{ if(val[l][k]!=now){ now=val[l][k]; if(ren>=c){ for(int m=l-ren;m<l;m++)kie[m][k]=true; } ren=1; }else ren++; } } if(ren>=c){ for(int m=a-ren;m<a;m++)kie[m][k]=true; } } for(int k=0;k<a;k++) for(int l=0;l<b;l++) if(kie[k][l]){ val[k][l]='.'; ok=true; } for(int k=0;k<b;k++){ int V=a-1; for(int l=a-1;l>=0;l--){ if(val[l][k]!='.')val[V--][k]=val[l][k]; } for(int l=V;l>=0;l--)val[l][k]='.'; } // for(int k=0;k<a;k++) // printf("%s\n",val[k]); }while(ok); ok=true; for(int k=0;k<a;k++) for(int l=0;l<b;l++) if(val[k][l]!='.')ok=false; if(ok){ printf("YES\n"); return 0; } } } printf("NO\n"); }
2175
変なルールがないので楽なシミュレーション
#include<stdio.h> char str[13][4][3]; int num[13][4]; char pro[2]; int main(){ while(1){ scanf("%s",pro); if(pro[0]=='#')return 0; for(int i=0;i<4;i++) for(int j=0;j<13;j++) scanf("%s",str[j][i]); for(int i=0;i<13;i++) for(int j=0;j<4;j++){ if(str[i][j][0]=='A')num[i][j]=14; else if(str[i][j][0]=='K')num[i][j]=13; else if(str[i][j][0]=='Q')num[i][j]=12; else if(str[i][j][0]=='J')num[i][j]=11; else if(str[i][j][0]=='T')num[i][j]=10; else num[i][j]=str[i][j][0]-'0'; if(str[i][j][1]==pro[0])num[i][j]+=40; } int ns=0; int ew=0; int at=0; for(int i=0;i<13;i++){ char c=str[i][at][1]; int n=at; int p=num[i][at]; for(int j=1;j<4;j++){ if((c==str[i][(at+j)%4][1]||num[i][(at+j)%4]>40)){ if(p<num[i][(at+j)%4]){ p=num[i][(at+j)%4]; n=(at+j)%4; } } } if(n%2)ew++; else ns++; at=n; } if(ew>6)printf("EW %d\n",ew-6); else printf("NS %d\n",ns-6); } }
1316
全探索
#include<string> #include<vector> #include<algorithm> #include<stdio.h> using namespace std; char str[10][21]; int dx[]={1,1,1,0,0,-1,-1,-1}; int dy[]={1,0,-1,1,-1,1,0,-1}; vector<string> V; int main(){ int a,b; while(scanf("%d%d",&a,&b),a){ V.clear(); for(int i=0;i<a;i++)scanf("%s",str[i]); for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ for(int k=0;k<8;k++){ int row=i; int col=j; string S=""; do{ S+=str[row][col]; row+=dx[k]; col+=dy[k]; if(row<0)row+=a; if(row>=a)row-=a; if(col<0)col+=b; if(col>=b)col-=b; }while(row!=i||col!=j); V.push_back(S); } } } std::sort(V.begin(),V.end()); int len=0; int m=0; for(int i=0;i<V.size()-1;i++){ int P=0; for(int j=0;j<min(V[i].size(),V[i+1].size());j++){ if(V[i][j]!=V[i+1][j])break; P++; } if(P>len){ len=P; m=i; } } if(len<2)printf("0\n"); else{ for(int i=0;i<len;i++)printf("%c",V[m][i]); printf("\n"); } } }
難易度表250が埋まりました。
さすがに250はシミュレーションだらけでつまらないので、もっと高い点数も埋めていきます。
