SRM356 div2 medium 500pts : AverageProblem 解説

はじめに

SRM356 div2 500pts を部内の練習で解いたところ、面白い問題だった && 人々が辛そうにしてた && 日本語の解説記事が見つからなかったので解説記事を書いてみることにした。

問題概要

0 以上 10 以下の範囲の整数で評価する、評価項目が 1 つ以上あるアンケートを 1 つ以上とった。各アンケート毎に、そのアンケートの評価項目毎の評価の平均を小数第4位で切り捨てたものが与えられる。アンケートに回答した回答者の人数としてありうる人数の最小値を求めよ。

1 ≤ アンケート数 ≤ 50
1 ≤ アンケート毎の項目数 ≤ 50

解法

アンケートの回答者を1人から順に調べ、その人数でアンケートを回答したとき、入力として与えられた平均となるような回答の方法があるかどうかを調べればよい。アンケートの項目ごとにどのような判定を行うべきかを解説する。

判定法

アンケートの回答者を $N$ 人、各人のアンケート項目への評価を $a_{i}$ とすると、アンケートの評価の平均 $E$ は、
$E = \cfrac{\sum_{i=0}^{N-1}a_{i}}{N}$
入力として与えられる平均 $E_{in}$ は小数点以下3桁まででそれ以下の値は切り捨てられている。切り捨てられた値を $r$ として、 $E = E_{in} + r$ と表せる。上の式は
$\sum_{i=0}^{N-1}a_{i} = N \cdot E_{in} + N \cdot r$
と変形でき、右辺を整数にできるか否かを判定する問題となる*1。今回の場合、左辺の値が具体的に何になるかを考慮する必要は無い。右辺を整数にするためには、入力として与えられる平均が表現できる最小の値が $p$ *2、アンケートの参加人数が $N$ 人(定数)であったとき、半開区間 $[N \cdot E_{in} ,\ N \cdot E_{in} + N \cdot p)$ に整数があればよい。 $r$ が $0 \leq r < p$ の範囲の値を取るためである。

計算量

アンケートの数を $Q$ 、アンケート $i$ の項目数を $q_{i}$ 、与えられる平均が表現できる最小の値を $p$ とすると、時間計算量は
$O \left( \cfrac{1}{p} \cdot \sum_{i=0}^{i=Q-1} q_{i} \right)$

実装

上で書いたことを実装すればよい。誤差対策として入力として与えれれる値を1000倍して持っておくとよい。整数であれば剰余演算子を用いれるので、判定を行う部分の実装も楽になる。

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <sstream>
#include <list>
#include <deque>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<long,long> pll;

class AverageProblem {
	public:
	int numberOfParticipants(vector <string> marks) {
		vector<int> ave;
		
		// 入力の受け取り部
		for(int i = 0; i < marks.size(); i++) {
			stringstream sstr(marks[i]);
			string s;
			while(sstr >> s) {
				// 入力を1000倍して, ave に追加する
				int a = 0;
				for(int j = 0; j < s.size(); j++) {
					if(s[j] != '.') {
						a *= 10;
						a += s[j] - '0';
					}
				}
				ave.push_back(a);
			}
		}

		// resはアンケートに答えた人の人数の候補
		int res = 1;
		// このループは1000回を超えて回ることはない
		while(1) {
			bool flg = true;
			for(int i = 0; i < ave.size() && flg; i++) {
				// diff は ave[i] * res 以上の最小の整数との差
				int diff = (1000 - (ave[i] * res) % 1000) % 1000;

				if(diff < res) // 条件成立
					;
				else
					flg = false; // 条件不成立
			}

			// ave のすべての要素に対して条件が成立していれば, その res が答え
			if(flg)
				return res;
			// そうでなければresを増やしてまた調べる
			res++;
		}
	}
};

感想

素直な問題で解いていて面白かった。計算量の見積もりや、アンケートの回答者がN人のとき入力として与えられた平均にできるか否かの判定など、div2med(500pts)の問題としては難しいように感じた。この難易度なら最近のdiv1easy(250pts)でも通用するのではないだろうか。切り捨てた値を適当な文字で表して式変形を進めるという考えに至れれば解け、行う式変形も分母を払う程度で難しくないため、その発想に至れるかどうかが勝負の分かれ目のよう。

無視した値を適当な文字で表すというアイデアに関しては、例えば電気系であれば抵抗の誤差を適当な変数として表して、最終的にどの程度誤差が現れるかを調べるなどの応用が利くので押さえておきたい。

*1:右辺が整数になりさえすれば, 左辺は右辺と一致するように選ぶことができる

*2:うまく表現できてる気がしないが、つまりは $E_{in}$ の精度のこと。今回は0.001

学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

SRM356 div2 medium 500pts : AverageProblem 解説

はじめに

問題概要

解法

判定法

計算量

実装

感想