0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@tomosu_engine(Tomotaka Aragaki)

AtCoder Programming Guide for beginners(APG4b)をPHPで解く 2章

0
Last updated at Posted at 2020-04-10

2.01 ループの書き方と範囲for文

for文

ループを書く時の3ステップ

  1. ループを使わずに書く
  2. パターンを見つける
  3. ループで書き直す

愚直に結果を出して見て、そこからアルゴリズムを見出す。

範囲for文

配列の全ての要素に対して何かしらの処理を行いたいとき、phpの場合は、foreach()を使うと良い。

ループ構文の使い分け

  • 配列の全ての要素に対する処理を行う場合 → foreach文
  • それ以外で一定回数繰り返し処理をする場合 → for文
  • それ以外の場合 → while文 (繰り返す回数が決まっていない時)

Ex.16

fgets()は、改行コード(\n)まで読み込んでしまうので、見えない文字列（改行コード、スペースなど）に気をつける。

Ex.16
<?php
  $a = explode(" ", fgets(STDIN));
  $count = 0;
  for ($i=0; $i<count($a)-1; $i++){
    if ((int)$a[$i] == (int)$a[$i+1]){
      $count++;
    }
  }
  if ($count > 0){
    echo "YES\n";
  } else {
    echo "NO\n";
  }
?>

2.02 多重ループ

  • ループ公文の中にさらにループ構文があるものを多重ループという。
  • 多重ループを一度抜けたい場合は、フラグ変数を用意してそれぞれのループを抜けるようにする必要がある。

Ex.17

Ex.17

<?php
  fscanf(STDIN,"%d %d", $n,$s);
  $a = explode(" ", trim(fgets(STDIN)));
  $p = explode(" ", trim(fgets(STDIN)));
  $count = 0;
  for($i=0; $i<$n; $i++){
    for($j=0; $j<$n; $j++){
      if($a[$i] + $p[$j] == $s){
        $count++;
      }
    }
  }
  echo $count."\n";
?>

2.03 多次元配列

  • 2次元の表を扱う時に便利。
  • $array = [ [],[],[] ]のようにして作ることができる。
  • $array[i][j]で、i行目j列目へアクセスできる。
  • $count($array)で縦の大きさを取得できる。
  • $count($array[0])で横の大きさを取得できる。

Ex.18

Ex.18
<?php
  fscanf(STDIN,"%d %d", $n,$m);
  $game = [];
  if($m == 0){
    echo "-\n";
    exit;
  }
  for($i=0; $i<$m; $i++){
    fscanf(STDIN,"%d %d", $a,$b);
    $game[] = [$a,$b];
  }
  for($x=0; $x<$n; $x++){
    for($y=0; $y<$n; $y++){
      for($z=0; $z<$m; $z++){
        if($x == $game[$z][0]-1 && $y == $game[$z][1]-1){
          echo "o";
          break;
        }else if($y == $game[$z][0]-1 && $x == $game[$z][1]-1){
          echo "x";
          break;
        }else if($z == $m-1){
          echo "-";
        }
      }
      if ($y != $n-1){
        echo " ";
      }
    }
    echo "\n";
  }
?>

2.04 参照

PHPでは、「&」をつけることで参照渡しができる。

example
$参照の名前 = &$参照先
$参照の名前 =& $参照先

参照渡しと値渡しの違い

「値渡し」は、変数に代入した値の"コピー"を渡す。

値渡し
$value = 1;
$result = $value; // 1をコピーして代入

「参照渡し」は、変数に代入した値の"参照先"を渡す。

参照渡し
$value = 1;
$result =& $value; // 値の入れ物を参照先として代入

参照渡しは、変数のコピーではなく変数の参照先、すなわち「メモリアドレス」が渡されるため、元の変数が書き変わってしまう。

サンプル

変数、配列は、$参照の名前 =& $参照先で書くこと参照渡しとなる。

オブジェクトは、もともと参照型なので、「&」をつけなくても参照される。

objectの参照渡し
$a = new stdClass();
$a->property = 1;
$b = $a;　             // オブジェクトを代入
$a->property = 3;    // オブジェクトaを変更

var_dump($b);

# 結果
stdClass Object
(
    [property] => 3
)

オブジェクトを参照させたくない場合は、「clone」を使うことで値渡しにすることができる。

objectの値渡し
$a = new stdClass();
$a->property = 1;
$b = clone $a;　      // cloneをつけて代入
$a->property = 3;    // オブジェクトaを変更

var_dump($b);

# 結果
stdClass Object
(
    [property] => 1
)

参照渡しは関数の引数として使用されることもある。
（引数の変数名に&をつける。）

参照渡しの利点

  • 関数の結果を複数返したいとき
  • 無駄なコピーを減らすことができる

Ex.19

Ex.19
<?php
  function saiten(&$A, &$correct_count, &$wrong_count){
    for($i=0; $i<9; $i++){
      for($j=0; $j<9; $j++){
        $ans = ($i+1)*($j+1);
        if($A[$i][$j] != $ans){
          $A[$i][$j] = $ans;
          $wrong_count++;
        }else{
          $correct_count++;
        }
      } 
    }
  }

  function main(){
    $A = [];
    for($i=0; $i<9; $i++){
      $a = explode(" ",trim(fgets(STDIN)));
      $A[] = $a;
    }
    
    $correct_count = 0; //ここに正しい値のマスの個数を入れる
    $wrong_count = 0;   //ここに誤った値のマスの個数を入れる
    
    saiten($A, $correct_count, $wrong_count);
    
    //正しく修正した表を出力
    for($i=0; $i<9; $i++){
      for($j=0; $j<9; $j++){
        echo $A[$i][$j];
        if($j<8){echo " ";}
        else{echo "\n";}
      }
    }
    echo $correct_count."\n";
    echo $wrong_count."\n";
  }
  main();
?>

2.05 再帰関数

再帰は繰り返し処理を行う方法の一つ。
再帰とは、「ある関数の中で同じ関数を呼び出す」こと。また、このような関数を再帰関数という。

再帰関数の例 「0からnまでの総和を計算する関数」

example

function sum($n){
  if($n==0){
    return 0;
  }
  // 関数sumの中で関数sumを呼び出している。
  $s = sum($n-1);
  return $s + $n;
}  
echo sum(3)."\n";

# 結果
6

再帰関数の性質

再帰関数の内容は大きく2つ

  • ベースケース : 再帰呼び出しを行わずに完了できる処理
  • 再帰ステップ : 再帰呼び出しを行い、その結果を用いて行う処理。

再帰関数が正しく動作するためには、
「再帰呼び出しの連鎖に終わりがある」
ことが条件である。

言い換えると、
「再帰ステップでの再帰呼び出しを繰り返すうちに必ずベースケースに到達する」
ということになる。
（この条件を満たさない場合、無限ループになる。）

再帰関数の実装法

  1. **「引数」「返り値」「処理内容」**を決める
    「処理内容」は「返り値」を計算するという内容になる。

  2. 再帰ステップの実装
    「具体的にどのような再帰呼び出しを使って処理を実現できるのか」を考える。
    「処理内容」を実装するために、「引数を変えて再帰呼び出しした結果」を利用できないかを考える。

  3. ベースケースの実装（再帰呼び出しを行わすに完了できる処理）
    ベースケースをif文を場合わけして、処理を実装する。
    適当な引数を与えた時に、再帰ステップでの再帰呼び出しが最終的にベースケースに到達することを確認しておく。

例題 報告書の伝達時間

例題
<?php
  function complete_time(&$children, $x){
    if(count($children[$x]) == 0){
      return 0;
    }
  
    $max_receive_time = 0;
    foreach($children[$x] as $c){
      $receive_time = complete_time($children, $c)+1;
      $max_receive_time = max($max_receive_time, $receive_time);
    }
    return $max_receive_time;
  }
  
  function main(){
    $N = trim(fgets(STDIN));
    $p = explode(" ",fgets(STDIN));
    array_unshift($p,-1);
    
    $children = [];
    for($i=0; $i<$N; $i++){
      $children[] = [];
    }
    for($i=1; $i<$N; $i++){
      $parent = $p[$i];
      $children[$parent][] = $i;
    }
    echo complete_time($children,0)."\n";
  }
  main();
?>

Ex.20

Ex.20
<?php
  function count_report_num(&$children, $x, &$reports){
    if(count($children[$x]) == 0){
      return $reports[$x] = 1;
    }  
    $give = 1;
    foreach($children[$x] as $c){
      $give += count_report_num($children, $c ,$reports);
    }
    $reports[$x] = $give;
    return $give;
  }
  
  function main(){
    $N = trim(fgets(STDIN));
    $p = explode(" ",trim(fgets(STDIN)));
    array_unshift($p,-1);
    
    $children = [];
    for($i=0; $i<$N; $i++){
      $children[] = [];
    }
    for($i=1; $i<$N; $i++){
      $parent = $p[$i];
      $children[$parent][] = $i;
    }
    $reports = array();
    for ($i=0; $i<$N; $i++) $reports[] = -1;
    count_report_num($children,0,$reports);
    for ($i=0; $i<$N; $i++) {
      echo $reports[$i]."\n";
    }
  }
  main();
?>

2.06 計算量

アルゴリズム

ある処理を行うプログラムを作成するときに、どのような計算量を行なっていくかという計算手順のことをアルゴリズムという。

例：1から100までの総和を計算

[アルゴリズムA]
$$1+2+3+...+100 （順番に足していく）$$

このアルゴリズムでは、99回の足し算が必要。

[アルゴリズムB]
$$\frac{100 \times (1+100)}{2}$$

このアルゴリズムでは、足し算、掛け算、割り算の計3回の計算で求められる。

断然アルゴリズムBの方が処理が早い。
すなわち計算量が少ない!

計算時間と記憶領域

  • 計算量 : 必要な計算時間や必要な記憶領域の量が、入力に対してどれくらい変化するかを示す指標。
    • 時間計算量 : 「プログラムの実行に必要な計算のステップ数が入力に対してどのように変化するか」という指標。計算ステップ数とは、四則演算や数値の比較などの回数。
    • 空間計算量 : 「プログラムの実行に必要なメモリの量が入力に対してどのように変化するか」という指標。

計算量メモ
$$2^N > N^2$$

O(logN)

log_x Nは、「xを何乗したらNになるか」を示す。

例 : 長さが8の棒を長さが1になるまで半分に切る(2で割る)ことを繰り返した時に切る回数はlog_2 8回になる。

計算量の大まかな大小

$$0(1)<O(logN)<O(N)<O(NlogN)<O(N^2)<O(2^N)$$

N 0(1) O(logN) O(N) O(NlogN) O(N^2) O(2^N)
1 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
10 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
1000 一瞬 一瞬 一瞬 一瞬 0.01秒くらい 終わらん
10^6 一瞬 一瞬 0.01秒くらい 0.2秒くらい 3時間くらい 終わらん
10^8 一瞬 一瞬 1秒くらい 30秒くらい 3年くらい 終わらん
10^16 一瞬 一瞬 3年くらい 170年くらい 終わらん 終わらん

Ex.21

phpで出すと、TLEになっちゃう。

<?php
  function f0($N){
    return 1;
  }

  function f1($N,$M){
    $s = 0;
    for ($i=0; $i<$N; $i++){
      $s++;
    }
    for ($i=0; $i<$M; $i++){
      $s++;
    }
    return $s;
  }

  function f2($N){
    $s = 0;
    for ($i=0; $i<$N; $i++){
      $i = $N;
      $cnt = 0;
      while ($t > 0){
        $cnt++;
        $t /= 2;
      }
      $s += $cnt;
    }
    return $s;
  }

  function f3($N){
    $s = 0;
    for ($i=0; $i<3; $i++){
      for ($j = 0; $j < 3; $j++) {
        $s++;
      }
    }
    return $s;
  }

  function f4($N){
    $s = 0;
    for ($i = 0; $i < $N; $i++) {
      for ($j = 0; $j < $N; $j++) {
        $s += $i + $j;
      }
    }
    return $s;
  }

  function f5($N,$M){
    $s = 0;
    for ($i = 0; $i < $N; $i++) {
      for ($j = 0; $j < $M; $j++) {
        $s += $i + $j;
      }
    }
    return $s;
  }

  function main(){
    fscanf(STDIN,"%d %d",$N,$M);
    $a0 = -1;
    $a1 = -1;
    $a2 = -1;
    $a3 = -1;
    $a4 = -1;
    $a5 = -1;
    
    $a0 = f0($N);
    $a1 = f1($N,$M);
    $a2 = f2($N);
    $a3 = f3($N);
    #$a4 = f4($N);
    $a5 = f5($N,$M);
    
    echo "f0:".$a0."\n";
    echo "f1:".$a1."\n";
    echo "f2:".$a2."\n";
    echo "f3:".$a3."\n";
    echo "f4:".$a4."\n";
    echo "f5:".$a5."\n";
    
  }
  main();
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?