月別アーカイブ: 12月 2015

JOI2015/2016 予選

こんばんは，ransewhaleです。

実は先週の日曜日(2015/12/13)に日本情報オリンピック(Japanese Olympiad in Informatics/JOI)2015/2016の予選に参加してきました! してきましたと言っても予選はオンライン実施で家で参加したわけですが…

というわけで，昨日結果がわかったんですが，反省の意を込めてこの予選を振り返ってみたいなと思います。

  • 問題1

    科目選択 (Selecting Subjects)
    問題1は解説にある通り”肩慣らし”ですね。自分なりのソースコードを

    #include<stdio.h>
int main(void){
    int science,social[2],worst=101,i,total=0;
    for(i=0; i<4; i++){
        scanf("%d",&science);
        total+=science;
        if(worst>science){
            worst=science;
        }
    }
    total-=worst;
    for(i=0; i<2; i++){
        scanf("%d",&social[i]);
    }
    total+=(social[0]>social[1])?social[0]:social[1];
    printf("%d\n",total);
    return 0;
}

  • 問題2

    ゼッケンの交換 (Swapping Bibs)
    ちょっとミスって危なかったですが，なんとかクリアw コードが汚いのは気にしない()

    #include<stdio.h>
int main(void){
    int n,m,num[101],i,j,a,b;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++){
        scanf("%d",&num[i]);
    }
    for(i=1; i<=m; i++){
        for(j=1; j<n; j++){
            a = num[j]%i;
            b = num[j+1]%i;
            if(a>b){
                a=num[j];
                num[j]=num[j+1];
                num[j+1]=a;
            }
        }
    }
    for(i=1; i<=n; i++){
        printf("%d\n",num[i]);
    }
    return 0;
}

  • 問題3

    ロシアの旗 (Russian Flag)
    よくよく考えなくてもプロのみなさんならわかる通り，これ一行にどんな配置で色が塗ってあっても関係ないんですよねw ←あたりまえだろって? でも私はn分ほど気付かなかったんだよ
    そこに気づいたらあとはそんなに時間はかからなかった気がします。
    今考えると無駄が多いような気も…? まあこれから精進精進(白目)

    #include<stdio.h>
int main(void){
    int n,m,flag[50][3],i,j,k,a,ans=-1;
    char color[50];
    scanf("%d%d",&n,&m);
    for(i=0; i<n; i++){
        flag[i][0]=0;
        flag[i][1]=0;
        flag[i][2]=0;
        scanf("%s",color);
        for(j=0; j<m; j++){
            if(color[j]=='W'){
                flag[i][0]++;
            }else if(color[j]=='B'){
                flag[i][1]++;
            }else if(color[j]=='R'){
                flag[i][2]++;
            }
        }
    }
    for(i=1; i<n-1; i++){
        for(j=i; j<n-1; j++){
            a=0;
            for(k=0; k<n; k++){
                if(k<i){
                    a+=flag[k][0];
                }else if(k>j){
                    a+=flag[k][2];
                }else{
                    a+=flag[k][1];
                }
            }
            if(ans<a){
                ans = a;
            }
        }
    }
    ans -= n*m;
    ans *= (-1);
    printf("%d\n",ans);
    return 0;
}

  • 問題4

    JOI国のお散歩事情 (Walking in JOI Kingdom)
    多分大部分の方はすぐに「あっDPじゃない」と気づかれたのかと思われますが，私はずっとDPでどう解けるか考えてました()
    入出力例1を図に書いてみて，初めて「あっ，これってそれぞれが出会う場所ってすぐ求められるじゃないか」と気づいてそこから実装していきました。
    しかも私は問題文を読まない悪い子なので()，”すべての i (1 ≦ i ≦ N – 1) について，Ai < Ai+1 を満たす”という条件を見事に見逃してて無駄なコードを書いてました。本選までには治したい癖ですね。
    long long intを100000個とか本選だとメモリ制限に引っかかりそうだしこれからはそこらへんも考えないとダメなのかな…(と思ってサンプルソース見たらそうでもなかったですね)
    あっ，あと今回初めてllabs関数とかいう関数を知りました。(abs関数使ったら怒られた)

    #include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(void){
    int n,q,b[100000],i,j,flag=0,min,max,meet[50000],count,person,now=0;
    long long int t,a[100000],tmp,point[50000];
    scanf("%d%lld%d",&n,&t,&q);
    for(i=0; i<n; i++){
        scanf("%lld%d",&a[i],&b[i]);
        if(flag==0){
            if(b[i]==1){
                flag=1;
                count=0;
                meet[count]=i;
            }
        }else{
            if(b[i-1]==1 && b[i]==2){
                point[count]=(a[i-1]+a[i])/2;
            }else if(b[i-1]==2 && b[i]==1){
                count++;
                meet[count]=i;
            }
            if(b[i]==2 && i==n-1){
                count++;
                meet[count]=n;
            }
        }
    }
    for(i=0; i<q; i++){
        scanf("%d",&person);
        flag=0;
        person--;
        for(j=now; j<count; j++){
            if(person<meet[0]){
                tmp=a[person]-t;
                printf("%lld\n",tmp);
                now = j;
                flag=1;
                break;
            }else if(person>=meet[j] && person<meet[j+1]){
                if(llabs(point[j]-a[person]) > t){
                    tmp=(b[person]==1)?(a[person]+t):(a[person]-t);
                }else{
                    tmp=point[j];
                }
                printf("%lld\n",tmp);
                now = j;
                flag = 1;
                break;
            }
        }
        if(flag==0){
            tmp=a[person]+t;
            printf("%lld\n",tmp);
        }
    }
    return 0;
}

  • 問題5

    ゾンビ島 (Zombie Island)
    これは時間内に(時間があっても…?)解けませんでした。
    危険な島と安全な島を分けるところまでは組めたんですが，そこからダイクストラを実装できませんでした() 頭の中にダイクストラというワードが出てきただけにつらかったです。組む知識/能力がなかった上に時間も残り5分だったので諦めました。
    精進あるのみ。

  • 問題6

    屋台 (Food stalls)
    これは1つくらい部分点が狙えたのではないかとおもうと案の定解説に…

    屋台の数を S とすると，お菓子を購入する屋台の選び方は 2S 通りになり，入力 1 に対しては正解できる

    とあったのでとてもつらいです。

というわけで，合計4完=400点でした。

スクリーンショット 2015-12-18 2.37.09
一応400≥360なので(ですよね? 違うなら今言ってくださいw)本当に本選に行ってもいいのかと聞きたくなるレベルの雑魚さではあるんですが，本選に行けることとなりました。本当に嬉しいです!

蟻本を買って1から勉強しようと思ってます。せっかく掴んだ最後のチャンス，最善を尽くしたいと思ってます(^o^)/

そして，今回なんだか競技プログラミングがすごく面白く感じたので，他のオンラインコンテストとかにも参加してみようかとかも検討中ですw こういう趣味はすごくいいかなぁと。(まあ受験とか語学とかとの兼ね合いもあるんですがね…)

何かあればコメントを下さるとありがたいです。ではではm(_ _)m