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

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

3.0.1 数値型

キーポイント

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

問題

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

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

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


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"){

    }
  }