Google Code Jam Qualification Round 通りました

先日受けたGoogle Code Jam通りました。
次は次週の土曜日か日曜日。

このまま順調に行くと地元へ帰る予定とぶつかったりして困るなぁと取らぬ狸の皮算用してるわけですが、最初から次に進めないと思ってやっていたら駄目になるだろうからどっちに転んでもよいように準備していきたいなとは思います。

とりあえずやっつけコードをさらします。コメントを追記したのみで後はいじってません。あらためて見るとやけに長いコードだと感じる。
問題文はhttp://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQwを参照。Problem AとProblem Bです。

Problem A

#include <stdio.h>
#include <string.h>

struct check {
    char s[101]; /* 検索エンジン名 */
    int flag;    /* 使われたかどうかを管理 */
};

int main()
{
    int i, j, k, l;
    int strings;         /* 検索エンジン登録数 */
    int count;           /* 問題数 */
    int s_count;         /* 検索エンジン数 */
    int q_count;         /* クエリ数 */
    struct check s[100]; /* 重複しないかチェック */
    char buf[101];       /* 入力用のバッファ */
    int switches;        /* 何回検索エンジンを切り替えるようか　*/
    int all;             /* クエリ要求された検索エンジンのカウント */

    fgets(buf, 101, stdin);
    sscanf(buf, "%d", &count);
    for(i = 0; i < count; i++) {
        /* 初期化。不要だったか  */
        for(j = 0; j < 100; j++) {
            s[j].s[0] = '\0';
            s[j].flag = 0;
        }

        /* 検索エンジン数を取得 */
        fgets(buf, 101, stdin);
        sscanf(buf, "%d", &s_count);

        /* 重複なしで検索エンジンを登録 */
        strings = 0;
        for(j = 0; j < s_count; j++) {
            fgets(buf, 101, stdin);
            for(k = 0; k < strings; k++) {
                if(strcmp(buf, s[k].s) == 0) {
                    break;
                }
            }
            if(k == strings) {
                strcpy(s[strings].s, buf);
                strings++;
            }
        }

        /* ひっかかるかひっかからないか */
        fgets(buf, 101, stdin);
        sscanf(buf, "%d", &q_count);

        switches = 0;
        all = 0;
        for(j = 0; j < q_count; j++) {
            fgets(buf, 101, stdin);
            for(k = 0; k < strings; k++) {
                if(s[k].flag == 0 && strcmp(buf, s[k].s) == 0) {
                    all++;
                    /* すべての検索エンジンにクエリがかかったので
                     * 切り替えないといけなくなった。
                     */
                    if(all == strings) {
                        switches++;
                        for(l = 0; l < strings; l++) {
                            s[l].flag = 0;
                        }
                        all = 0;
                        all++;
                    }
                    /* 切り替えた時点で現在の検索エンジンは
                     * 使用していることになる
                     */
                    s[k].flag = 1;
                    break;
                }
            }
        }

        printf("Case #%d: %d\n", i+1, switches);
    }

    return 0;
}

Problem B

#include <stdio.h>
#include <string.h>

struct trip {
    int start; /* 出発時刻 */
    int end;   /* 到着時刻 */
    int flag;  /* 乗り換えたか管理 */
};

/* 時間順で並べるために使用 */
void sort(struct trip *data, int n);

int main()
{
    int N;  /* 問題数 */
    int NA; /* Aから出発する数 */
    int NB; /* Bから出発する数 */
    int T;  /* 待ち合わせ時間 */

    struct trip a_data[100]; /* Aから出発する列車の管理 */
    struct trip b_data[100]; /* Bから出発する列車の管理 */
    int AHH, AMM, BHH, BMM;  /* 出発、到着時刻入力用 */
    int a_count;             /* 最低限必要なAからでる列車の数 */
    int b_count;             /* 最低限必要なBからでる列車の数 */
    
    int i, j, k;   /* ループカウンタ */
    char buf[128]; /* 入力用バッファ */

    /* 問題数の入力 */
    fgets(buf, 128, stdin);
    sscanf(buf, "%d", &N);

    for(i = 0; i < N; i++) {
        /* 待ち合わせ時間の入力 */
        fgets(buf, 128, stdin);
        sscanf(buf, "%d", &T);

        /* Aからの出発する回数,Bから出発する回数の入力 */
        fgets(buf, 128, stdin);
        sscanf(buf, "%d %d", &NA, &NB);

        /* Aから出発する列車の情報の入力 */
        for(j = 0; j < NA; j++) {
            fgets(buf, 128, stdin);
            sscanf(buf, "%d:%d %d:%d", &AHH, &AMM, &BHH, &BMM);
            a_data[j].start = AHH * 60 + AMM;
            a_data[j].end   = BHH * 60 + BMM;
            a_data[j].flag  = 0;
        }
        sort(a_data, NA);

        /* Aから出発する列車の情報の入力 */
        for(j = 0; j < NB; j++) {
            fgets(buf, 128, stdin);
            sscanf(buf, "%d:%d %d:%d", &AHH, &AMM, &BHH, &BMM);
            b_data[j].start = AHH * 60 + AMM;
            b_data[j].end   = BHH * 60 + BMM;
            b_data[j].flag  = 0;
        }
        sort(b_data, NB);

        a_count = NA;
        b_count = NB;

        /* Aから出発した列車をBから出発に利用できないか */
        for(j = 0; j < NA; j++) {
            for(k = 0; k < NB; k++) {
                if(b_data[k].flag == 0
                && (a_data[j].end + T) <= b_data[k].start) {
                    b_data[k].flag = 1;
                    b_count--;
                    break;
                }
            }
        }
        /* Bから出発した列車をAから出発に利用できないか */
        for(j = 0; j < NB; j++) {
            for(k = 0; k < NA; k++) {
                if(a_data[k].flag == 0
                && (b_data[j].end + T) <= a_data[k].start) {
                    a_data[k].flag = 1;
                    a_count--;
                    break;
                }
            }
        }

        printf("Case #%d: %d %d\n", i+1, a_count, b_count);
    }

    return 0;
}

/* 時間順で並べるために使用 */
/* 出発時間で昇順に並べる */
/* 出発時間が同じならば到着時間で昇順になるようにする */
void sort(struct trip *data, int n)
{
    int i, j;
    struct trip temp;

    for(i = 0; i < n-1; i++) {
        for(j = i+1; j < n; j++) {
            if(   data[i].start > data[j].start
               || (  (data[i].start == data[j].start)
                   &&(data[i].end    > data[j].end  )) ) {
                temp    = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
    }
}