POH! Vol.2 C模範解答

こちらではpaiza事務局側で作成したコードを随時掲載していきます。
更新日:2014年4月30日(水)

C: paiza事務局作成コード Vol.3 動的計画法

得点:100点
通過テストケース数:7/7

#include <stdio.h>

#define MIN(a, b) ((a)<(b)?(a):(b))
#define INF 1001001001

int main(void)
{
    int h, w, n;
    int i, j, k;
    int dp[310][310], ans[310][310] = {{}};
    char display[310][310];
    int swap = 0;

    scanf("%d%d", &h, &w);
    for(i=0; i<h; ++i){
        scanf("%s", display[i]);
    }

    if(w < h){
        int t[310][310];
        for(i=0; i<h; ++i){
            for(j=0; j<w; ++j){
                t[i][j] = display[i][j];
            }
        }

        int tmp = h;
        h = w;
        w = tmp;
        swap = 1;

        for(i=0; i<h; ++i){
            for(j=0; j<w; ++j){
                display[i][j] = t[j][i];
            }
        }
    }

    for(i=0; i<h; ++i){
        for(j=0; j<w; ++j){
            dp[i][j] = INF;
        }
        dp[i][w] = 0;
    }

    for(k=0; k<h; ++k){
        int hist[310] = {};

        for(i=0; i<h-k; ++i){
            dp[i][0] &= display[i+k][0] == '0';
            for(j=1; j<w; ++j){
                dp[i][j] = display[i+k][j] == '0' ? MIN(dp[i][j], dp[i][j-1]+1) : 0;
            }
        }

        for(i=0; i<h-k; ++i){
            for(j=0; j<w; ++j){
                hist[dp[i][j]] += dp[i][j] && !dp[i][j+1];
            }
        }

        int sum = 0;
        for(i=1; i<=w; ++i){
            sum += hist[i];
            ans[k+1][1] += i*hist[i];
        }

        for(i=2; i<=w; ++i){
            ans[k+1][i] = ans[k+1][i-1] - sum;
            sum -= hist[i-1];
        }
    }

    scanf("%d", &n);
    for(k=0; k<n; ++k){
        int s, t;
        scanf("%d%d", &s, &t);
        printf("%d\n", swap ? ans[t][s] : ans[s][t]);
    }

    return 0;
}

C: paiza事務局作成コード Vol.2 O(H^2W^2)

得点:71点
通過テストケース数:5/7

#include <stdio.h>

int main(void)
{
    int h, w, n;
    int i, j, k;
    int sum[310][310];

    scanf("%d%d", &h, &w);
    for(i=0; i<h; ++i){
        char line[310];
        scanf("%s", line);
        for(j=0; j<w; ++j){
            sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + (line[j] == '1');
        }
    }

    scanf("%d", &n);
    for(k=0; k<n; ++k){
        int s, t, cnt = 0;
        scanf("%d%d", &s, &t);

        for(i=s; i<=h; ++i){
            for(j=t; j<=w; ++j){
                int num = sum[i][j] - sum[i-s][j] - sum[i][j-t] + sum[i-s][j-t];
                cnt += num == 0;
            }
        }

        printf("%d\n", cnt);
    }

    return 0;
}

C: paiza事務局作成コード Vol.1 O(H^3W^3)

得点:42点
通過テストケース数:3/7

#include <stdio.h>

int main(void)
{
    int h, w, n;
    int i, j, k;
    char display[310][310];

    scanf("%d%d", &h, &w);
    for(i=0; i<h; ++i){
        scanf("%s", display[i]);
    }

    scanf("%d", &n);
    for(k=0; k<n; ++k){
        int s, t, cnt = 0;
        int y, x;
        scanf("%d%d", &s, &t);

        for(y=0; y<=h-s; ++y){
            for(x=0; x<=w-t; ++x){
                int ok = 1;
                for(i=0; i<s; ++i){
                    for(j=0; j<t; ++j){
                        if(display[y+i][x+j] == '1'){
                            ok = 0;
                            goto next;
                        }
                    }
                }
            next:
                cnt += ok;
            }
        }
        printf("%d\n", cnt);
    }

    return 0;
}
ページの先頭へ戻る