TopCoder SRM601: WinterAndCandies

ヒストグラムを取って、

• １の個数
• １の個数 * ２の個数
• ...
• １の個数 * ２の個数 * ３の個数 * ... * |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;
    }
}