POH! Vol.2 PHP模範解答

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

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

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

<?php
  fscanf(STDIN, '%d %d', $H, $W);
  $display = array(array());
  for($i = 0; $i < $H; $i++){
    fscanf(STDIN, '%s', $s);
    for($j = 0; $j < $W; $j++){
      $display[$i][$j] = $s[$j] == '0' ? 0 : 1;
    }
  }
  $table = array(array());
  for($i = 0; $i < 310; $i++)for($j = 0; $j < 310; $j++)$table[$i][$j] = 0;
  $dp = array(array());
  for($i = 0; $i < 310; $i++)for($j = 0; $j < 310; $j++)$dp[$i][$j] = 100100100;

  for($k = 0; $k < $H; $k++) {
    for($i = 0; $i < $H-$k; $i++){
      $dp[$i][0] = $display[$i+$k][0] == 0 ? min($dp[$i][0], 1) : 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;
      }
    }
    $hist = array();
    for($i = 0; $i < 310; $i++)$hist[$i] = 0;
    for($i = 0; $i < $H-$k; $i++){
      for($j = 0; $j < $W-1; $j++){
        if($dp[$i][$j+1] == 0 && $dp[$i][$j] > 0){
          $hist[$dp[$i][$j]]++;
        }
      }
      if($dp[$i][$W-1] > 0){
        $hist[$dp[$i][$W-1]]++;
      }
    }

    $total = 0;
    for($i = 0; $i < $W; $i++) $total += $hist[$i+1];
    for($i = 0; $i < $W; $i++) $table[$k+1][1] += ($i+1)*$hist[$i+1];
    for($i = 2; $i < $W+1; $i++) {
      $table[$k+1][$i] += $table[$k+1][$i-1] - $total;
      $total -= $hist[$i-1];
    }
  }

  fscanf(STDIN, '%d', $N);
  for($i = 0; $i < $N; $i++) {
    fscanf(STDIN, '%d%d', $S, $T);
    print($table[$S][$T]."\n");
  }
?>

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

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

<?php
  fscanf(STDIN, '%d %d', $H, $W);
  $display = array(array());
  for($i = 0; $i < 310; $i++)for($j = 0; $j < 310; $j++)$display[$i][$j] = 0;
  for($i = 0; $i < $H; $i++){
    fscanf(STDIN, '%s', $s);
    for($j = 0; $j < $W; $j++){
      $display[$i+1][$j+1] = $s[$j] == '0' ? 0 : 1;
    }
  }

  for($i = 0; $i < $H; $i++)
    for($j = 0; $j < $W; $j++)
      $display[$i+1][$j+1] += $display[$i+1][$j];

  for($j = 0; $j < $W; $j++)
    for($i = 0; $i < $H; $i++)
      $display[$i+1][$j+1] += $display[$i][$j+1];

  fscanf(STDIN, '%d', $N);
  for($_ = 0; $_ < $N; $_++) {
    $cnt = 0;
    fscanf(STDIN, '%d%d', $S, $T);
    for($i = 0; $i < $H-$S+1; $i++)
      for($j = 0; $j < $W-$T+1; $j++) {
        $d = $display[$i+$S][$j+$T] - $display[$i+$S][$j] - $display[$i][$j+$T] + $display[$i][$j];
        if($d == 0) $cnt += 1;
      }
    print($cnt."\n");
  }
?>

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

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

<?php
  fscanf(STDIN, '%d %d', $H, $W);
  $display = array(array());
  for($i = 0; $i < 310; $i++)for($j = 0; $j < 310; $j++)$display[$i][$j] = 0;
  for($i = 0; $i < $H; $i++){
    fscanf(STDIN, '%s', $s);
    for($j = 0; $j < $W; $j++){
      $display[$i][$j] = $s[$j] == '0' ? 0 : 1;
    }
  }

  fscanf(STDIN, '%d', $N);
  for($_ = 0; $_ < $N; $_++) {
    $cnt = 0;
    fscanf(STDIN, '%d%d', $S, $T);
    for($i = 0; $i < $H-$S+1; $i++)
      for($j = 0; $j < $W-$T+1; $j++) {
        $flag = true;
        for($k = 0; $k < $S; $k++)
          for($l = 0; $l < $T; $l++){
            $x = $i + $k;
            $y = $j + $l;
            if($x < $H && $y < $W){
              if(1 == $display[$x][$y]) $flag = false;} else {$flag = false;}
          }
        if($flag)$cnt++;
      }
    print($cnt."\n");
  }
?>
ページの先頭へ戻る