Arc's Laboratory

プログラミングとかの研究室

日本情報オリンピック2017/2018 予選レビュー

どうも。Arcです。

今回は、2017年12月10日に行われた日本情報オリンピック(以下JOI)の記録とか反省とかを話していきたいと思います。

問題はこちらのJOI公式サイトからどうぞ。

ソースコードはすべてCです。

問題1 鉛筆 (Pencils)

#include<stdio.h>
int main(void){
    int n,a,b,c,d;
    int bought_a=0,bought_c=0;
    int cost_a=0,cost_c=0;
    int loop;
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    while(bought_a<n){ //n本以上の鉛筆が集まるまで買い続ける
        bought_a+=a; //買った個数を増やす
        cost_a+=b; //総額を増やす
    }
    while(bought_c<n){
        bought_c+=c;
        cost_c+=d;
    }
    if(cost_a>cost_c){
        printf("%d\n",cost_c);
    }else{
        printf("%d\n",cost_a);
    }
    
    return 0;
}

……模範解答と比べてだいぶ汚いなこりゃ。というか[(Q+P-1)/P]なんて思いつかない

問題2 双六(Sugoroku)

#include<stdio.h>

int main(void){
    int n;
    int temp;
    int chain=0;
    int max=0;
    int loop;
    scanf("%d",&n);
    for(loop=0;loop<n;loop++){
        scanf("%d",&temp);
        if(temp==1){ //見ているマスが1だったら
            chain++; //chainをインクリメント
        }else{ //そうでなければ
            if(max<chain){ //chainの最大値を更新する処理
                max=chain;
            }
            chain=0;
        }
    }
    if(max<chain){  //もしかしたら最大値更新されているかもしれないのでもう一度
        max=chain;
    }
    printf("%d\n",max+1);
    
    return 0;
}

1の書かれたマスが最大max個続いていれば、max+1の目があるサイコロでゲームクリア可能。ということで、maxの値を求めにいきました。

模範解答とは解法が違うようですが、一応O(n)のアルゴリズムです。

問題3 幹線道路 (Trunk Road)

#include<stdio.h>
#include<stdlib.h>

//macro
#define INF 1000000

//global
int h,w;
int field[25][25];
int min=INF;

//function
int solve(int road_h,int road_w){
    int loop1,loop2;
    int answer=0;
    int dis_h,dis_w; //distance_h方向、distance_w方向の意味
    for(loop1=0;loop1<h;loop1++){
        for(loop2=0;loop2<w;loop2++){
            dis_h=loop1-road_h;
            dis_w=loop2-road_w;
            if(dis_h<0) dis_h=dis_h*-1;
            if(dis_w<0) dis_w=dis_w*-1;
            if(dis_h<dis_w){
                answer+=field[loop1][loop2]*dis_h;
            }else{
                answer+=field[loop1][loop2]*dis_w;
            }
        }
    }
    return answer;
}

int main(void){
    int loop1,loop2;
    int temp;
    scanf("%d%d",&h,&w);
    for(loop1=0;loop1<h;loop1++){
        for(loop2=0;loop2<w;loop2++){
            scanf("%d",&field[loop1][loop2]);
        }
    }
    for(loop1=0;loop1<h;loop1++){
        for(loop2=0;loop2<w;loop2++){
            temp=solve(loop1,loop2);
            if(min>temp){
                min=temp;
            }
        }
    }
    printf("%d\n",min);
    return 0;
}

東西方向の道路をloop1、南北方向の道路をloop2としたときの距離の総和をtemp=solve(loop1,loop2)で求めています。

求めた値tempで最小値を更新できれば更新して、最終的な最小値を出力しています。

最初の#define INF 1000000の値を小さくしすぎるとバグるので要注意。一度Wrong Answerになりました。

問題4 水ようかん (Mizuyokan)

#include<stdio.h>
#include<stdlib.h>

//global
int n;
int yokan[50]={};
int frag=0;
int yokanlength=0;
//function
void scan(void)
{
    int loop=0;
    scanf("%d",&n);
    for(loop=0;loop<n;loop++){
        scanf("%d",&yokan[loop]);
        yokanlength+=yokan[loop];
    }
}
void search(int min,int max,int point){
    int length=0;
    while(length<=max && point<n){
        length+=yokan[point];
        point++;

        if(length>=min && length<=max){
            if(point>=n){
                frag++;
            }else{
                search(min,max,point);  
            }
        }
    }
}

int main(void){
    scan();
    int answer,minimum;
    int loop;
    int temp;
    while(frag==0){
        for(answer=0;answer<yokanlength;answer++){
            for(minimum=0;minimum<yokanlength-answer;minimum++){
                search(minimum,minimum+answer,0);
            }
            if(frag!=0){
                printf("%d\n",answer);
                return 0;
            }
        }   
    }
}

最初は動的計画法(DP)を使おうとしたのですが、うまいやり方が見つかりませんでした。

悩んでたら時間がなくなってきたので、仕方なく部分点狙いで(ちょっと工夫した)全探索をかけることにしました。

ちょっと解説

main関数

answerの値は「羊羹の長さの最大誤差」です。

main()関数内のforループでsearch(min,max,0)を呼び出していますが、この関数は

search(切り分ける羊羹の最短の長さ,切り分ける羊羹の最長の長さ,どこまで羊羹の切れ目を見たか)

という感じに見てください。

minimumとanswerの値を利用して、minmaxの値を変化させています。

search(min,max,point)関数

ここでは、pointから羊羹の切れ目を眺めていったときに、min以上max以下の長さの羊羹を切り分けられるかを判別しています。

もし切り分けられるのなら、新たにsearch(min,max,次に羊羹の切れ目を眺め始める場所)を呼び出します。

切り分けられる場所が複数あることを考慮して、深さ優先探索(DFS)的なコードにしてあります。

また、羊羹の切れ目をすべて眺め終わっていたのなら、フラグを立ててmain()answerの値を出力します。

一応ムダな計算をしないように作ったつもりではいますが、多分完答できないだろうな……と思ったら。

完答できました。

main部の計算量は{(yokanlength2)/2}ぐらいなんですが、search部の深さ優先探索で処理数が大幅に増える可能性があったのでびっくりしました。

フラグが立てばバッサリ枝刈りできることが功を奏したのでしょうか。

ちなみにAtcoderの処理時間は1000msぐらいでした。

問題5

時間切れになりました。問題4で時間使いすぎました。

まとめ

偶然に助けられた感じもしましたが、最終結果は400点。Aランクで本戦進出決定しました。

もう20分ぐらいあれば問題5も解けたのかも……というところが少々残念。

動的計画法にもっと慣れなければなりませんね。

ということで、JOI予選レビューでした。