POH! Vol.1 Perl模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。

【POH Vol.1結果発表】新人女子を最も助けたコードとは?

Perl: paiza事務局作成コード Vol.3 O(DN)

通過テストケース数:3
実行時間(テストケース1):0.02秒
実行時間(テストケース2):0.33秒
実行時間(テストケース3):10.02秒

$line1 = <STDIN>;
@line1 = split(/ /, $line1);
$N = $line1[0];
$D = $line1[1];
@p;
for( $i = 0 ; $i < $N ; $i++)
{
    $p[$i] = <STDIN>;
}
@p = sort { $a <=> $b } @p;
for( $i = 0 ; $i < $D ; $i++ )
{
    $m_j = <STDIN>;
    $ans = 0;
    $flag = 1;
    $s = 0;
    $t = $N - 1;
    while( $s < $t )
    {
        $tmp = $p[$s] + $p[$t];
        if( $tmp > $m_j )
        {
            $t--;
        }
        else
        {
            if( $ans < $tmp )
            {
                $ans = $tmp;
            }
            $s++;
        }
    }
    print "$ans\n";
}

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

通過テストケース数:2
実行時間(テストケース1):0.22秒
実行時間(テストケース2):6.38秒
実行時間(テストケース3):--

$line1 = <STDIN>;
@line1 = split(/ /, $line1);
$N = $line1[0];
$D = $line1[1];
@p;
for( $i = 0 ; $i < $N ; $i++)
{
    $p[$i] = <STDIN>;
}
@p = sort { $a <=> $b } @p;
for( $i = 0 ; $i < $D ; $i++ )
{
    $m_j = <STDIN>;
    $ans = 0;
    for( $j = 0 ; $j < $N ; $j++ )
    {
  $r = $m_j - $p[$j];
  $lb = 0, $ub = $N;
  while( $ub - $lb != 1 )
  {
      $mid = int(($ub + $lb) / 2);
      if( $p[$mid] <= $r )
      {
    $lb = $mid;
      }
      else
      {
    $ub = $mid
      }
  }
  $ub--;
  if( $j >= $ub )
  {
      next;
  }
  if( $p[$ub] > $r )
  {
      next;
  }
  $tmp = $p[$j] + $p[$ub];
  if( $tmp <= $m_j && $ans < $tmp )
  {
      $ans = $tmp;
  }
    }
    print "$ans\n";
}

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

通過テストケース数:1
実行時間(テストケース1):6.46秒
実行時間(テストケース2):--
実行時間(テストケース3):--

$line1 = <STDIN>;
@line1 = split(/ /, $line1);
$N = $line1[0];
$D = $line1[1];
@p;
for( $i = 0 ; $i < $N ; $i++)
{
    $p[$i] = <STDIN>;
}

for( $i = 0 ; $i < $D ; $i++ )
{
    $m_j = <STDIN>;
    $ans = 0;
    for( $j = 0 ; $j < $N ; $j++ )
    {
  for( $k = $j + 1 ; $k < $N ; $k++ )
  {
      $tmp = $p[$j] + $p[$k];
      if( $tmp > $m_j )
      {
    next;
      }
      if( $ans < $tmp )
      {
    $ans = $tmp;
      }
  }
    }
    print "$ans\n";
}
ページの先頭へ戻る