SRM 226 DIV1 Hard TestScores

問題 Editorial

問題

いくつかの質問の回答率が与えられる。
このテストの平均点と標準偏差を求めて、回答数から"standardized score"を求めよ
"standardized score" = 1000 + 300 * (回答数 - 平均) / 標準偏差

解答

あまりよくわかってない。
自分は標準偏差を、なんとなくDPをやって求めたらできた。
しかし簡単に(sqrt$ sum [ q * (1-q) | q <- questions])と求められるらしい

コメント

わかってなくてもなんとなくDPできたのはいいと思う。
でも標準偏差くらいの知識はあろうよ…
"standardized score"も式がわからなかったり。ふつうにぐぐったら良かったか

コード

#include <vector>
#include <numeric>
#include <cmath>
#include <cstring>
#define all(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
double dp[55][55];
struct TestScores {
	vector<double> q; int n; double m; int s;
	double rec(int i, int score) {
		if(dp[i][score] == dp[i][score]) return dp[i][score];
		if(i == n) return (score - m) * (score - m);
		double p = q[i];
		return dp[i][score] = p * rec(i+1, score+1) + (1-p) * rec(i+1, score);
	}
	double weightedScore(vector <double> questions, int testScore) {
		q = questions, n = q.size(), m = accumulate(all(q), 0.), s = testScore;
		mset(dp, -1);
		double dev = sqrt(rec(0, 0));
		return 1000 + 300 * ((testScore - m) / dev);
	}
};