POH! Vol.2 Perl模範解答

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

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

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

use List::Util 'min';
$h = 0;
$w = 0;
chomp($line = <STDIN>);
($h, $w) = split/\s+/, $line;
@display;
for ( $i = 0 ; $i < $h ; ++$i )
{
    chomp($display[$i] = <STDIN>);
}
@table;
for ( $i = 0 ; $i < 310 ; ++$i )
{
    for ( $j = 0 ; $j < 310 ; ++$j )
    {
  $table[$i][$j] = 0;
    }
}
@dp;
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 )
    {
  @a = ($dp[$i][0], 1);
  $dp[$i][0] = (substr($display[$i+$k], 0, 1) eq '0') ? min @a : 0;
  for ( $j = 1 ; $j < $w ; ++$j )
  {
      @b = ($dp[$i][$j], $dp[$i][$j-1]+1);
      $dp[$i][$j] = (substr($display[$i+$k], $j, 1) eq '0') ? min @b : 0;
  }
    }
    @hist = (0) x 310;
    for ( $i = 0 ; $i < $h - $k ; ++$i )
    {
  for ( $j = 0 ; $j < $w - 1 ; ++$j )
  {
      if ( $dp[$i][$j+1] == 0 && $dp[$i][$j] >= 1 )
      {
    $hist[$dp[$i][$j]] += 1;
      }
  }
  if ( $dp[$i][$w-1] > 0 )
  {
      $hist[$dp[$i][$w-1]] += 1;
  }
    }
    $sum = 0;
    for ( $i = 0 ; $i < $w ; ++$i )
    {
  $sum += $hist[$i+1];
    }
    for ( $i = 0 ; $i < $w ; ++$i )
    {
  $table[$k+1][1] += ($i+1)*$hist[$i+1];
    }
    for ( $i = 2 ; $i <= $w ; ++$i )
    {
  $table[$k+1][$i] = $table[$k+1][$i-1] - $sum;
  $sum -= $hist[$i-1];
    }
}
chomp( $n = <STDIN> );
for ( $i = 0 ; $i < $n ; ++$i )
{
    chomp( $line = <STDIN> );
    ($s, $t) = split/\s+/, $line;
    print "$table[$s][$t]\n";
}

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

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

$h = 0;
$w = 0;
chomp($line = <STDIN>);
($h, $w) = split/\s+/, $line;
@display;
for ( $i = 0 ; $i < $h ; $i++ ) {
    chomp($f[$i] = <STDIN>);
}
@ss;
for ( $i = 0 ; $i < $h ; $i++ ) {
    for ( $j = 0 ; $j < $w ; $j++ ) {
  $ss[$i+1][$j+1] = ((substr($f[$i], $j, 1) eq '1') ? 1 : 0);
    }
}
for ( $i = 0 ; $i< $h ; $i++ ) {
    for ( $j = 0 ; $j < $w ; $j++ ) {
  $ss[$i+1][$j+1] += $ss[$i+1][$j];
    }
}
for ( $i = 0 ; $i< $h ; $i++ ) {
    for ( $j = 0 ; $j < $w ; $j++ ) {
  $ss[$i+1][$j+1] += $ss[$i][$j+1];
    }
}

chomp($n = <STDIN>);
for ( $k = 0 ; $k < $n ; $k++ ) {
    chomp($line = <STDIN>);
    ($s, $t) = split/\s+/, $line;
    $cnt = 0;
    $ii = $h - $s + 1;
    $jj = $w - $t + 1;
    for ( $i = 0 ; $i < $ii ; ++$i ) {
  for ( $j = 0 ; $j < $jj ; ++$j ) {
      $d = $ss[$i+$s][$j+$t] - $ss[$i+$s][$j] - $ss[$i][$j+$t] + $ss[$i][$j];
      if ( $d == 0 ) {
    $cnt++;
      }
  }
    }
    print "$cnt\n";
}

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

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

$h = 0;
$w = 0;
chomp($line = <STDIN>);
($h, $w) = split/\s+/, $line;
@display;
for ( $i = 0 ; $i < $h ; ++$i )
{
    chomp($display[$i] = <STDIN>);
}
chomp($n = <STDIN>);
for ( $kk = 0 ; $kk < $n ; ++$kk )
{
    chomp($line = <STDIN>);
    ($s, $t) = split/\s+/, $line;
    $cnt = 0;
    $a = $h - $s + 1;
    $b = $w - $t + 1;
    for ( $i = 0 ; $i < $a ; ++$i )
    {
  for ( $j = 0 ; $j < $b ; ++$j )
  {
      if ( substr($display[$i], $j, 1) eq '1' )
      {
    next;
      }
      $flag = 1;
      for ( $ii = 0 ; $ii < $s ; ++$ii )
      {
    for ( $jj = 0 ; $jj < $t ; ++$jj )
    {
        if ( substr($display[$i+$ii], $j+$jj, 1) eq '1' )
        {
      $flag = 0;
      last;
        }
    }
    if ( $flag == 0 )
    {
        last;
    }
      }
      if ( $flag == 1 )
      {
    $cnt = $cnt + 1;
      }
  }
    }
    print "$cnt\n";
}
ページの先頭へ戻る