競プロ典型90問 010 - Score Sum Queries 覚書き PHP
PHPで解答を作成しています。
今回は競プロ典型90問から。難易度★2、300点問題レベルです。
問題のリンク
解法については以下のリンクを参考にしました。ありがとうございます。
解のポイント
合計する値を出すときにアルゴリズムの累積和を使う。
理由
条件ごとに１回ずつ計算した場合、計算量が膨大になってしまうため。
この記事をやってみたい。
類似の問題はこちらの記事を参考にする
考察
累積和を作成するときのポイント
・最初の要素（インデックス0）の値が0である
累積和の計算は前の要素の値に現在の要素の値を加えることで行われるため、最初の要素の値が0でなければ正しい累積和を計算することができない
for ($i = 1; $i <= $N; $i++)が1からスタートもポイント
-
最初の要素の値が0 → これを保持する必要がある
インデックス[0]は残す → 1からスタート -
学籍番号＝インデックスにする
上記２つの理由により、1からスタートする。
なぜarray_fillを使うのか？
理由…
累積和を出す→ 前の累積和に新しい値を足していく → つまり前の累積和が必要
ところが！
最初の要素（インデックス0）には前の要素がない → 困る…！
そこでインデックス0を初期化するためにarray_fillを使用する。
array_fillの$N + 1の理由
累積和の場合、最初のインデックス0が必要なため、配列の数が１つ余計に必要。
インデックス0が必要な理由…
累積和の計算は前の要素の値に現在の要素の値を加えることで行われるため、インデックス0に値0を設定する。その後に配列の値をN個、設定していく。そのため配列の数がN+1となる。
例えば、
使用した関数、演算子
array_fill
配列をあらかじめ指定した値で埋める。
array_fill(int $start_index, int $count, mixed $value): array
リンク
全体コード
<?php
$N = trim(fgets(STDIN));
// 各組での累積和を求める：前処理
// 配列を作成→初期化で0を入れる
$point_array1 = array_fill(0, $N + 1, 0); // 1組の得点配列
$point_array2 = array_fill(0, $N + 1, 0); // 2組の得点配列
for ($i = 1; $i <= $N; $i++) {
list($a, $b) = explode(" ", trim(fgets(STDIN))); // $a: 1組か2組か $b: 得点
if ($a == 1) {
$point_array1[$i] = $point_array1[$i - 1] + $b;
$point_array2[$i] = $point_array2[$i - 1];
} else {
$point_array2[$i] = $point_array2[$i - 1] + $b;
$point_array1[$i] = $point_array1[$i - 1];
}
}
// 質問数を取得
$Q = trim(fgets(STDIN));
for ($j = 0; $j < $Q; $j++) {
list($c, $d) = explode(" ", trim(fgets(STDIN))); // $c: 起点 $d: 終点
$sum1 = $point_array1[$d] - $point_array1[$c - 1];
$sum2 = $point_array2[$d] - $point_array2[$c - 1];
echo $sum1 . " " . $sum2 . "\n";
}
Discussion