SRM548 Div1 Medium(450) KingdomAndDice

1番目のダイスと2番目のダイスのラベルのN*N通りの組合わせのうち、1番目ダイスのほうが大きいもの個数をp個とすると、勝率はp/(N*N)。pをN*N/2に近づければ良い。

ラベルの数字に意味は無くて、2番目のダイスのラベルのうち何個に勝てるかが重要。また、同じ勝ち数のラベルが0の個数以上あっても意味が無い。結局、例えば、最初の例{{0, 2, 7, 0}, {6, 3, 8, 10}, 12}は、勝ち数がそれぞれ0, 0, 1, 1, 3, 4, 4のラベルから、2枚を選んで、剥がれていないラベルの勝ち数の総和2と合わせて、N*N/2=8に近づけよ、という問題に帰着できる。

あとは動的計画法。O(N⁵)になりそうだけど、x番目までのラベルを使って、勝ち数の総和をiにするために必要な最小のラベル数を覚えておくことで、O(N⁴)で計算できる。たぶん、このために0のラベルは複数使える問題設定なのだと思う。

#include <vector>
#include <algorithm>
using namespace std;

class KingdomAndDice{public:
double newFairness( vector <int> firstDie, vector <int> secondDie, int X )
{
    int N = (int)firstDie.size();

    //  0の個数
    int zn = (int)count(firstDie.begin(),firstDie.end(),0);

    //  使えるラベル
    //  secondDieに何勝できるかを入れる
    //  同じ勝ち数でzn以上は意味が無いので、最大zn個
    vector<int> L;
    sort(secondDie.begin(),secondDie.end());
    for ( int i=1; i<=N; i++ )
    {
        int c = 0;
        for ( int j=secondDie[i-1]+1; j<=(i<N?secondDie[i]-1:X); j++ )
        {
            if ( count(firstDie.begin(),firstDie.end(),j)==0 )
            {
                L.push_back(i);
                if ( ++c >= zn )
                    break;
            }
        }
    }

    //  firstDieのsecondDieに対する勝ち数の総和
    int w = 0;
    for ( int i=0; i<N; i++ )
        for ( int j=0; j<N; j++ )
            if ( firstDie[i]>secondDie[j] )
                w++;

    //  secondDieに対する勝ち数の和をiにするのに必要な最小のラベル数
    vector<int> T(N*N+1,9999);
    T[w] = 0;
    for ( int i=0; i<(int)L.size(); i++ )
    {
        vector<int> P = T;
        for ( int j=L[i]; j<=N*N; j++ )
            T[j] = min(T[j],P[j-L[i]]+1);
    }

    //  N*N/2に最も近い勝ち数
    int ans = -N*N;
    for ( int i=0; i<=N*N; i++ )
    if ( T[i]<=zn )
        if ( abs(i*2-N*N) < abs(ans*2-N*N) )
            ans = i;

    return (double)ans/(N*N);
}};