LoginSignup
1
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 3 years have passed since last update.

@kumanomi-kumanomi

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

Last updated at Posted at 2020-04-14

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

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

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