POH! Vol.1 PHP模範解答

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

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

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

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

<?php
fscanf(STDIN, "%d %d", $N, $D);

for($i = 0; $i < $N; $i++) fscanf(STDIN, "%d", $p[$i]);
sort($p);
$len = count($p);

for($_ = 0; $_ < $D; $_++) {
  fscanf(STDIN, "%d", $m_j);
  $h = 0;
  $t = $len - 1;
  $ans = 0;
  while($h != $t) {
    $s = $p[$h] + $p[$t];
    if ($s > $m_j) $t--;
    else {
      if ($ans < $s) $ans = $s;
      $h++;
    }
  }
  echo $ans, "\n";
}
?>

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

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

<?php
fscanf(STDIN, "%d %d", $N, $D);

for($i = 0; $i < $N; $i++) fscanf(STDIN, "%d", $p[$i]);
sort($p);
$len = count($p);

for($_ = 0; $_ < $D; $_++) {
  fscanf(STDIN, "%d", $m_j);
  $ans = 0;
  for($j=0; $j<$N; $j++) {
    $r = $m_j - $p[$j];
    $lb = 0;
    $ub = $N;
    while($ub-$lb!=1){
      $mid = ceil(($ub+$lb)/2);
      if($p[$mid] <= $r){
        $lb = $mid;
      } else {
        $ub = $mid;
      }
    }
    $ub--;
    if($j >= $ub){
      continue;
    }
    if($p[$ub] > $r){
      continue;
    }
    $tmp = $p[$j] + $p[$ub];
    if($tmp <= $m_j && $ans < $tmp){
      $ans = $tmp;
    }
  }
  echo $ans, "\n";
}
?>

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

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

<?php
fscanf(STDIN, "%d %d", $N, $D);

for($i = 0; $i < $N; $i++) fscanf(STDIN, "%d", $p[$i]);
sort($p);
$len = count($p);

for($_ = 0; $_ < $D; $_++) {
  fscanf(STDIN, "%d", $m_j);
  $ans = 0;
  for($j = 0;$j < $N;$j++){
    for($k = 0; $k < $N;$k++){
      $s = $p[$j] + $p[$k];
      if($s <= $m_j && $ans <= $s && $j != $k){
        $ans = $s;
      }
    }
  }
  echo $ans, "\n";
}
?>
ページの先頭へ戻る