ゆらのふなびと

競プロ, Python, C++

yukicoder No.398 ハーフパイプ(2)

yukicoder 場合の数 順列

なんとか時間内に通せてよかった。

問題

No.398 ハーフパイプ(2) - yukicoder

6人の審査員がいる。審査員は1人ごとに、0点以上から100点以下の整数の得点を提示する。提示された6つの得点のうち、最大値と最小値を除いた4人分の平均はXであった。このような6人の採点結果は何通りか？ ただし、審査員はそれぞれ区別されることに注意せよ。

制約

0.00 <= X <= 100.00

X は小数第二位まで与えられる

答えが0通りになるような入力は与えられない

解法

想定解はDPの埋め込みですが、ここでは順列的な考察(?)による数え上げの解法を紹介します。

愚直に列挙すると、1人について0点から100点までの101通りなので、全てで 101^6 \sim 10^{12} 通りあります。これを陽に列挙することは難しいので、効率化しなければなりません。そこで、採点結果に登場する数の組み合わせを考え、その組み合わせを各審査員に割り当てる方法の数を足し上げるという戦略を取ることにします。ここで、採点結果に登場する数の組み合わせとは、以下の条件を満たす組 \{a_0, a_1, a_2, a_3, a_4, a_5\} のことです。

0 \leq a_0 \leq a_1 \leq a_2 \leq a_3 \leq a_4 \leq a_5 \leq 100, a_i は整数 (i = 0..5) \cdots (1)

まず、最小値と最大値を除く4つの数 (a_1, a_2, a_3, a_4) に注目します。題意より a_1 + a_2 + a_3 + a_4 = 4x \cdots (2) です。4重ループを回せば 条件(1), (2)を満たす a_1, a_2, a_3, a_4 を全列挙できます。これだと計算回数は 101^4 \sim 10^8 回となり若干怪しいですが、条件(2)より a_1, a_2, a_3 が決まれば a_4 は O(1) で求まるので、実際は計算回数 101^3 \sim 10^6 で済みます*1。 a_1, a_2, a_3, a_4 が決まると、 a_0 と a_5 は 0 \leq a_0 \leq a_1, a_4 \leq a_5 \leq 100 を満たせばなんでもよいということがわかります。

次に、組 \{a_0, a_1, a_2, a_3, a_4, a_5\} を審査員に割り当てる方法を考えます。例えば \{2, 4, 4, 5, 7, 7\} なら、同じものを含む順列の考え方により 6! / 2!2! 通りとなります。分子は 6! で一定ですが、分母は同じ数がいくつずつあるかによって変わります。つまり分母は「 a_0 と a_1 が等しいか」「 a_4 と a_5 が等しいか」に依存するので、これらによって場合分けをすればよいです。具体的な式はコードを見てください。

ちなみに、順列の数え上げはサイズが小さければnext_permutationに配列を渡してループ回数を数えるという方法でも良いです(yosupoさんのコードから学んだ)。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

int fact[] = {1, 1, 2, 6, 24, 120, 720};

int perm(map<int, int> cnt, int x1, int x2) {
    if (x1 != -1) cnt[x1]++;
    if (x2 != -1) cnt[x2]++;
    int ret = fact[6];
    for (auto&& p : cnt) {
        ret /= fact[p.second];
    }
    return ret;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    double x;
    cin >> x;
    int sm = 4 * x;

    const int MAX = 100;
    int ans = 0;
    rep(a1, MAX + 1) {
        rep2(a2, a1, MAX + 1) {
            rep2(a3, a2, MAX + 1) {
                int a4 = sm - a1 - a2 - a3;
                if (!(a3 <= a4 && a4 <= MAX)) continue;
                map<int, int> cnt;
                cnt[a1]++;
                cnt[a2]++;
                cnt[a3]++;
                cnt[a4]++;
                if (a1 != 0 && a4 != MAX)   ans += perm(cnt, -1, -1) * a1 * (MAX - a4);
                if (a4 != MAX)              ans += perm(cnt, a1, -1) * (MAX - a4);
                if (a1 != 0)                ans += perm(cnt, a4, -1) * a1;
                ans += perm(cnt, a1, a4);
            }
        }
    }

    cout << ans << endl;
}

*1:yukicoderなら108でも十分通るので4重ループで書いてもよかった