paiza スキルチェック過去問「値の計算」をC言語で解く

paizaの過去問の以下を解きましたので、コメントを書いたプログラムを掲載し、メモします。

成績としては、入力受け取りで12分、1回目の回答まで25分かかり一部誤答、そして追加で5分考えて、2回目の回答をし、正答となりました。

入力受け取りを書くのに、そこそこ時間がかかっています。
どういうデータ構造で受けとればいいか迷い、最終的にA~Zまでの文字を0~25までに対応させることにしました。

1回目の回答は以下の通りです。

1回目 解答

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

int main(void){
    char buf[1000 * 1000 + 1];
    int n;
    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%d", &n);
    
    
    float r[26] = {0};
    for(int i = 0; i < n; i++) {
        char s;
        int w;
        fgets(buf, sizeof(buf), stdin);
        sscanf(buf, "%c %d", &s, &w);
        r[s - 'A'] = w;
    }
    
    int m;
    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%d", &m);
    
    char kairo[1000][1000+1];
    fgets(buf, sizeof(buf), stdin);
    char *ptr = strtok(buf, " ");
    int i = 0;
    while(ptr != NULL) {
        sscanf(ptr, "%s", kairo[i]);
        ptr = strtok(NULL, " ");
        i++;
    }
    
#if 0
    for(int i = 0; i < n; i++) {
        printf("[%c] %f\n", (char)('A' + i), r[i]);
    }
    for(int i = 0; i < m; i++) {
        printf("%s\n", kairo[i]);
    }
#endif

    float result[1000] = {0};
    for(int i = 0; i < m; i++) {
        //printf("%d\n", strlen(kairo[i]));
        if(strlen(kairo[i]) >= 2) {
            float sum = 0;
            for(int j = 0; j < strlen(kairo[i]); j++) {
                //printf("2ijou %c %f\n", kairo[i][j], r[kairo[i][j]-'A']);
                sum += (float)1 / r[kairo[i][j]-'A'];
            }
            result[i] = (float)1 / sum;
        }
        else {
            //printf("1chars %c %f\n", kairo[i][0], r[kairo[i][0]-'A']);
            result[i] = r[kairo[i][0]-'A'];
        }
    }
    
    float sum = 0;
    for(int i = 0; i < m; i++) {
        //printf("[%d] %f\n", i, result[i]);
        sum += result[i];
    }
    
    printf("%d\n", (int)sum);

    
    return 0;
}

これで、最後のテストデータのみ誤答となりました。

与えられる入力を確かめると、最大値の入力を与えられた場合のようでしたので、たぶんバッファの確保がおかしいんだなと検討をつけ、確認。

最終的には、回路図を受けとるbufのサイズを、
char buf[1000 * 1000 + 1];から、
char buf[1000 * (1000 + 1)];へ修正しました。

スペース区切りの各部分回路の長さは最長1000文字で、NULL終端も受けとるので+1、それを1000セットあるのが最大に必要なバッファのサイズという考え方です。

でも、あっているかはあんまり自信がありません。

また、floatだとオーバーフローしているかもしれないため、doubleへ置き換えました。

そして、最終的なコードは以下の通りです。
適宜コメントを付与しておきました。

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

int main(void){
    
    // 入力受け取り
    
    // t_1 t_2 ... t_Mを受けとるのにも使うので、必要なだけ確保する
    char buf[1000 * (1000 + 1)];
    
    // 抵抗の個数
    int n;
    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%d", &n);
    
    // 各抵抗の名前と抵抗値
    double r[26] = {0};
    for(int i = 0; i < n; i++) {
        char s;
        int w;
        fgets(buf, sizeof(buf), stdin);
        sscanf(buf, "%c %d", &s, &w);
        r[s - 'A'] = w; // 'A' = 0, 'B' = 1, 'C' = 2, ... 'Z' = 25となる
    }
    
    // 回路図のスペース区切りのデータ数（直列の個数）
    int m;
    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%d", &m);
    
    // 回路図を受けとる
    char kairo[1000][1000+1]; // kairo[0], kairo[1], ...にそれぞれスペース区切りの部分回路が格納
    fgets(buf, sizeof(buf), stdin);
    char *ptr = strtok(buf, " ");
    int i = 0;
    while(ptr != NULL) {
        sscanf(ptr, "%s", kairo[i]);
        ptr = strtok(NULL, " ");
        i++;
    }
    
    // 入力が正常に受けとれたか確認
#if 0
    for(int i = 0; i < n; i++) {
        printf("[%c] %f\n", (char)('A' + i), r[i]);
    }
    for(int i = 0; i < m; i++) {
        printf("%s\n", kairo[i]);
    }
#endif

    // ここから回答
    
    // 直列でつながっているすべての部分回路の抵抗値を求める
    double result[1000] = {0}; // 各部分の抵抗値
    for(int i = 0; i < m; i++) {
        //printf("%d\n", strlen(kairo[i]));
        // 各部分回路の文字数を確認、2以上だったら、
        // 部分回路は並列に抵抗がつながっているので、計算する
        if(strlen(kairo[i]) >= 2) {
            double sum = 0; // 並列計算の分母
            for(int j = 0; j < strlen(kairo[i]); j++) {
                //printf("2ijou %c %f\n", kairo[i][j], r[kairo[i][j]-'A']);
                sum += (double)1 / r[kairo[i][j]-'A']; // doubleへのキャストが必要だと思う
            }
            // 最終的な部分回路の抵抗値を求める
            result[i] = (double)1 / sum;
        }
        // 抵抗が1つの場合は、それが部分回路の抵抗値である
        else {
            //printf("1chars %c %f\n", kairo[i][0], r[kairo[i][0]-'A']);
            result[i] = r[kairo[i][0]-'A'];
        }
    }
    
    // 各部分の抵抗値を求め終わったため、すべて足し合わせて出力する
    double sum = 0;
    for(int i = 0; i < m; i++) {
        //printf("[%d] %f\n", i, result[i]);
        sum += result[i];
    }
    
    printf("%d\n", (int)sum);

    return 0;
}

終わりに

境界値のテストデータを扱われると、ふわふわとした考えで回答していることによる穴を突かれます。

ここもゆくゆく改善していきたいです。