こちらでは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; }