【PHPで解いてみた】3章 C++入門 AtCoder Programming Guide for beginners (APG4b)

※章を進めるごとに随時更新します。

# 3.0.1 数値型

## キーポイント
* ２つの値を計算する場合は、自動キャストされることがある。
* 方変換は(int)、(string)のような形でする
* PHPのint型の上限はPHP_INT_MAXで確認することが可能です。ちなみに最大はint(9223372036854775807)。


## 問題

```php
<?php

    fscanf(STDIN,"%d",$N);
        $before1 = 2;
        $before_result = 1;


        if($N == 1){
            echo "1\n";
        }else{
            $l_now=0;
            for($i=1;$i<$N;$i++){
                $l_now = $before1+$before_result;
                $before1 = $before_result;
                $before_result = $l_now;
            }
            echo $l_now."\n";
    
        }
        
```

###メモ化再帰を用いた解法

```php
<?php

    fscanf(STDIN,"%d",$N);
        
    $memo = array();
    for($i=0;$i<$N;$i++){
        $memo[$i] = -1;
    }

    

    function ryuka($n,&$memo){
        if($n==1 ){
            return 1;
        }
        if($n==0){
            return 2;
        }

        if($memo[$n-1] != -1){
            return $memo[$n-1];
        }
        
        $memo[$n-1] = ryuka($n-1,$memo)+ryuka($n-2,$memo);
        return $memo[$n-1];
    }

    echo ryuka($N,$memo)."\n";

```

# 3.0.2 pair／tupleとauto
* autoは型を省略できるものだが、PHPではもともと型の宣言は必要ない。
* 複数の値を表すことができるtupleとpairもPHPにはない。複数の値を表すときにはリストを用いる。

##EX22.2つ目の値でソート
```php

<?php
    fscanf(STDIN,"%d",$N);
    for($i=0;$i<$N;$i++){
        $list = explode(" ",trim(fgets(STDIN)));
        $tmp1[0] = $list[1];
        $tmp1[1] = $list[0];

        $pairs_list[] = $tmp1;
    }
    sort($pairs_list);

    var_dump($pairs_list);
    foreach($pairs_list as $pair){
        echo $pair[1]." ".$pair[0]."\n";
    }
        
    
?>
```

# 3.03.STLのコンテナ

集合を扱うのに適した３つのアルゴリズムを以下に記す。

* stack
    * 最後に追加したものが一番優先度が高い。
* queue
    * 最初に追加したものが一番優先度が高い。
* heap（優先度付きqueue）0
    * ヒープは２分木で表現され、親ノードとその子ノードに着目したとき、親ノードは必ず最小になります。データを追加したり参照するときに便利。その都度ソートせずに一部だけソートすればいいので。

##EX23.最頻値
```php
<?php
    fscanf(STDIN,"%d",$N);

    $list_A = explode(" ", trim(fgets(STDIN)));

    sort($list_A);
    $max=0;
    $count=1;
    $before_count = 0;
    $max_value = "";
    $max_tmp=0;


    for($i=0;$i<count($list_A);$i++){
        if($list_A[$i] == $list_A[$i+1]){
            //リストに幾つ要素があるかカウントする
            $count++;
        }else{
            $count=1;
        }
        $max = max($count,$before_count);
        if($count>$max_count){
            $max_count = $count;
            $max_value = $list_A[$i];
        }
        $before_count = $count;
    }




    echo $max_value." ".$max_count."\n";
```

#3.04.構造体

PHPには構造体はないですが、同様の役割を担うクラスがあります。

※構造体はないので割愛します。


# 3.05.ビット演算

##キーポイント
* ビット演算は集合の演算を行ったり、高速な演算が必要な場合に用いられる。
* ビット演算の種類:PHPのビット演算子
    * AND演算: &
    * OR演算: |
    * XOR演算: ^
    * NOT演算: ~
    * 左シフト演算: <<
    * 右シフト演算： >>　※右シフトした際、はみ出した0 or 1は消える。そのため、切り下げになっている。


```php

<?php
  
// これより下は書き換えない


function change_to_bit($a,$b = []){
  $Aset = 0;
  for($i=0;$i<count($a);$i++){
    $Aset = $Aset | (1<<$a[$i]);
  }
  $Bset = 0;
  for($i=0;$i<count($b);$i++){
    $Bset = $Bset | (1<<$b[$i]);
  }
  return [$Aset,$Bset];
}

function intersection($a,$b = []){
  $sets = change_to_bit($a,$b);
  $Aset = $sets[0];
  $Bset = $sets[1];
  $result = $Aset & $Bset;  
  return $result;
  
}

function union_set($a,$b){
  $sets = change_to_bit($a,$b);
  $Aset = $sets[0];
  $Bset = $sets[1];
  return $result = $Aset | $Bset;
}

function symmetric_diff($a,$b){
  $sets = change_to_bit($a,$b);
  $Aset = $sets[0];
  $Bset = $sets[1];
  return $result = $Aset ^ $Bset;
}

function subtract($a,$x){
  $x_element = 0;
  $sets = change_to_bit($a);
  $Aset = $sets[0];
  $x_element = $x_element | (1<<($x));
  $result = $Aset ^ $x_element;
  return $result;
}

function increment($a){
  $sets = change_to_bit($a,$b);
  $Aset = $sets[0];
  $Aset = $Aset<<1;
  if($Aset>>50 & 1){
      $Aset = $Aset | 1;
  }
  return $Aset;
}

function decrement($a){
  $tmp = 1;
  $sets = change_to_bit($a);
  $Aset = $sets[0];
   $Aset = $Aset>>1;
  if($Aset & 1){
    $Aset = $Aset | $tmp <<49;
  }else{
    $Aset = $Aset>>1;
  }
  return $Aset;
}

  


function print_set($S){
  $cont = array();
  for($i=0;$i<50;$i++){
    if($S>>$i & 1){
      $cont[] = $i;
    }
  }
  for($i=0;$i<count($cont);$i++){
    if($i>0){
      echo " ";
    }
    echo $cont[$i];
  }
 echo "\n";
}



function main() {
    fscanf(STDIN,"%d",$N);
    $A = explode(" ",trim(fgets(STDIN)));

    fscanf(STDIN,"%d",$M);
    $B = explode(" ",trim(fgets(STDIN)));


    $enzanshis = explode(" ",trim(fgets(STDIN)));
  $com = $enzanshis[0];
  if ( count($enzanshis) == 2 ){ 
    $x = $enzanshis[1];
  }
 
  if ($com == "intersection") {
    print_set(intersection($A, $B));
  } else if ($com == "union_set") {
    print_set(union_set($A, $B));
  } else if ($com == "symmetric_diff") {
    print_set(symmetric_diff($A, $B));
  } else if ($com == "subtract") {
    print_set(subtract($A, $x));
  } else if ($com == "increment") {
    print_set(increment($A));
  } else if ($com == "decrement") {
    print_set(decrement($A));
  }
}


main();
```

##3.06.その他の機能

##キーポイント
* コンピュータの内部では「文字」を数値として扱っており、文字に対応する数値を文字コードという
* 関数の中で宣言した変数をローカル変数と呼びます。関数の外で宣言した変数はグローバル変数と呼びます。衝突が起こる可能性があるので注意。
* 無名関数
    * 関数明を指定せずに関数を作成できる。
    * コールバックなどのパラメートして使う際に便利
    * 変数へ無名関数を代入する
    * 親のスコープからの変数の引き継ぎ
* do-while文
    * do-whileループは、論理式のチェックが各反復の 最初ではなく最後に行われること以外は、whileループと 全く同じ
    * 最低一回の実行は保証する
* &&と||は左の式から実行し、結果が確定した時点で条件判定処理を中断する
* 条件式 ? 式1 : 式2　trueであれば1、falseなら2を返す。
* gotoは、プログラム中他の命令にジャンプできる

```
<?php
goto a;
echo 'Foo';
 
a:
echo 'Bar';
?>
```

この場合、"Bar"が出力される



## EX25 ２時間やったが解けなかった

```
<?php

fscanf(STDIN,"%d",$N);
//変数を読み取る
function  read_name($a_list){
  return $a_list[1];
}


//整数を計算する //引数はintから始まる式
function calc_int($a_list){
  $sum = 0;
  $name = read_name($a_list);
  foreach($a_list as $val){
    if($val != $name && $val != "=" && $val != ";"){
      $sum += $val;
    }
  }
  echo $sum;
  return $sum;
}

function calc_vec($a_list,$var_dec){
  foreach($a_list as $val){
    if(is_numeric((int)$val)){
      
    }

  }

}

  $var_int = array();
  $var_dec = array();

  for($i=0;$i<$N;$i++){
    $a_list = explode(" ",trim(fgets(STDIN)));

    if($a_list[0] == "int"){
      $name = read_name($a_list);
      $var_int[$name] = calc_int($a_list);
    }


    if($a_list[0] == "vec" ){
      $name = read_name($a_list);
      $var_vec[$name] = calc_vec(var_int, var_vec);
    }


    if($a_list[0] == "print_int"){
      $sum=0;
      foreach($var_int as $val){  //直書きで総和を計算
        $sum +=$val;
      }
      echo $sum."\n";
    }

    if($a_list[0] == "print_vec"){

    }
  }


```