JOI2015/2016 本選

JOI予選の話を見てない方はそちらを先に… 

JOIの本選に参加してきました。

結果から言うと,151点。ホントにダメダメ… (最初で)最後の機会だっただけに本当に信じられず自分でもショックです…

では詳細を…

往路

本選よりなにより新幹線に乗れることが嬉しかったですw ←この時点でダメ

きちんと切符を改札に通すことなく無効印を押してもらって回収出来たのもよかったです。

プラクティス

ご存知の方もいると思いますが,JOIの本選ではプラクティスという本番環境になれるためのコンテストがあります。

場の雰囲気が緩やかだったのもあり緊張することなく,(16:20くらい開始になってましたが)無事時間内に全問解くことができました。割りとこれは自信になったと思います。

第5問のソースコードをプロに見せると,

これ二分探索つかってるけど二分探索使わずにO(nlog n)じゃなくてO(n2)で解ける

と言われ,その解法でも一応通しておきました。プロに圧倒的感謝m(_ _)m

夕食

自己紹介に気が取られてあまり食べられませんでした。

自己紹介はみんなプロプロしていました。

僕は雑魚っぽく「文系の人は徒党組みましょう」としか言えなかったです。自然言語が好きな人とか呼びかければよかった…

お風呂よりシャワーがよかったので,23:00にシャワーが開くのを待ってました。

つもりが…

ダイクストラをやって,そのあとフクロモモンガに悪戦苦闘してました。

結局シャワー室に行ったのは23:45くらいで,寝たのは01:30頃。

05:40に目が覚めて,フクロモモンガをなんとか通しました。やったぜ()

朝ごはんが和食でうれしかったです。

本選競技

つらい。

まず,1番をDPでとこうと頑張ったがうまくいかず,仕方なしにそこで仕切るかというのを全列挙していきました。頭悪い。これで2時間弱使ったのに20点。つらい。

2番は解説とはすこし違ったが比較的簡単に通りました(馬鹿なのでJとIもすべての場所について試すソースになってたはず)。2回くらいWAを出したあとAC。やったぜ。

3番はDijkstraで26点頂きました。終了間際に少し改良した(つもり)のソースコードを提出したのですがWAでした。

4番は2次元配列にシミュレーションして5点頂きました。(ちなみに最初200100*200100の配列をつくってCompile Error出しました())

5番は脳が地学の問題だと思い込んで反応してくれなかったので0点。

20+100+26+5+0=151 … とてもつらい。

せめて1番で部分点70はなんとか取らないといけなかったと反省してます。

解説

解説はなんとか理解できたが,その発想力に驚かされた。面白かったですw

おまけ

つくばに住んでいらっしゃるというフォロワーさんにお会いしました。会場まで来てくださったの本当に有難うございました。

まとめ

来年がないだけにつらいです。まあでも,英検みたいにボーダーギリギリで落ちるよりは精神的に優しいかなぁ,と思ってます。

これから競技プログラミングを続けるかもまだ決めてませんが,面白いとは思いますし,続けていけたらなあと思ってます。

これからも精進するのでよろしくお願いします!

追記(2016/02/16)… 151点で確定,Bランクでした。みなさん本選お疲れ様でした。春合宿に行かれる方,来年チャンスがあってまた挑戦する方は頑張ってください!! 

広告

あけましておめでとうございます

皆様,新年明けましておめでとうございます!

今年もどうぞよろしくお願いいたします。

ところで,新年の抱負,みなさんはもう考えましたか? 僕なりの抱負をここに…

つい廃から脱すること。
圧倒的成長を遂げること。
少しでも健康的な体型になること。
(引用元: Ask.fm – ransewhale)

というわけで今年も精一杯生きていきます。温かい目でみてください()
自分がもう受験生になる… というのは信じられません。勉強を頑張っていい大学に入るのか,適度に頑張って普通に行ける大学に行くのかすらまだ決めていません。自分が今までやり残したことがあまりに多すぎて,とても後悔しています。つらい。
そして,受験生になるというのに受験に対するモチベーションは下がる一方です。いっそ留年でもしたいくらいの気分です。来年のこの時期には余裕でセンター試験を待ち構えられているといいですね。とりあえずJOIの本選に向けて頑張りたい。
ではでは皆様,今年もよい1年になりますように…

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

新たな気持ちで

こんにちは,ransewhaleと申します。

この度,ransewhale.netのサーバーをlolipopから自鯖に移したのですが,データ移行をすっかり忘れてたためブログを新設いたしました。
<p style=”text-align: left;”>放課後の黒板のようにいろんなことをちまちま書いていきたいと思ってます。どうぞこれからよろしくお願いします。</p>
<p style=”text-align: left;”>ブログの方はとりあえずは2週間に1回の更新を目指したいと思いますw 軽い気持ちでいつでも覗いてくださいなww</p>
<p style=”text-align: left;”>年末(2015年12月)までにはransewhale.netのシステムを整えて運用できる状態にしたいですね^^ ハードル結構ありますが頑張ります〜</p>
<p style=”text-align: left;”>最後に,ブログを見つけて「こいつおもしれぇ」ってなったらTwitterアカウント( <a href=”https://twitter.com/ransewhale&#8221; target=”_blank”>@ransewhale</a> )にリプもしくはフォローお願いします!</p>
<p style=”text-align: left;”>ではでは(^-^)/</p>