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

# 3.01 数値型

##整数のオーバーフロー

integer型の範囲外の数を指定した場合、代わりにfloatとして解釈される。

```php
<?php
var_dump(PHP_INT_MAX);         // int(9223372036854775807)

$large_number = 9223372036854775807;
var_dump($large_number);                     // int(9223372036854775807)

$large_number = 9223372036854775808;
var_dump($large_number);                     // float(9.2233720368548E+18)

$million = 1000000;
$large_number =  50000000000000 * $million;
var_dump($large_number);                     // float(5.0E+19)
?>
```

##浮動小数点数

浮動小数点数は、次の構文により指定できる。

```php
<?php
$a = 1.234; 
$b = 1.2e3; 
$c = 7E-10;
$d = 1_234.567; // PHP 7.4.0 以降
?>
```

##演習問題

```php:LucasNumber
<?php
  $n = trim(fgets(STDIN));
  $i = 2;
  function lucas($a,$b){
      global $n,$i;
      if($n <= $i){
         return $a+$b;
      }
     $i++;
      return lucas($b,$a+$b);
    }
  $a = 2;
  $b = 1;
  if ($n == 0) echo "2\n";
  else if ($n == 1) echo "1\n";
  else{
    echo lucas($a,$b)."\n";
  }
```

# 3.02 pair/tupleとauto

## Ex.22

```php:Ex.22
<?php
  $n = trim(fgets(STDIN));
  $ab = [];
  $b = [];
  for($i=0; $i<$n; $i++){
    $ab[] = explode(" ",trim(fgets(STDIN)));
    $b[] = $ab[$i][1];
  }
  sort($b);
  for($i=0; $i<$n; $i++){
    for($j=0; $j<$n; $j++){
      if($b[$i] == $ab[$j][1]){
        echo $ab[$j][0]." ".$ab[$j][1]."\n";
        break;
      }
    }
  }
```

# 3.03 STLのコンテナ

##配列

PHPの配列は、整数値/文字列を値と対応させたマップと見なすことがきる。

基本的に`array()`や`[]`で定義すると、連想配列になる。

`SplFixedArray($整数)`を使うと固定長となり、整数値で指定した範囲の添え字しか使用できない。

## ヒープ

「それまでに追加した要素のうち、最も大きいものを取り出す」という処理を行う。

**データを追加したり、取り出したりする時**、要素の追加や削除がO(logN)で済むので、配列でsortしてから取り出すよりも計算量が抑えられる。

## Ex.23

```php:Ex.23
<?php
  $n = trim(fgets(STDIN));
  $a = explode(" ",trim(fgets(STDIN)));
  $b = [];
  for($i=0; $i<$n; $i++){
    $b[$a[$i]] += 1;
  }
  $max = max($b);
  echo array_keys($b,$max)[0]." ".$max."\n";
```

# 3.04 構造体

PHPには、構造体の概念はないが、構造体より便利なClassが存在する。
このClassはメソッドを持つことができる。

# 3.05 ビット演算

- 「0」か「1」の2通りの状態を表現することができるデータの単位を**ビット**という。


## ビット演算

- AND演算
- OR演算
- XOR演算
- NOT演算
- 左シフト演算
- 右シフト演算

## （例題）ビット全探索問題

```php

<?php
  fscanf(STDIN,"%d %d",$n,$k);
  $a = explode(" ",trim(fgets(STDIN)));
  $ans = false;
  for($tmp=0; $tmp<(1<<$n); $tmp++){
    $sum = 0;
    for($i=0; $i<$n; $i++){
      if($tmp>>$i & 1){
        $sum += $a[$i];
      }
    }
    if($sum == $k){
      $ans = true;
    }
  }

  if($ans){
    echo "YES\n";
  }else{
    echo "NO\n";
  }
```

## Ex.25


```php:Ex.25
<?php
  
  function intersection($A, $B){
    return $A & $B;
  }
  
  function union_set($A, $B){
    return $A | $B;
  }

  function symmetric_diff($A, $B){
    return $A ^ $B;
  }

  function subtract($A, $x){
    $A = $A ^ (1<<$x);
    return $A;
  }

  function increment($A){
    $A = $A<<1;
    if($A>>50){
      $A = subtract($A, 50);
      $A = add($A, 0);
    }
    return $A;
  }

  function decrement($A){
    if($A>>0){
      $A = $A>>1;
      $A = add($A, 49);
    }else{
      $A = $A>>1;
    }
    return $A;
  }
  
  function add($S, $x){
    $S = $S | (1<<$x);
    return $S;
  }
  
  function print_set($S){
    $cont = [];
    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(){
    $A = 0;
    $B = 0;
    $n = trim(fgets(STDIN));
    $a = explode(" ",trim(fgets(STDIN)));
    for($i=0; $i<$n; $i++){
      $A = add($A, $a[$i]);
    }
    $m = trim(fgets(STDIN));
    $b = explode(" ",trim(fgets(STDIN)));
    for($i=0; $i<$m; $i++){
      $B = add($B, $b[$i]);
    }

    $command = explode(" ",trim(fgets(STDIN)));
    $com = $command[0];
    $x = 0;
    if(count($command) == 2){
      $x = $command[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文
論理式のチェックが各反復の最初ではなく最後に行われるwhile文。

## goto文
プログラム中の他の命令にジャンプすることができる。

## Ex.26


```php
<?php
  $n = trim(fgets(STDIN));
  $order = [];
  $x = [];
  $vec = [];
  for($i=0; $i<$n; $i++){
    $order = explode(" ",trim(fgets(STDIN))); 
    switch($order[0]){
      case 'int':
        $x[$order[1]] = int_set($order,$x);
        break;
      case 'print_int':
        echo print_int($order,$x)."\n";
        break;
      case 'vec':
        $vec[$order[1]] = vec($order,$vec,$x);
        break;
      case 'print_vec':
        echo print_vec($order,$vec,$x)."\n";
    }
  }

  function int_set ($order, $x){
    $ans = 0;
    $flag=true;
    for($i=3; $i<count($order)-1; $i++){
      if($order[$i] == "-"){
        $i++;
        if(array_key_exists($order[$i],$x)){
          $ans -= $x[$order[$i]];
        }else{
          $ans -= $order[$i];
        }
        continue;
      }else{
        if(ctype_digit($order[$i])){
	      $ans += $order[$i];
        }else{
          $ans += $x[$order[$i]];
        }
      }
    }
    return $ans;
  }

  function print_int ($order,$x){
    $ans = 0;
    for($i=1; $i<count($order)-1; $i++){
      if(ctype_digit($order[$i])){
        $ans += $order[$i];
      }else if($order[$i] == "-"){
        $i++;
        if(ctype_digit($order[$i])){
          $ans -= $order[$i];
        }else{
          $ans -= $x[$order[$i]];
        }
      }else{
        $ans += $x[$order[$i]];
      }
    }
    return $ans;
  }

  function vec($order,$vec,$x){
    $v = [];
    $j=0;
    $flag = true;
    for($i=3; $i<count($order)-2; $i++){
      if($order[$i] == "]"){
        for($i=3; $i<count($order)-1; $i++){
          if(array_key_exists($order[$i],$vec)){
            for($j=0; $j<count($v); $j++){
              if($order[$i-1] == '-'){
                $v[$j] -= $vec[$order[$i]][$j];
              }else{
                $v[$j] += $vec[$order[$i]][$j];
              }
            }
          }
        }
        break;
      }
      if($order[3] == "["){
        $i++;
        if(ctype_digit($order[$i])){
          $v[] = $order[$i];
        }else if($order[$i] == ","){
          continue;
        }else{
          $v[] = $x[$order[$i]];
        }
      }else{
        $com = $vec[$order[3]];
        if($order[$i] == '-'){
          $flag = false;
          continue;
        }
        if(ctype_digit($order[$i])){
          if($flag){        
            $v[] = $com[$j] + $order[$i];
            $j++;
          }else{
            $v[] = $com[$j] - $order[$i];
            $j++;
          }
        }       
      }
    }
    
    return $v;
  }

  function print_vec($order, $vec, $x){
    $flag = true;
    $v = [];
    $j = 0;
    if(count($order) == 3){
      $v = $vec[$order[1]];
    }else{
    for($i=1; $i<count($order)-1; $i++){
      if($order[1] == "["){
        
        if($order[$i] == '-'){
          $flag = false;
          continue;
        }
        
        if(ctype_digit($order[$i])){
          if($flag){
            $v[$j] += $order[$i];
            $j++;
          }else{
            $v[$j] -= $order[$i];
            $j++;
          }
        }else if($order[$i] == "]"){
          $j = 0;
        }
      }else{
        if(array_key_exists($order[$i],$vec)){
          $com = $vec[$order[$i]];
          if($order[$i] == '-'){
            $flag = false;
            continue;
          }
          for($k=0; $k<count($com); $k++){
            if($flag){
              $v[$k] += $com[$k];
            }else{
              $v[$k] -= $com[$k];
            }
          }
          $flag=true;
        }else if(array_key_exists($order[$i],$x)){
          if($flag){
            $v[$j] += $x[$order[$i]];
            $j++;
          }else{
            $v[$j] -= $x[$order[$i]];
            $j++;
          }
        }else{
          if($order[$i] == '-'){
            $flag = false;
            continue;
          }
          if(ctype_digit($order[$i])){
            if($flag){
              $v[$j] += $order[$i];
              $j++;
            }else{
              $v[$j] -= $order[$i];
              $j++;
            }
          }
        }
      }
    }
    }
    echo "[ ";
    for($i=0; $i<count($v); $i++){
      echo $v[$i]." ";
    }
    echo "]";
  }
```