TopCoder SRM601: WinterAndCandies
ヒストグラムを取って、
- 1の個数
- 1の個数 * 2の個数
- ...
- 1の個数 * 2の個数 * 3の個数 * ... * |type| の個数
の合計を出すだけ。
よく見てみると O(|type|) に落とせますね。
public class WinterAndCandies { public int getNumber(int[] type) { var hist = new int[100]; int ans = 0; foreach (var t in type) { hist[t]++; } for (int k = 1; k <= type.Length; k++) { int sub = 1; for (int i = 1; i <= k; i++) { sub *= hist[i]; } ans += sub; } return ans; } }