【クエリメニュー】点の幅 (paizaランク A)-解答例-PHP編

2022年9月10日

【クエリメニュー】> FINAL問題点の幅 (paizaランク A 相当) [難易度: 1878 ±36]

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

問題文

テストの返却中に暇だった paiza 君は、また 2 人で遊ぶゲームを思いつきました。

「2 人はそれぞれ生徒番号 1 〜 N の全校生徒 N 人の中から生徒番号が連続するように好きな人数の生徒を選ぶ。その選んだ生徒達の得点の幅が大きい方、すなわちその生徒たちの (最高点 - 最低点) の値が大きい方が勝ち、同じだったら引き分け！」

「ただし、このルールだと人を多く選ぶ方が有利になってしまうから、選べる生徒の数はお互い N/2 人以下ね！」

また審判を任されたあなたは、全ての生徒の得点を記録しておくことで、選んだ生徒たちの最小・最大の生徒番号を確認するだけで、その生徒たちの中の (最高点 - 最低点) の値をすぐに求めることができることに気付きました。

学校の生徒数 N と試合の数 K , 各生徒の得点 S_1 ... S_N と、
i 番目の試合で対戦した A と B の 2 人が選んだ生徒の最小の生徒番号と最大の生徒番号が与えられるので、各試合のジャッジをしてください。

入力値（例）
4 2
1
3
2
4
1 2 2 3
1 2 3 4

出力値（例）
A
DRAW

解答例

<?php
    list($n, $k) = explode(" ", trim(fgets(STDIN)));
    
    for ($i=1; $i<$n; $i++) {
        if ($i * $i == $n) {
            $root = $i;
            break;
        }
    }

    for ($i=0; $i<$n; $i++) {
        $s[$i] = trim(fgets(STDIN));
    }

    for ($i=0; $i<$root; $i++) {
        for ($j=0; $j<$root; $j++) {
            if ($j == 0) {
                $range_max[$i] = $s[$i*$root];
                $range_min[$i] = $s[$i*$root];
            } else {
                $range_max[$i] = max($range_max[$i], $s[$i*$root+$j]);
                $range_min[$i] = min($range_min[$i], $s[$i*$root+$j]);
            }
        }
    }
    
    for ($i=0; $i<$k; $i++) {
        list($al, $ar, $bl, $br) = explode(" ", trim(fgets(STDIN)));
        $al--;
        $ar--;
        $amx = $s[$al];
        $amn = $s[$al];
        $anow = $al;

        while ($anow <= $ar) {
            if ($anow%$root == 0 && $anow+$root-1 <= $ar) {
                $amx = max($amx, $range_max[$anow/$root]);
                $amn = min($amn, $range_min[$anow/$root]);
                $anow += $root;
            } else {
                $amx = max($amx, $s[$anow]);
                $amn = min($amn, $s[$anow]);
                $anow++;
            }
        }

        $bl--;
        $br--;
        $bmx = $s[$bl];
        $bmn = $s[$bl];
        $bnow = $bl;

        while ($bnow <= $br) {
            if ($bnow%$root == 0 && $bnow+$root-1 <= $br) {
                $bmx = max($bmx, $range_max[$bnow/$root]);
                $bmn = min($bmn, $range_min[$bnow/$root]);
                $bnow += $root;
            } else {
                $bmx = max($bmx, $s[$bnow]);
                $bmn = min($bmn, $s[$bnow]);
                $bnow++;
            }
        }

        if ($amx-$amn == $bmx-$bmn) {
            $result = "DRAW";
        } elseif ($amx-$amn > $bmx-$bmn) {
            $result = "A";
        } else {
            $result = "B";
        }
    
        echo $result. "\n";
    }
?>

<?php

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

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

if ($i * $i == $n) {

$root = $i;

break;

}

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

$s[$i] = trim(fgets(STDIN));

}

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

for ($j=0; $j<$root; $j++) {

if ($j == 0) {

$range_max[$i] = $s[$i*$root];

$range_min[$i] = $s[$i*$root];

} else {

$range_max[$i] = max($range_max[$i], $s[$i*$root+$j]);

$range_min[$i] = min($range_min[$i], $s[$i*$root+$j]);

}

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

list($al, $ar, $bl, $br) = explode(" ", trim(fgets(STDIN)));

$al--;

$ar--;

$amx = $s[$al];

$amn = $s[$al];

$anow = $al;

while ($anow <= $ar) {

if ($anow%$root == 0 && $anow+$root-1 <= $ar) {

$amx = max($amx, $range_max[$anow/$root]);

$amn = min($amn, $range_min[$anow/$root]);

$anow += $root;

} else {

$amx = max($amx, $s[$anow]);

$amn = min($amn, $s[$anow]);

$anow++;

}

$bl--;

$br--;

$bmx = $s[$bl];

$bmn = $s[$bl];

$bnow = $bl;

while ($bnow <= $br) {

if ($bnow%$root == 0 && $bnow+$root-1 <= $br) {

$bmx = max($bmx, $range_max[$bnow/$root]);

$bmn = min($bmn, $range_min[$bnow/$root]);

$bnow += $root;

} else {

$bmx = max($bmx, $s[$bnow]);

$bmn = min($bmn, $s[$bnow]);

$bnow++;

}

if ($amx-$amn == $bmx-$bmn) {

$result = "DRAW";

} elseif ($amx-$amn > $bmx-$bmn) {

$result = "A";

} else {

$result = "B";

}

echo $result. "\n";

}

解答例

カテゴリー