こちらではpaiza事務局側で作成したコードを随時掲載していきます。
更新日:2014年4月30日(水)
C#: paiza事務局作成コード Vol.3 動的計画法
得点:100点
通過テストケース数:7/7
using System; class Program { public static void Main(String[] args) { String[] line = Console.ReadLine().Split(' '); int h = int.Parse(line[0]); int w = int.Parse(line[1]); String[] display = new String[h]; for(int i=0; i<h; i++){ display[i] = Console.ReadLine(); } int[,] dp = new int[310, 310]; int[,] table = new int[310, 310]; for(int i=0; i<310; i++){ for(int j=0; j<310; j++){ dp[i, j] = 1001001001; } } for(int k=0; k<h; k++){ for(int i=0; i<h-k; i++){ dp[i, 0] = display[i+k][0] == '0' ? Math.Min(dp[i, 0],1) : 0; for(int j=1; j<w; j++){ dp[i, j] = display[i+k][j] == '0' ? Math.Min(dp[i, j], dp[i, j-1]+1) : 0; } } int[] hist = new int[310]; for(int i=0; i<h-k; i++){ for(int j=0; j<w-1; j++){ hist[dp[i, j]] += (dp[i, j] >= 1 && dp[i, j+1] == 0) ? 1 : 0; } if(dp[i, w-1] >= 1)hist[dp[i, w-1]]++; } int sum = 0; for(int i=0; i<w; i++){ sum += hist[i+1]; table[k+1, 1] += (i+1) * hist[i+1]; } for(int i=2; i<w+1; i++){ table[k+1, i] = table[k+1, i-1] - sum; sum -= hist[i-1]; } } int n = int.Parse(Console.ReadLine()); for(int k=0; k<n; ++k){ line = Console.ReadLine().Split(' '); int s = int.Parse(line[0]); int t = int.Parse(line[1]); Console.WriteLine(table[s, t].ToString()); } } }
C#: paiza事務局作成コード Vol.2 O(H^2W^2)
得点:71点
通過テストケース数:5/7
using System; class Program { public static void Main(String[] args) { String[] line = Console.ReadLine().Split(' '); int h = int.Parse(line[0]); int w = int.Parse(line[1]); int[,] sum = new int[h+1, w+1]; for(int i=0; i<h; ++i){ String str = Console.ReadLine(); for(int j=0; j<w; ++j){ sum[i+1, j+1] = sum[i+1, j] + sum[i, j+1] - sum[i, j] + (str[j] == '1' ? 1 : 0); } } int n = int.Parse(Console.ReadLine()); for(int k=0; k<n; ++k){ line = Console.ReadLine().Split(' '); int s = int.Parse(line[0]); int t = int.Parse(line[1]); int cnt = 0; for(int i=s; i<=h; ++i){ for(int j=t; j<=w; ++j){ if(sum[i, j] - sum[i-s, j] - sum[i, j-t] + sum[i-s, j-t] == 0){ ++cnt; } } } Console.WriteLine(cnt.ToString()); } } }
C#: paiza事務局作成コード Vol.1 O(H^3W^3)
得点:42点
通過テストケース数:3/7
using System; class Program { public static void Main(String[] args) { String[] line = Console.ReadLine().Split(' '); int h = int.Parse(line[0]); int w = int.Parse(line[1]); String[] display = new String[h]; for(int i=0; i<h; ++i){ display[i] = Console.ReadLine(); } int n = int.Parse(Console.ReadLine()); for(int k=0; k<n; ++k){ line = Console.ReadLine().Split(' '); int s = int.Parse(line[0]); int t = int.Parse(line[1]); int cnt = 0; for(int y=0; y<=h-s; ++y){ for(int x=0; x<=w-t; ++x){ bool ok = true; for(int i=0; i<s; ++i){ for(int j=0; j<t; ++j){ if(display[y+i][x+j] == '1'){ ok = false; } } } if(ok){ ++cnt; } } } Console.WriteLine(cnt.ToString()); } } }