【クエリメニュー】平方分割 (paizaランク B)-解答例-PHP編

2022年9月2日

【クエリメニュー】> FINAL問題平方分割 (paizaランク B 相当) [難易度: 2188 ±43]

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

問題文

paiza くんは、長さ N の整数列 A の区間 A[l_i] ... A[r_i] の最大の要素の値を K 回求めたいのですが、与えられる区間の要素をいちいち全て調べていては時間計算量にして最大で O(NK) かかってしまいます。
そこで、paiza くんは平方分割と言われるアルゴリズムを用いることで、この計算量を減らそうと考えました。
平方分割とは、次のようなアルゴリズムです。

1. 長さ N の配列が与えられたとき、N の平方根を x を求め、配列を長さ x の配列に分割し、それぞれの配列について目的の値を調べておく。
（分割で得られる最後の配列の長さは必ずしも x になるとは限りません）
2. 調べたい区間に完全に含まれている配列についての 1. で求めた値と、その配列以外の部分の値を全て調べて、目的の値を求める。

この問題では、長さ 10,000 の数列 A について手順 2. までやってみましょう。

入力値（例）
3
74769
-62958
6542
-93191
-6767
-5945
65384
-97133
85447
-80479
...
7984 9087
8855 9824
8228 8478

出力値（例）
99983
99983
99948

解答例

<?php
    for ($i=1; $i<10000; $i++) {
        if ($i*$i>=10000) {
          $root = $i;
          break;
        }
    }
    
    $k = trim(fgets(STDIN));
    
    for ($i=0; $i<10000; $i++) {
        $a[$i] = trim(fgets(STDIN));
    }
    
    for ($i=0; $i<$root; $i++) {
        for ($j=0; $j<$root; $j++) {
            if ($j==0) {
                $range_max[$i] = $a[$i*$root];
            } else {
                $range_max[$i] = max($range_max[$i], $a[$i*$root+$j]);
            }
        }
    }
    
    for ($i=0; $i<$k; $i++) {
        $ans = 0;
        list($l, $r) = explode(" ", trim(fgets(STDIN)));
        $l--;
        $r--;
        $ans = $a[$l];
        $now = $l;
    
        while ($now<=$r) {
          if ($now%$root==0 && $now+$root-1 <= $r) {
            $ans = max($ans, $range_max[$now / $root]);
            $now += $root;
          } else {
            $ans = max($ans, $a[$now]);
            $now++;
          }
        }
        echo $ans. "\n";
    }
?>

<?php

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

if ($i*$i>=10000) {

$root = $i;

break;

}

$k = trim(fgets(STDIN));

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

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

}

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

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

if ($j==0) {

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

} else {

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

}

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

$ans = 0;

list($l, $r) = explode(" ", trim(fgets(STDIN)));

$l--;

$r--;

$ans = $a[$l];

$now = $l;

while ($now<=$r) {

if ($now%$root==0 && $now+$root-1 <= $r) {

$ans = max($ans, $range_max[$now / $root]);

$now += $root;

} else {

$ans = max($ans, $a[$now]);

$now++;

}

echo $ans. "\n";

}

解答例

カテゴリー