ARC 060に参加しました

arc060.contest.atcoder.jp

爆死しました。C問題部分点(しかも解いたのかなり遅い)のみでした。
しかもコンテスト終了後10分後にこの問題がACしたのでとてもつらい。メモっておきます。

arc060.contest.atcoder.jp

数字が書かれたn枚のカードがあります。このうち1枚以上使って、平均がaになるようなカードの選び方は何通りあるでしょう。同じカードを複数回選んではいけません、という問題です。

何がつらかったというと、

• カードが最大50枚なので、全部で最大2^50通りあり全通り試していたら間に合わない

• DPを使いたかったが、平均を出すためには和と枚数の情報が必要

いろいろ悩んだ結果、メモ化再帰で解くことにしました。回答はこんな感じです。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    long long int n, a;
    int x[51];
     
    long long int num[60][60][2510];
     
    long long int solve(int restsum, int restcardnum, int selectcardnum)
    {   
        if(restcardnum == 0 && restsum == 0){
            num[selectcardnum][restcardnum][restsum] = 1;
            return 1;
        }
        if(num[selectcardnum][restcardnum][restsum] != -1) return num[selectcardnum][restcardnum][restsum];
        long long int result = 0;
        for(int i = selectcardnum; i <= n; i++){
            if(restcardnum > 0 && restsum >= x[i]) result += solve(restsum - x[i], restcardnum - 1, i + 1);
        }
        num[selectcardnum][restcardnum][restsum] = result;
        // cout << restsum << " " << restcardnum << " " << selectcardnum << " " << result << endl;
        return result;
    }
     
    int main()
    {
        cin >> n >> a;
        long long int xsum = 0;
        for(int i = 1; i <= n; i++){
            cin >> x[i];
            xsum += x[i];
        }
        for(int i = 0; i < 51; i++){
            for(int j = 0; j < 51; j++){
                for(int k = 0; k < 2501; k++){
                    num[i][j][k] = -1;
                }
            }
        }
        long long int ans = 0;
        long long int nownum = a;
        long long int nowcardnum = 1;
        while(nowcardnum <= n && nownum <= xsum){
            ans += solve(nownum, nowcardnum, 1);
            nownum += a;
            nowcardnum++;
        }
        cout << ans << endl;
        return 0;
    }

num[i][j][k]は、i枚目またはi枚目以降を使用してj枚使って和がkになる組み合わせの数になります(名前は適当に決めましたわかりにくくてよくない)。
まず枚数とその和を決定しておきます。枚数をpとしたとき、和がa * pとなるようにすれば平均がaになります。
これを引数として、solve関数を使って枚数とカードの和の条件を満たす組み合わせの数を求めます。
solve関数は、selectcardnum枚目またはそれ以降を使用して、restcardnum枚で和がrestsumになるような組み合わせの数を返します。numを更新しながら再帰で答えを求めていきます。

3次元配列のDPはなかなか難しいなあ。
レートも落ちてしまったのでしょんぼり。次回はわからなくてもとりあえず部分点をとりにがんばります。