*571 JJOOII http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0571 百万文字の文字列を読み込んで文字列の中から Jがn個Oがn個Iがn個が連続して並んでいるという条件を満たす部分のうち最大長の文字列を探してその長さを返す問題。 各ＪOIの連続出現回数をjoiCountsに保存して後は一文字ずつ読み込みながらmodeを変化させていく状態遷移マシンで実装。 手前から読んでJJJ,,,OOO,,,III,,が条件を満たすなら数えるのを継続し満たさないならＪがでるまで数えるのをやめるだけである。 競技プログラムの問題は手前からリニアにデータを読んで一つのデータにつき一回の処理で終わりリニアに解を決定できる問題。 なんども複数のデータを照合して突き合わせないと終わらない問題に大別できる。 リニアな問題は簡単なのが多いけどこの問題は典型的なリニアな問題だった。 これ25分くらいで実装できたけど世間様だったらもっと早く実装するのかな。 俺４流プログラマだしよくわかんね。 #include<stdio.h> int main(){ int joiCounts[3],mode=0,ans=0; int c; while(c=getchar()){ if(c==-1||c=='\n')break; if(mode==0){ if(c=='J'){ joiCounts[0]=1; mode=1; } }else if(mode==1){ if(c=='J'){ joiCounts[0]++; }else if(c=='O'){ joiCounts[1]=1; mode=2; }else if(c=='I'){ mode=0; joiCounts[0]=0; } }else if(mode==2){ if(c=='O'){ joiCounts[1]++; if(joiCounts[1]>joiCounts[0]){ mode=0; } }else if(c=='J'){ mode=1; joiCounts[0]=1; }else if(c=='I'){ joiCounts[2]=1; mode=3; if(joiCounts[1]==1)ans=ans>1?ans:1; } }else if(mode==3){ if(c=='I'){ joiCounts[2]++; if(joiCounts[2]==joiCounts[1]){ ans=ans>joiCounts[2]?ans:joiCounts[2]; }else if(joiCounts[2]>joiCounts[1]){ mode=0; } }else if(c=='J'){ mode=1; joiCounts[0]=1; }else if(c=='O'){ mode=0; } } } printf("%d\n",ans); } *572 Card Game is Fun http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0572 単調増加数列の概念を応用して解く。 自由にカードを抜けるＡさんのカードをＢさんのカードと照合しながら動的計画法で解けばよい。 特に賢く解く部分もないが油断して2回も不合格を食らった問題。 私の場合油断してというパタンが多い。 #include<stdio.h> #include<string.h> #include <algorithm> int main(){ int cardsA[5001],cardsB[5001]; int a,b; int memo[5001]; memset(memo,0,sizeof(memo)); scanf("%d %d",&a,&b); for(int i=0;i<a;i++){ scanf("%d",&cardsA[i]); } for(int i=0;i<b;i++){ scanf("%d",&cardsB[i]); } for(int i=0;i<a;i++){ for(int j=b-1;j>0;j--){ if(cardsA[i]==cardsB[j]){ memo[j]=std::max(memo[j-1]+1,memo[j]); } } for(int j=0;j<b;j++){ if(cardsA[i]==cardsB[j]){ memo[j]=std::max(1,memo[j]); } } } int ans=0; for(int i=0;i<b;i++)ans=std::max(ans,memo[i]); printf("%d\n",ans); } *0573 Night Market http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0573 aとｂの書き間違いに気づかず不正回を2連続で食らった問題。 問題自体は制限付きの動的計画法で楽々である。 条件の説明がめんどくさい数式で書かれていて読みづらいので入力の解説だけを読んだ方がいい問題。 #include<stdio.h> #include<string.h> #include <algorithm> int main(){ int n,t,s,a,b; int memo[3001],ans=0; memset(memo,0,sizeof(memo)); scanf("%d %d %d",&n,&t,&s); for(int i=0;i<n;i++){ scanf("%d %d",&a,&b); for(int j=t;j>=0;j--){ int L=j+b; if(j<s && s<L) continue; if(L>t)continue; memo[L]=std::max(memo[L],memo[j]+a); ans=std::max(ans,memo[L]); } } printf("%d\n",ans); } *0574 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0574 釘の打ちつけられた板に輪ゴムが張られているので何個の釘が輪ゴムに囲まれているかを答える問題。 ２列ずつにわけての動的計画法でアセプト。 実装をシンプルにした分速度は出てない。 #include<stdio.h> #include<map> #include<algorithm> #include<string.h> struct P{ int a,b; bool operator<(const P& p)const{ if(b!=p.b)return b<p.b;//より左側にあり return a<p.a;//より上にあり } bool operator==(const P& p)const{ return a==p.a&&b==p.b; } }; int memo[2][5004]; std::map<P,int> points; std::map<P,int>::iterator it; int main(){ int n,m,x; scanf("%d %d",&n,&m); P p; for(int i=0;i<m;i++){ scanf("%d %d %d",&p.a,&p.b,&x); if(points.find(p)==points.end()||points[p]<x+1){ points[p]=x+1; } } memset(memo,0,sizeof(memo)); int c,ans=0; it=points.begin(); for(int i=1;i<=n;i++){ int now=(i+1)&1; int old=i&1; p.b=i; memo[now][i-1]=0; for(int j=i;j<=n;j++){ //0段目としてダミーデータ0を入れてある p.a=j; if(it!=points.end()&&(*it).first==p){ c=(*it).second; it++; }else{ c=0; } memo[now][j]=std::max(std::max(c,memo[old][j-1]-1),memo[now][j-1]-1);//斜め左上か斜め右上からの三角形の連続、もしくはこのマスで始まる新しい三角形のどれかで一番大きいのを選ぶ if(memo[now][j]!=0)ans++; } } printf("%d\n",ans); } *576 Homework http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0576 宿題の日数を計算する問題。 解法 一番簡単な部類の問題なので何も考えません。 #include<stdio.h> #include<iostream> int main(){ int L,a,b,c,d; std::cin>>L>>a>>b>>c>>d; a--; b--; std::cout<<(L-1-(a/c>b/d?a/c:b/d))<<"\n"; } *577 Unique number http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0577 簡単なゲームのスコアを求める問題。 解法 簡単な問題なので何も考えません。 #include<stdio.h> #include<string.h> int main(){ int n; int scores[201][3]; int memo[3][101]; memset(memo,0,sizeof(memo)); scanf("%d",&n); for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ scanf("%d",&scores[i][j]); memo[j][scores[i][j]]++; } } for(int i=0;i<n;i++){ int ans=0; for(int j=0;j<3;j++){ if(memo[j][scores[i][j]]==1)ans+=scores[i][j]; } printf("%d\n",ans); } } *0578 Signboard http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0578 看板の文字を上塗りして看板を再利用する問題。 解法 何も思いつかなかったので全探索しました。 賢い方法というのもあるかもしれません。 等間隔というのが結構難題です。 #include<stdio.h> #include<string.h> int main(){ int n,baseLen,ans=0; char name[30],old[110]; scanf("%d %s",&n,name); baseLen=strlen(name); for(int i=0;i<n;i++){ scanf("%s",old); int len=strlen(old); int add=0; for(int j=0;old[j]!='\0';j++){ if(add==1)break; for(int k=1;k<len;k++){ int count=0; for(int L=0;L*k+j<len;L++){ int p=L*k+j; if(name[count]!=old[p])break; count++; if(count>=baseLen)break; } if(count==baseLen)add=1; } } ans+=add; } printf("%d\n",ans); } *0579 Hot days http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0579 毎日の服を選ぶ問題。 解法 条件を満たす服だけで動的計画法を適用すれば解けます。 #include<stdio.h> #include<string.h> int main(){ int d,n,ts[201],as[201],bs[201],cs[201]; int memo[201][201]; scanf("%d %d",&d,&n); for(int i=0;i<d;i++){ scanf("%d",&ts[i]); } memset(memo,-1,sizeof(memo)); int t=ts[0]; for(int i=0;i<n;i++){ scanf("%d %d %d",&as[i],&bs[i],&cs[i]); if(as[i]<=t&&t<=bs[i]){ memo[0][i]=0; } } int ans=0; for(int i=1;i<d;i++){ int t=ts[i]; for(int j=0;j<n;j++){ //今日の服j if(t<as[j]||bs[j]<t)continue; int c1=cs[j]; for(int k=0;k<n;k++){ //前日の服k int base=memo[i-1][k]; if(base==-1)continue; int c2=cs[k]; int c3=base+(c2>c1?c2-c1:c1-c2); if(memo[i][j]<c3)memo[i][j]=c3; if(ans<c3)ans=c3; } } } printf("%d\n",ans); }
