ABC 262

Thu, May 22, 2025

https://atcoder.jp/contests/abc262

A. World Cup

https://atcoder.jp/contests/abc262/tasks/abc262_a

B. Triangle (Easier)

https://atcoder.jp/contests/abc262/tasks/abc262_b

C. Min Max Pair

https://atcoder.jp/contests/abc262/tasks/abc262_c

D. I Hate Non-integer Number

https://atcoder.jp/contests/abc262/tasks/abc262_d

自力 AC

考えたこと

平均が整数になるということは $k$ 個を選んだとしたら選んだ数の和が $k$ で割り切れるということ
$a_i$ を $k$ で割った余りを求めてそれらから $k$ 個を選んだときの和の余りが $0$ になる組み合わせの数を求めれば良い
dp が使えそう
- $i$ 番目までの要素を見たときに $j$ 個を選んだときの和の余りが $m$ になる組み合わせは dp で求められる
全ての $k$ について求めて足し合わせる
$N \leq 100$ だから $O(N^4)$ でも間に合う

解法

$a_i$ を $d \in [1, N]$ で割った余りを予め求めておいて、その中から $d$ 個を選んだ和を $d$ で割った余りが $0$ となる組み合わせの数を求める。これを全ての $d$ について求めて足し合わせる。

$dp_m(i,j,k)$ を $i$ 番目までの要素を $j$ 個選んだときの和を $m$ で割った余りが $k$ となる組み合わせの数として DP を行う。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    vvll mod(N + 1, vll(N));
    rep2(m, 1, N + 1) rep(i, N) {
        mod[m][i] = A[i] % m;
    }

    mint ans = 0;
    rep2(m, 1, N + 1) {
        vector dp(vector(N + 1, vector(N + 1, vector<mint>(N))));
        rep(i, N) {
            dp[i][0][0] = 1;
        }

        rep2(i, 1, N + 1) {
            rep2(j, 1, N + 1) {
                rep(k, m) {
                    // i 番目の数字を選ばない
                    dp[i][j][k] += dp[i - 1][j][k];

                    // i 番目の数字を選ぶ
                    dp[i][j][k] += dp[i - 1][j - 1][(m - mod[m][i - 1] + k) % m];
                }
            }
        }
        ans += dp[N][m][0];
    }

    cout << ans.val() << endl;
}