TopCoder SRM 536 Div1 Medium RollingDiceDivOne

悩んだ末、答えがわかればコードは非常に単純な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11797

問題

N個のサイコロがある。
各サイコロは1～dice[i]までの目を等確率で出す。
全サイコロを同時に投げたときの目の合計で、最も出る確率の高い値を答えよ。
ただし、同じ確率の値が複数あるなら、最小値を答えよ。

解法

概ね全サイコロの平均値を足せばいいことは推測がつく。
ただし、同じ確率の値が複数ある場合は、平均値の和より少し小さい値になる場合もある(Example3)。

ここで手が止まったので、後はEditorialを見て解いた。
SRM536 Editorial

まず、各サイコロの値が1～dice[i]だと分かりにくいので、0～(dice[i]-1)と置き換えておく。
最後の値にサイコロ数Nを加算すればつじつまがある。

dice[i]の値が小さいなら、各合計値の頻度を計算できるので、試しに小さな値で実験してみる。
得られるヒストグラムは、明らかに平均値を中心にした線対称なグラフである。
よって通常平均値が最頻値であることがわかる。

平均値が最頻値でないケースとして、dice[i]の最大値が全体の和の半分以上を占める場合がある。
この場合、Editorialにあるとおり最頻値となる合計値の区間がしばらく続く。
この最頻値は(dice[i]-1)の和からdice[i]の最大値を引いた数値から始まる。

class RollingDiceDivOne {
	public:
	long long mostLikely(vector <int> dice) {
		int N=dice.size();
		int i;
		
		FOR(i,N) dice[i]--;
		sort(dice.begin(),dice.end());
		ll sum=0,ma=0;
		FOR(i,N) {
			sum+=dice[i];
			ma=max(ma,(ll)dice[i]);
		}
		
		return N+min(sum/2,sum-ma);
	}
}

まとめ

こんなあっさり解けるとは…。