D - 分散 (Variance) 解説 /

実行時間制限: 5 sec / メモリ制限: 64 MB

統計において、データの散らばり度合いを表す数である分散について説明しよう。

数列a[1], a[2], …, a[n]があるとき、

  • a[1]からa[n]までの合計をnで割ったものが平均mである。
  • それぞれのa[k]について、mとの差の二乗を計算し、その合計値をnで割ったものが分散(σ^2)である。

数列上のある区間の分散を計算したい。

課題

ここに数列 A[0], A[1], ... A[N-1]がある。最初に init(N, A) によって A の初期値が与えられる。

次のプロシージャを実装せよ:

  • 次のパラメータを持つプロシージャ init(N, A):
    • N -- 数列の長さ。数列の各項には 0 から N-1 までの異なる整数の番号がつけられている。
    • A -- 数列の各項を表す整数の配列。0 ≦ i < N に対し 1 ≦ A[i] ≦ 10 000 を仮定してよい。
    このプロシージャは最初に update(i, x) または variance(i, j) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
  • 次のパラメータを持つプロシージャ update(i, x):
    • i -- 値が変化する数列の項の番号。0 ≦ i < N を仮定してよい。
    • x -- 値が変化した後の i 番目の項の値。0 ≦ x ≦ 10 000 を仮定してよい。
    このプロシージャは複数回呼び出される。1回の呼び出しは1回の数列の値の変化に対応する。このプロシージャは戻り値を持たない。
  • 次のパラメータを持つプロシージャ variance(i, j):
    • i -- 分散を計算したい区間のはじめの項の番号。 0 ≦ i < N を仮定してよい。
    • j -- 分散を計算したい区間の最後の項の番号。 i ≦ j < N を仮定してよい。
    このプロシージャは複数回呼び出される。それぞれの呼び出しに大して i 番目の項から j 番目の項(両端も含む)までの(j - i + 1)個の値を母集団としたときの分散を戻り値として返す必要がある。小数点以下の値は切り捨てて整数値にして返すこと。

N = 3, A[i] の初期値が

A =  0
12
6

の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後、複数回の update または variance の呼び出しが任意の順番で行われる。以下に呼び出しと正しい戻り値の例を示す:

パラメータ 戻り値
variance(0, 2) 24
variance(1, 2) 9
update(2, 0) なし
variance(0, 2) 32
variance(1, 2) 36
update(1, 11) なし
variance(0, 2) 26

小課題

以下、1回の実行において updatevariance が呼び出される回数をそれぞれ P, Q とする。

小課題 1 (50 点)

  • 1 ≦ N ≦ 1 000
  • 1 ≦ P+Q ≦ 1 000

小課題 2 (50 点)

  • 1 ≦ N ≦ 100 000
  • 1 ≦ P+Q ≦ 100 000

実装の詳細

制限

  • CPU 時間制限: 5 秒
  • メモリ制限: 64 MB
    注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。

インターフェース (API)

  • 実装フォルダ: variance/ (プロトタイプ: variance.zip)
  • 競技者が実装するファイル: variance.cpp
  • 提出ファイルのインターフェース: variance.h
  • 採点プログラムのサンプル: grader.cpp
  • 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
    注意:採点プログラムのサンプルは次の書式の入力を読み込む。
    • 1 行目: N
    • 2 行目: N 個の整数 A[0], A[1], ..., A[N-1] が空白区切りで書かれている。A[i] は数列の i 番目の項の初期値を表す。
    • 3 行目: 整数 MMP+Q に等しい。
    • 4 行目から M+3 行目: 0 ≦ i < M に対し、i+4 行目には3つの整数 T[i], X[i], Y[i] が空白区切りで書かれている。T[i] = 0のとき i 回目に update(X[i], Y[i]) という呼び出しが行われ、T[i] = 1のとき i 回目に variance(X[i], Y[i]) が呼び出されることを表す。
  • 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
    注意:採点プログラムのサンプルは次の書式の出力を書き出す。
    • 1 行目から Q 行目: 0 ≦ i < Q に対し、i+1 行目には i 回目の variance 呼び出しの際に返されるべき戻り値が書かれている。

  • Problem Proposal: qnighy
  • Problem Statement: qnighy

出典

IJPC 2012 Practice