📝

AtCoder Beginner Contest 349 C - Airport Code 覚書き PHP

2024/04/16に公開

競技プログラミング

PHPで解答を作成しています。

解のポイント

計算量を少なくするためには？
→文字列の左端から照合しわかった時点で処理を終了させる
→アルゴリズム貪欲法

貪欲法とは
全ての選択肢を考えると選択肢の組み合わせが爆発的に増えていく
→ 「後先のことを考えず、その場その場での選択を繰り返していく」
→　これが貪欲法

これって人生での選択についてもためになる考え方だと少し感動。
でもなんで貪欲法という名前？

調べてみた
将来的な影響を考慮せずに、現時点で最善の選択をし続けるアプローチ方法。
この「貪欲に」という言葉が示すように、貪欲法は短絡的で短期的な利得を最大化することを目指します。最終的な最適解を保証するわけではありませんが、場合によっては最適解または最適解に近い解を見つけることができる。

↓
将来的な影響も考える場合は「動的計画法」などのアプローチが必要

今回の場合は、１回のチェックのみでＯＫ。その後に条件が変化していくといった問題ではないため貪欲法でOKなのではないか。
※あとで動的計画法についても調べてみる

と思ったらPaizaの中にあったわ。やる。

参考ページ
https://algo-method.com/descriptions/95

使用する関数/演算子

&&
&&: 演算子の両側が true の場合に限り、結果が true となる。

strtoupper
文字列を大文字に変換する。

strlen
文字列の長さを取得する。

三項演算子（条件演算子）
条件式を評価し、trueであれば式1、falseでれば式2を返します。

<?php
"条件式" ? "式1" : "式2";

三項演算子について。
if文との使い分けに迷ったので調査。

処理速度…if文の方が少しだけ早いかも？
可読性…三項演算子は処理を読み取りにくいので嫌う人が多いという話あり。

ただReactでは頻出の演算子なので慣れておく方が良さそう。

全体コード

<?php

$S = strtoupper(trim(fgets(STDIN)));// 取得して大文字化
$T = trim(fgets(STDIN));// 空港コード


// 文字列 $T の各文字が文字列 $S の中に含まれるかどうかをチェックし、含まれる場合は true、含まれない場合は false を返します。

function check($S, $T)
{
  $i = 0;// ループカウンター初期化で0
  $len_S = strlen($S);// 文字列の長さを取得
  // ここから$Tが$S内の文字として存在するかをチェックするfor文
  for ($j = 0; $j < strlen($T); $j++) {
    $t = $T[$j];// 空港コードの$j番目の文字を$tに格納する
    // $Sの中に$tが存在するかチェック→$Sの文字列の長さまでループ＆$Sの$i番目の文字が$tでない間、$iをインクリメントしていく、つまり見つかったらループを抜けるので計算量が減る
    while ($i < $len_S && $S[$i] != $t) {
      $i++;
    }
    // $iが$Sの文字列の長さと等しくなった時は$Sの文字列の中に$Tがなかったという事なのでfalseを返して関数を抜ける
    if ($i == $len_S) {
      return false;
    }
    // $t が $S 内に見つかった場合に実行され、次の文字を探すために $i をインクリメントする
    $i++;
  }
  // ループを抜けた場合( $T の全ての文字が $S 内に見つかった場合)に実行され、true を返します。
  return true;
}



if (substr($T, -1) != "X") {// もし最後の数がXでない場合
  $result = check($S, $T);
} else {
  // 最後の文字がXの場合、最後の文字を取り除いた文字列でチェックを行う
  $result = check($S, substr($T, 0, -1));
}

echo ($result ? "Yes" : "No");

AtCoder Beginner Contest 349 C - Airport Code 覚書き PHP

解のポイント

使用する関数/演算子

全体コード

参考情報

Discussion