【累積和メニュー】区間の数え上げ 1 (paizaランク C)-解答例-PHP編

2022年9月16日

【累積和メニュー】> 【区間の数え上げ】STEP: 1 区間の数え上げ 1 (paizaランク C 相当) [難易度: 1954 ±50]

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

問題文

この問題では、累積和と似たアルゴリズムである「しゃくとり法」について扱います。

しゃくとり法を用いることで、条件を満たす区間の数や、最も長い区間の長さを求めることができます。

この問題集を通してしゃくとり法の問題に触れ、少しずつしゃくとり法に慣れていきましょう。

まずは、問題を見てみましょう。

以下の 10 個の整数からなる数列が与えられます。

1 5 9 1 20 5 3 6 5 4

この数列において、長さが 1 以上で総和が 15 以下の区間がいくつあるか求めてください。

入力値（例）
なし

出力値（例）
与えられた数列において、総和が 15 以下の区間がいくつあるか求めてください。

末尾に改行を入れ、余計な文字、空行を含んではいけません。

解答例

<?php
    $a = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4];
    
    $k = 15;
    $count = 0;
    
    for ($i=0; $i<count($a); $i++) {
        $r = $i+1;
        $sectionSum = 0;
        while ($r < count($a)+1) {
            $sectionSum += $a[$r-1];
            if ($sectionSum > $k) break;
            $r++;
        }
        $count += $r-$i-1;
    }
    echo $count;
?>

<?php

$a = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4];

$k = 15;

$count = 0;

for ($i=0; $i<count($a); $i++) {

$r = $i+1;

$sectionSum = 0;

while ($r < count($a)+1) {

$sectionSum += $a[$r-1];

if ($sectionSum > $k) break;

$r++;

}

$count += $r-$i-1;

}

echo $count;

解答例

カテゴリー