【クエリメニュー】指定要素の検索 (query) (paizaランク D)-解答例-PHP編

2022年8月6日

【クエリメニュー】> 【ソートと検索 (query)】STEP: 3 指定要素の検索 (query) (paizaランク D 相当) [難易度: 2117 ±31]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

長さ N の重複した要素の無い数列 A と Q 個の整数 K_1 ... K_Q が与えられるので、
各 K_i について、 A に K_i が含まれていれば "YES" を、そうでなければ "NO" を出力してください。

入力値（例）
5 5
1
2
3
4
5
1
3
5
7
9

出力値（例）
YES
YES
YES
NO
NO

解答例

<?php
    list($n, $q) = explode(" ", trim(fgets(STDIN)));
    
    for ($i = 0; $i < $n; $i++) {
        $value = trim(fgets(STDIN));
        $a[$value] = $value;
    }
    //print_r($a);
    
    for ($i = 0; $i < $q; $i++) {
        $k = trim(fgets(STDIN));
        
        echo (isset($a[$k])) ? "YES" : "NO";
        echo "\n";
    }
?>

<?php

list($n, $q) = explode(" ", trim(fgets(STDIN)));

for ($i = 0; $i < $n; $i++) {

$value = trim(fgets(STDIN));

$a[$value] = $value;

}

//print_r($a);

for ($i = 0; $i < $q; $i++) {

$k = trim(fgets(STDIN));

echo (isset($a[$k])) ? "YES" : "NO";

echo "\n";

}

解説

失敗コード

<?php
    list($n, $q) = explode(" ", trim(fgets(STDIN)));
    
    for ($i = 0; $i < $n; $i++) {
        $a[] = trim(fgets(STDIN));
    }
    
    for ($i = 0; $i < $q; $i++) {
        $k = trim(fgets(STDIN));
        
        echo (in_array($k, $a)) ? "YES" : "NO";
        echo "\n";
    }
?>

<?php

list($n, $q) = explode(" ", trim(fgets(STDIN)));

for ($i = 0; $i < $n; $i++) {

$a[] = trim(fgets(STDIN));

}

for ($i = 0; $i < $q; $i++) {

$k = trim(fgets(STDIN));

echo (in_array($k, $a)) ? "YES" : "NO";

echo "\n";

}

in_array()を用いて配列内に対象の値があるかどうか判別していますが、データ量がかなり多く指定時間に処理できませんでした。

このように、配列を用いてデータを受け取り、繰返しin_array()で判定するとプログラム全体でN*Q回ループを回す必要があります。この問題の条件を見ると、NとQは最大10万ものデータがあるため、最大100億となってしまいます。

テスト4に関しては、16秒もかかっているためタイムオーバーとなってしまいました。

他の方がpythonで解答している内容などでは、in_array()に対応するinという演算子を使ってうまく処理できていました。

データ量が多いときの値検査では、in_array()よりもisset()が有力なようです。テスト4が通らなくて泣きそうになりましたがなんとか通過できて良かったです。(*'ω'*)

解答例

解説

失敗コード

カテゴリー