AtCoder Beginner Contest 352 備忘録 PHP

PHPで解いています。

問題はこちら。
https://atcoder.jp/contests/abc352/tasks

A - AtCoder Line

<?php

list($N, $X, $Y, $Z) = explode(" ", trim(fgets(STDIN)));

// 判定
$ans = false;

if($X > $Y && $Y < $Z && $Z < $X){
    $ans = true;
}elseif($X < $Y && $X < $Z && $Z < $Y){
    $ans = true;
}else{
    $ans = false;
}

echo $ans ? "Yes" : "No";

B - Typing

<?php

$S = trim(fgets(STDIN));
$T = trim(fgets(STDIN));

$S = str_split($S);
$T = str_split($T);


// 答えの配列を作成
$ans = array();

$count_t = count($T);// $Tの文字列の長さ

$k = 0;// 文字列Tとの比較は１回目はindex0から始める:初期値0に設定

foreach($S as $char){    
    for($j = $k; $j < $count_t; $j++){
        if($char === $T[$j]){
            $ans[] = $j + 1;
            $k = $j + 1;
            break;
        }
    }
}

sort($ans); // 出力を昇順に並び替える
echo implode(" ", $ans);

C - Standing On The Shoulders

解法のポイント
どんな条件ならば高さが最大になるかを考える

頂上の巨人のみ頭分の長さをプラスされることになる。
高さは、肩までの高さ × N　+　頭の長さ(B - A)
つまり頭と肩の差の最大を求め、最後にプラスすれば良い。

また、肩までの距離をN人分足していく処理は、配列処理の中で一緒にすますことで計算量を抑える。

<?php

$N = trim(fgets(STDIN));

// それまでの最大の差分を記録する配列を作成する
$max_diff = 0;

// 距離を記録する変数を作成する
$distance = 0;

for($i = 0; $i < $N; $i++){
    list($A, $B) = explode(" ", trim(fgets(STDIN)));
    // 差分を出す
    $C = $B - $A;
    // 差分がこれまでの最大の差分より大きければ、最大の差分を更新し順番を格納する
    if($C > $max_diff){
        $max_diff = $C;
    }    
    // 肩までの距離をすべて足していく
    $distance += $A;
}

// 最後に最大の差分（頭の分だけ）を足せばいい
echo $distance + $max_diff . PHP_EOL;