【クエリメニュー】平方分割のバケット (paizaランク C)-解答例-PHP編

2022年9月1日

【クエリメニュー】> 【平方分割】STEP: 5 平方分割のバケット (paizaランク C 相当) [難易度: 1543 ±31]

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

問題文

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

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

この問題では、長さ 10,000 の数列 A について手順 1. を行ってみましょう。
10,000 の平方根は 100 なので、先頭から 100 要素ずつの最大値を求めましょう。

入力値（例）
74769
-62958
6542
-93191
-6767
-5945
65384
-97133
85447
-80479
...

出力値（例）
99070
99686
97400
98349
98202
95846
97976
98004
96188
96561
...

解答例

<?php
    for ($i=0; $i<10000; $i++) {
        $a[] = trim(fgets(STDIN));
    }
    
    for ($i=0; $i<100; $i++) {
        for ($j=0; $j<100; $j++) {
            if ($j==0) {
                $ans[$i] = $a[$i *100];
            } else {
                $ans[$i] = max($ans[$i], $a[$i*100+$j]);
            }
        }
    }
    
    for ($i=0; $i<100; $i++) {
        printf("%d\n", $ans[$i]);
    }
?>

<?php

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

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

}

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

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

if ($j==0) {

$ans[$i] = $a[$i *100];

} else {

$ans[$i] = max($ans[$i], $a[$i*100+$j]);

}

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

printf("%d\n", $ans[$i]);

}

解答例

カテゴリー