読者です 読者をやめる 読者になる 読者になる

AOJ Volume 0 (0020-0039)

はい。
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?volumeNo=0

0020: Capitalize

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    int n,m;
    char s[210];
    fgets(s,210,stdin);
    int len=strlen(s);
    for (int i=0;i<len;i++) {
        if (islower(s[i])) {
            s[i]=toupper(s[i]);
        }
    }
    printf("%s",s);
    return 0;
}

fgetsで一行まるごと空白区切りも改行コードもコミでchar s[210]で受け取ってislower()で小文字判定になったものだけをtoupper()で置換する。

0021: Parallelism

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        double x1,y1,x2,y2,x3,y3,x4,y4;
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
        if (abs((y3-y4)*(x1-x2)-(y1-y2)*(x3-x4))<1e-10) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

線分AB,CDの傾きを比較すればと思ったけどちょっと違うらしい。

0022: Maximum Sum Sequence

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    int n;
    int ans;
    for (;;) {
        scanf("%d",&n);
        if (n!=0) {
            vector<int> p(n);
            for (auto&e:p) {
                scanf("%d",&e);
            }
            ans=p[0];
            for (int i=0;i<n;i++) {
                int tmp=0;
                for (int j=i;j<n;j++) {
                    tmp+=p[j];
                    ans=max(ans,tmp);
                }
            }
        } else {
            break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

開始位置を1ずつずらしながら末尾までの和を常に比較して最大値を保存して全部調べる。

0023: Circles Intersection

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    int n;
    int ans;
    double xa,ya,ra,xb,yb,rb;
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        scanf("%lf %lf %lf %lf %lf %lf",&xa,&ya,&ra,&xb,&yb,&rb);
        double tmp=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
        if ((tmp+rb)<ra) {
            printf("2\n");
        } else if ((tmp+ra)<rb) {
            printf("-2\n");
        } else if ((tmp)>(ra+rb)) {
            printf("0\n");
        } else {
            printf("1\n");
        }
    }
    return 0;
}

2点間の距離を調べておく。 2点の距離+Bの半径よりもAの半径が大きければAの中にBが入っている状態。A,B入れ替えるとBの中にAが入っている状態。Aの半径とBの半径の和よりも2点の距離が大きければ重なっていない状態。それ以外が交わっている状態。多分、円の中に入って接している?状態は交わっている状態判定に含むっぽい。

0024: Physical Experiments

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    double v;
    while (scanf("%lf",&v)!=EOF) {
        double t=v/9.8;
        double y=t*t*4.9;
        int tmp;
        for (int j=0;;j++) {
            if ((j*5-5)*1.0>=y) {
                tmp=j;
                break;
            }
        }
        printf("%d\n",tmp);
    }
    return 0;
}

写経した。

0025: Hit and Blow

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    int a[4],b[4];
    while (scanf("%d %d %d %d",&a[0],&a[1],&a[2],&a[3])!=EOF) {
        scanf("%d %d %d %d",&b[0],&b[1],&b[2],&b[3]);
        int h=0,l=0;
        for (int i=0;i<4;i++) {
            for (int j=0;j<4;j++) {
                if (i!=j && a[i]==b[j]) {
                    l+=1;
                } else if (a[i]==b[j]) {
                    h+=1;
                }
            }
        }
        printf("%d %d\n",h,l);
    }
    return 0;
}

全部調べる。

0026: Dropping Ink

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    int a[10][10];
    for (int i=0;i<10;i++) {
        for (int j=0;j<10;j++) {
            a[i][j]=0;
        }
    }
    int x,y,s;
    int ans[2]={100,0};
    while (scanf("%d,%d,%d",&x,&y,&s)!=EOF) {
        a[y][x]+=1;
        if (y>0) a[y-1][x]+=1;
        if (x>0) a[y][x-1]+=1;
        if (y<9) a[y+1][x]+=1;
        if (x<9) a[y][x+1]+=1;

        if (s>=2) {
            if (y>0 && x>0) a[y-1][x-1]+=1;
            if (y>0 && x<9) a[y-1][x+1]+=1;
            if (y<9 && x>0) a[y+1][x-1]+=1;
            if (y<9 && x<9) a[y+1][x+1]+=1;
        }

        if (s==3) {
            if (y>1) a[y-2][x]+=1;
            if (x>1) a[y][x-2]+=1;
            if (y<8) a[y+2][x]+=1;
            if (x<8) a[y][x+2]+=1;
        }
    }

    for (int i=0;i<10;i++) {
        for (int j=0;j<10;j++) {
            if (a[i][j]!=0) {
                ans[0]-=1;
                ans[1]=max(ans[1],a[i][j]);
            }
        }
    }
    printf("%d\n%d\n",ans[0],ans[1]);
    return 0;
}

範囲外に気をつけてシミュレートする。

0027: What day is today?

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int m,d;
    int p[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
    map<int, string> week;
    week[0]="Monday";
    week[1]="Tuesday";
    week[2]="Wednesday";
    week[3]="Thursday";
    week[4]="Friday";
    week[5]="Saturday";
    week[6]="Sunday";
    for (;;){
        scanf("%d %d",&m,&d);
        if (m==0) break;
        int tmp=3;
        if (m>1) {
            for (int i=1;i<m;i++) {
                tmp=(tmp+p[i])%7;
            }
        }
        cout<<week[(tmp+d-1)%7]<<endl;
    }
    return 0;
}

月を超える時はその月が何日まであるかに合わせて計算。月内は1日から幾つズレるかで計算。

0028: Mode Value

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int n,tmp=0;
    int a[101]={0};
    while (scanf("%d",&n)!=EOF) {
        a[n]+=1;
        tmp=max(tmp,a[n]);
    }
    for (int i=1;i<101;i++) {
        if (a[i]==tmp) {
            printf("%d\n",i);
        }
    }
    return 0;
}

100個分の数列で出現回数をわかるようにして最頻値を調べる。

0029: English Sentence

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int mc=0,ml=0;
    map<string, int> m;
    string s,a,b;
    while(cin>>s){
        m[s]++;
        if (mc<m[s]) {
            mc=m[s];
            a=s;
        }
        if (ml<s.length()){
            ml=s.length();
            b=s;
        }

    }
    cout<<a<<" "<<b<<"\n";
    return 0;
}

文字列の扱い方難しい。

0030: Sum of Integers

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int n,s,ans;
    int dp[11][101]={0};
    dp[0][0]=1;
    for (int i=0;i<10;++i) {
        for (int j=i;j>=0;--j) {
            for (int k=0;k+i<=100;++k) {
                dp[j+1][k+i]+=dp[j][k];
            }
        }
    }
    for (;;) {
        scanf("%d %d",&n,&s);
        if (n==0 && s==0) break;
        printf("%d\n",dp[n][s]);
    }
    return 0;
}

数を0個から9個まで使うのをdpテーブルで予め表にしておくのとは別に力技でも出来ないこともない https://github.com/clarinet758/aoj/commit/7bf5fabac9197c57ff39406a5ef4b267a4dae502#diff-fc30481ee99d160a6d6ecae4617fc908 。むしろdpは写経だし、自力なのは力技でやった方。

0031: Weight

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int n;
    int w[10];
    w[0]=1;
    for (int i=1;i<10;++i) {
        w[i]=w[i-1]<<1;
    }
    while (scanf("%d",&n)!=EOF) {
        int tmp=0;
        stack<int> st;
        for (int i=9;i>=0;--i) {
            if (w[i]<=n) {
                st.push(w[i]);
                n-=w[i];
                tmp++;
            }
        }
        for (int i=0;i<tmp-1;++i) {
            printf("%d ",st.top());
            st.pop();
        }
        printf("%d\n",st.top());
    }
    return 0;
}

重りを重い方から使う。今見てる重りが残りの重さより重い場合には、その重りを使わないと重さが合わせられないため。

0032: Plastic Board

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int a,b,c;
    int ans[2]={0,0};
    while (scanf("%d,%d,%d",&a,&b,&c)!=EOF) {
        if (a==b) ans[1]+=1;
        else if (a*a+b*b==c*c) ans[0]+=1;
    }
    printf("%d\n%d\n",ans[0],ans[1]);
    return 0;
}

a,bの二辺が同じ長さか、a2+b2=c2の関係が成立するかで判定する。

0033: Ball

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int a,b,c;
    int ans[2]={0,0};
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;++i) {
        int l=0,r=0;
        vector<int> a(10);
        for(auto&e:a) {
            scanf("%d",&e);
        }
        int f=1;
        for (int j=0;j<10;++j) {
            if (j==0) l=a[0];
            else if (a[j]<l && a[j]<r) {
                f=0;
                printf("NO\n");
                break;
            } else if (a[j]>l && a[j]<r) {
                l=a[j];
            } else if (a[j]<l && a[j]>r) {
                r=a[j];
            } else if ((a[j]-l)>(a[j]-r)) {
                r=a[j];
            } else {
                l=a[j];
            }
        }
        if (f) printf("YES\n");
    }
    return 0;
}

どちらにも落とせそう?な時は落とそうとするものと、筒の上のボールの差分が小さい方へ落とす。あと、一番上のボールしか見ないので数を左右の筒を別々に1つずつだけ保存してあれば大丈夫。配列などで保存する必要は無いと思う。

0034: Railway Lines

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    int mod=1000000007;
    int a,b,c;
    int l[10],v[2];
    while (scanf("%d,",&l[0])!=EOF) {
        int tmp=l[0];
        for (int i=1;i<10;++i){
            scanf("%d,",&l[i]);
            tmp+=l[i];
        }
        scanf("%d,%d",&v[0],&v[1]);
        double chk=1.0*tmp*(v[0]*1.0/(v[0]+v[1]));
        if (chk-floor(chk)>1e-10) chk=chk+1.0;
        chk=floor(chk);
        int cnt=int(chk);
        int t=0;
        for (int i=0;i<10;i++) {
            t+=l[i];
            if (t>=cnt) {
                printf("%d\n",i+1);
                break;
            }
        }
    }
    return 0;
}

  駅間の長さ合計と列車の速さの比で計算すると思う。

0035: Is it Convex?

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()

double is_X (P p1, P p2, P p3, P p4) {
    return ((p1.X-p2.X) * (p3.Y-p1.Y) + (p1.Y-p2.Y) * (p1.X-p3.X)) * ((p1.X-p2.X) * (p4.Y-p1.Y) + (p1.Y-p2.Y) * (p1.X-p4.X));
}

int main(){
    int mod=1000000007;
    int a,b,c;
    double xa,xb,xc,xd,ya,yb,yc,yd;
    while (scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd)!=EOF) {
        P a(xa,ya);
        P b(xb,yb);
        P c(xc,yc);
        P d(xd,yd);

        if (is_X(a,c,b,d)>0.0 || is_X(b,d,a,c)>0.0) {
            printf("NO\n");
        } else {
            printf("YES\n");
        }
    }
    return 0;
}

あれ、、これって点が三角形の内外のどちらにあるかと同じ問題になるのでは。。。今回の判定方法は対角線が交差するかで判定。

0036: A Figure on Surface

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()


int main(){
    int mod=1000000007;
    int ax, ay;
    char f[12][12];
    bool flag=0;
    for (int i=0;i<12;++i) {
        for (int j=0;j<12;++j) {
            f[i][j]=0;
        }
    }

    for (;;) {
        for (int i=0;i<8;++i) {
            if(scanf("%s",f[i])==EOF) {
                flag=1;
                break;
            }
        }
        if (flag) break;

        for(int i=0;i<64;++i) {
            if (f[i/8][i%8]=='1') {
                ax=i%8;
                ay=i/8;
                break;
            }
        }
        if (f[ay+1][ax]=='1' && f[ay][ax+1]=='1' && f[ay+1][ax+1]=='1') printf("A\n");
        else if (f[ay+1][ax]=='1' && f[ay+2][ax]=='1' && f[ay+3][ax]=='1') printf("B\n");
        else if (f[ay][ax+1]=='1' && f[ay][ax+2]=='1' && f[ay][ax+3]=='1') printf("C\n");
        else if (f[ay+2][ax-1]=='1' && f[ay+1][ax]=='1' && f[ay+1][ax-1]=='1') printf("D\n");
        else if (f[ay][ax+1]=='1' && f[ay+1][ax+1]=='1' && f[ay+1][ax+2]=='1') printf("E\n");
        else if (f[ay+1][ax]=='1' && f[ay+1][ax+1]=='1' && f[ay+2][ax+1]=='1') printf("F\n");
        else if (f[ay][ax+1]=='1' && f[ay+1][ax]=='1' && f[ay+1][ax-1]=='1') printf("G\n");
    }
    return 0;
}

大きめの配列サイズ12で入力上のサイズの8*8の枠外を見に行ってもエラーにならない&枠外になるかを気にせずにブロックの形状を確認できるように対応。

0037: Path on a Grid

残件で

0038: Poker Hand

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()


int main(){
    int mod=1000000007;
    int ax, ay;
    char f[12][12];
    int c[5];
    while (scanf("%d,%d,%d,%d,%d",&c[0],&c[1],&c[2],&c[3],&c[4])!=EOF) {
        vector<int> card(5);
        for (int i=0;i<5;++i) {
            card[i]=c[i];
        }
        sort(card.begin(),card.end());
        if ((card[1]==card[2] && card[2]==card[3]) && (card[0]==card[1] || card[4]==card[3])) printf("four card\n");
        else if ((card[0]==card[1] && card[3]==card[4]) && (card[2]==card[1] || card[2]==card[3])) printf("full house\n");
        else if (card[0]==card[1]-1 && card[1]==card[2]-1 && card[2]==card[3]-1 && card[3]==card[4]-1) printf("straight\n");
        else if (card[0]==1 && card[1]==10 && card[2]==11 && card[3]==12 && card[4]==13) printf("straight\n");
        else if ((card[0]==card[1] && card[1]==card[2]) || (card[1]==card[2] && card[2]==card[3]) || (card[2]==card[3] && card[3]==card[4])) printf("three card\n");
        else if ((card[0]==card[1] && (card[2]==card[3] || card[3]==card[4])) || (card[1]==card[2] && card[3]==card[4])) printf("two pair\n");
        else if (card[0]==card[1] || card[1]==card[2] || card[2]==card[3] || card[3]==card[4]) printf("one pair\n");
        else printf("null\n");
    }
    return 0;
}

強い、優先順位の高い役から判定する。

0039:

C++14

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()


int main(){
    int mod=1000000007;
    map<char, int> d;
    d['I']=1;
    d['V']=5;
    d['X']=10;
    d['L']=50;
    d['C']=100;
    d['D']=500;
    d['M']=1000;
    char c[60];
    int len,t,value;
    while (fgets(c,60,stdin)!=NULL)  {
        len=strlen(c)-1;
        t=0,value=1000;
        for (int i=0;i<len;++i) {
            if (value>=d[c[i]]) {
                value=d[c[i]];
                t+=value;
            } else {
                t=t-value*2;
                value=d[c[i]];
                t+=value;
            }
        }
        printf("%d\n",t);
    }
    return 0;
}

昔にpythonで写経したものをC++で書き直し。