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