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で解く 3章

0
Last updated at Posted at 2020-04-13

3.01 数値型

整数のオーバーフロー

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

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

演習問題

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

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

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
  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

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
  $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 "]";
  }
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?