接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderRegularContest107 > AtCoder Regular Contest 107（ARC107）

AtCoder Regular Contest 107（ARC107）

AtCoderRegularContest107 AtCoderRegularContest ARC107 ARC

atcoder.jp

A - Simple Math

式変形を行うと
$ \sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc $
$ = \sum_{a=1}^{A} a \sum_{b=1}^{B} b \sum_{c=1}^{C} c $
$ = ( \frac{A * (1 + A)}{2} \times \frac{B * (1 + B)}{2} \times \frac{C * (1 + C)}{2} )$
となるのでそれぞれの等差数列の和の積が答え
提出コード

void solve(){
    ll A, B, C;
    cin >> A >> B >> C;
    mint a = A, b = B, c = C;
    mint ans = a * (a + 1) / 2 * b * (b + 1) / 2 * c* (c + 1) / 2;
    cout << ans << endl;
}

B - Quadruple

$ a + b - (c + d) = K $となるので$ a + b $ と$ c + d $に分けて考える（Kが負のときは入れ替えて考えればいい）
この時、$ a+ b $ の取る範囲を考えると $ c + d \geq 2$より$ x = K + 2 $が最小で$ 2 \times N $が最大となる
よって$ a + b = x $として$ 2 + K \leq x \leq 2 \times N $を全探索すればいい
この時$ a + b = x $となる$ ( a, b) $の組み合わせの数は$ min(x-1, 2 \times N - x + 1) $となる
$ c + d = y = x - K $の場合も同様に考えればいい
よって各$ x $ について $ min(x-1, 2 \times N - x + 1) \times min(y-1, 2 \times N - y + 1) $ の積が答え
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    ll ans = 0;
    K = abs(K);
    for(int i=K+2;i<=2*N;i++){
        ll x = i;
        ll y = i - K;
        x = min(x-1, 2*N+1-x);
        y = min(y-1, 2*N+1-y);
        ans += x * y;
    }
    cout << ans << endl;
}

C - Shuffle Permutation

行と行をswapした場合、各列には影響を及ぼさない
列と列をswapした場合も同様で、行方向と列方向を独立に考えても良い
行$ (i, j) $がswapできて$ (i, k) $がswapできる時、$ i, j, k $は任意の位置にswapできる
そのため、swapできる行をUnionFindなどで集合として管理をする
各集合において、集合の要素の任意の位置にswapで移動することができるので各集合のサイズの階乗をかけ合わせていけばいい
提出コード

void solve(){
    int n, K;
    cin >> n >> K;
    vector<vector<int>> a(n, vector<int>(n));
    REP(i,n) REP(j,n) cin >> a[i][j];
    UnionFind uf1(n), uf2(n);
    REP(i,n) REP(j,n) if(i != j){
        bool ok = true;
        REP(k,n){
            if(a[i][k] + a[j][k] > K){
                ok = false;
            }
        }
        if(ok) uf1.unite(i, j);
    }
    REP(i,n) REP(j,n) if(i != j){
        bool ok = true;
        REP(k,n) if(a[k][i] + a[k][j] > K) ok = false;
        if(ok) uf2.unite(i, j);
    }
    set<int> st1, st2;
    REP(i,n){
        st1.insert(uf1.root(i));
        st2.insert(uf2.root(i));
    }
    mint ans1 = 1;
    mint ans2 = 1;
    for(auto x : st1) ans1 *= bc.fact(uf1.size(x));
    for(auto x : st2) ans2 *= bc.fact(uf2.size(x));
    cout << ans1 * ans2 << endl;
}

D - Number of Multisets

想定解でupsolve
$ dp[n][k] := $ $ n $個の要素を取った時の総和が$ k $の時の場合の数としてDPをする
1を取る時の遷移は$ 1, \frac{1}{2}, \frac{1}{4}, ... $ から $ n - 1 $個取って、その総和が$ k - 1 $である場合の数となるので、に $ dp[n][k] += dp[n - 1][k - 1] $となる
1を取らない時の場合、$ \frac{1}{2}, \frac{1}{4}, ... $から$ n $個取って、その総和が$ k $である場合の数となる
ここで、全ての値を2倍にすると$ 1, \frac{1}{2}, \frac{1}{4}, ... $から$ n $個取って、その総和が$ 2k $となる場合の数と等しくなるので$ dp[n][k] += dp[n][2k] $となる
よって上記のようにDPをした時の$ dp[N][K] $が答え
初期化として$ dp[0][0] = 1 $
$ n \lt k $ のとき条件を満たさないので$ dp[n][k] = 0 (n \lt k) $
$ n \gt 0 , k = 0 $のときも同様に条件を満たさないので$ dp[n][k] = 0 (n \gt 0 , k = 0) $
となる 提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    vector<vector<mint>> dp(n+10, vector<mint>(n+10));
    vector<vector<bool>> used(n+10, vector<bool>(n+10));
    auto dfs = [&](auto && self, int N, int K) -> mint{
        if(N == 0 and K == 0) return 1;
        if(K > N) return 0;
        if(N > 0 and K == 0) return dp[N][K] = 0;
        if(used[N][K]) return dp[N][K];
        used[N][K] = true;
        mint res = self(self, N-1, K-1) + self(self, N, 2*K);
        return dp[N][K] = res;
    };
    cout << dfs(dfs, n, k) << endl;
}