ハーフパイプ(2) [yukicoder 398] - はまやんはまやんはまやん

問題

6要素のある数列があり、その中で最小と最大を（複数あっても）1つずつ取り除く。
残った4要素の平均を取るとXだったとする。
この時、6要素のある数列として正しいものは何通りあるか。

0.00 <= X <= 100.00
ある数列の各要素は0～100の整数

考察

1. まずXから4要素の和sumを求めておこう

2. 数え上げ問題なので「計算」か「DP」
3. 今回は計算でいけそうじゃない？
4. というかうまいこと列挙すればできそうじゃない？

5. 全列挙を考えてみよう
6. 残る4要素を列挙すると101^4通りある -> これは厳しい
7. 4つ全て列挙しなくても和が分かっているので、3要素だけ列挙すれば、残りの1つは一意に定まる -> 101^3通り -> OK
8. つまり、sum = i + j + ii + jj かつ i <= j <= ii <= jj となるように全列挙する

9. あとは各(i,j,ii,jj)に対して、場合の数が求められれば答えられる
10. あと2つの数が必要だが
(最小) <= i
jj <= (最大)
ということが分かる
11. 「(最小) i j ii jj (最大)」を入れ替えてできる場合の数を計算する
12. 普通に6!通りかとも思うが、同じ数が含まれている場合は、(同じ数の個数)!で割る必要がある
13. 数のダブリについて考えると、以下の4つに場合分けして場合の数を計算する必要がある

(1) (最小) < i かつ jj < (最大)
(2) (最小) = i かつ jj < (最大)
(3) (最小) < i かつ jj = (最大)
(4) (最小) = i かつ jj = (最大)

14. これを計算して総和をとれば答え

15. (解説見たらDPの方が楽じゃん…)

実装

http://yukicoder.me/submissions/104246

string s;
typedef long long ll;
//-----------------------------------------------------------------
int fac(int x) { int ret = 1; rep(i, 1, x + 1) ret *= i; return ret; }
//-----------------------------------------------------------------
int main() {
    cin >> s;

    int sum = 0;
    rep(i, 0, s.length()) if (s[i] != '.') sum = sum * 10 + (s[i] - '0');
    sum = sum * 4 / 100;

    ll ans = 0;
    rep(i, 0, 101) rep(j, i, 101) rep(ii, j, 101) {
        int jj = sum - (i + j + ii);
        if (jj < 0 || 100 < jj) continue;
        if (ii > jj) continue;

        int v[4] = { i, j, ii, jj };

        int cnt[4];
        rep(k, 0, 4) cnt[k] = 1;
        int idx = 0;
        rep(k, 1, 4) {
            if (v[k - 1] == v[k])
                cnt[idx]++;
            else {
                idx++;
            }
        }

        ll da;

        da = v[0] * (100 - v[3]) * fac(6);
        rep(k, 0, 4) da /= fac(cnt[k]);
        ans += da;

        da = (100 - v[3]) * fac(6);
        cnt[0]++;
        rep(k, 0, 4) da /= fac(cnt[k]);
        cnt[0]--;
        ans += da;

        da = v[0] * fac(6);
        cnt[idx]++;
        rep(k, 0, 4) da /= fac(cnt[k]);
        cnt[idx]--;
        ans += da;

        da = fac(6);
        cnt[0]++;
        cnt[idx]++;
        rep(k, 0, 4) da /= fac(cnt[k]);
        ans += da;
    }
    cout << ans << endl;
}