D - 分散 (Variance)
Editorial
/


Time Limit: 0 msec / Memory Limit: 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):
- i -- 値が変化する数列の項の番号。0 ≦ i < N を仮定してよい。
- x -- 値が変化した後の i 番目の項の値。0 ≦ x ≦ 10 000 を仮定してよい。
- 次のパラメータを持つプロシージャ variance(i, j):
- i -- 分散を計算したい区間のはじめの項の番号。 0 ≦ i < N を仮定してよい。
- j -- 分散を計算したい区間の最後の項の番号。 i ≦ j < N を仮定してよい。
例
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回の実行において update と variance が呼び出される回数をそれぞれ 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 行目: 整数 M。M はP+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