POH! Vol.2 C#模範解答

こちらでは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());
    }
  }
}
ページの先頭へ戻る