21か月前公開・21か月前更新・0 pv・13 min read

青色コーダーが ABC 全問解説する【ABC290】

https://cdn.magicode.io/media/notebox/blob_6RpCx2F

Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）

5 完。G 問題狙ったけど解けそうで解けなかった…。というか、C 問題読み違えなければパフォ +100 くらいはいけそうだった…(´・ω・｀)

A - Contest Result

\displaystyle\sum_{i=1}^M A_{B_i}

を出すだけ。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;

    cin >> n >> m;

    vector<int> a(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0, b; i < m; ++i) {
        cin >> b;
        ans += a[b - 1];
    }

    cout << ans;

    return 0;
}

B - Qual B

K

個目の o まではそのまま出力して、その後はすべて x を出力すればいい。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    string s;

    cin >> n >> k >> s;

    int i, j = 0;
    // K 個目の 'o' まではそのまま出力
    for (i = 0; j < k; ++i) {
        if (s[i] == 'o') ++j;
        cout << s[i];
    }
    // その後は 'x' を出力
    for (; i < n; ++i) cout << 'x';

    return 0;
}

C - Max MEX

要素

[i,i+K)

かと勘違いしてタイムロス…。任意の

K

個だった…(´・ω・｀)

B

は、

A

の順序を保っているらしいけど、

MEX

は順序関係ないので気にしなくてもいい。

K

と

MEX(A)

の大小別に考えてみる。

$K < MEX(A)$ のとき
$0,1, \cdots, MEX(A)-1$ と、任意の $K-MEX(A)$ 個の要素を選んで $B$ としたときが最大となる。答えは、 $MEX(A)$ 。
$K \geq MEX(A)$ のとき
$0,1, \cdots, K-1$ を選んで $B$ としたときが最大となる。答えは、 $K$ 。

よって、答えは、

\min(K,MEX(A))

。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;

    cin >> n >> k;

    vector<bool> num(n);
    for (int i = 0, a; i < n; ++i) {
        cin >> a;
        if(a < n) num[a] = true;
    }

    int ans;  // min(K, MEX(A))
    // MEX(A) を求める。ただし、K <= MEX(A) なら K で打ち切る
    for (ans = 0; ans < k; ++ans) if (!num[ans]) break;

    cout << ans;

    return 0;
}

D - Marking

x

を

(x+1) \bmod N

に更新しなければ、

x

は、

\frac{N}{\text{gcd}(N,D)}

回でループする。
つまり、

0, D \bmod N, \cdots, \left(\frac{N}{\text{gcd}(N,D)}-1\right)D \bmod N, \\ 1, (1+D) \bmod N, \cdots, \left(1+\left(\frac{N}{\text{gcd}(N,D)}-1\right)D\right) \bmod N, \\ \vdots \\ N-1, \cdots, \left(N-1+\left(\frac{N}{\text{gcd}(N,D)}-1\right)D\right) \bmod N

の順に、印をつけることになる。

よって、

(K-1)

を

\frac{N}{\text{gcd}(N,D)}

で割ったときの商を

quot

、余りを

rem

とおくと、答えは、

(quot + rem \times D) \bmod N

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int t;
    int n, d, k;

    cin >> t;

    for (int cases = 0; cases < t; ++cases) {
        cin >> n >> d >> k;
        --k;
        int g = gcd(n, d);
        int rem = k % (n / g), quot = k / (n / g);
        cout << (quot + (ll)rem * d) % n << '\n';
    }

    return 0;
}

E - Make it Palindrome

X

の

i

番目の要素を

X_i

とおく。また、

X

の連続部分列

\{X_L, \cdots, X_R\}

を

X[L,R]

とおく。

f(X)

の値は、

X_i \neq X_{|X|+1-i}

となる

i(\leq \frac{|X|}{2})

の数と等しい。
そのため、

f'(X)=(X_i = X_{|X|+1-i}

となる

i(\leq \frac{|X|}{2})

の数

)

とおくと、

f(X)=\left\lfloor \frac{|X|}{2}\right\rfloor-f'(X)

。

A

の連続部分列

X

における

f'(X)

の総和を考える。

i<j

となる

i,j

について考えると、

X[i,j],X[i-1,j+1], \cdots, X[i-\min(i-1,N-j),j+\min(i-1,N-j)]

において、

j=|X|+1-i

が成立する。
そのため、

X_i=X_j

のとき、

f'(X)

の総和は、

X_i \neq X_j

のときと比べて

\min(i-1,N-j)+1

大きくなる。

すべての

i,j(i < j)

で

X_i \neq X_j

なら、

f'(X)=0

なので、

f'(X)

の総和は、

\sum_{i<j,X_i=X_j} (\min(i-1,N-j)+1)

となる。

ここで、

j

を固定した場合を考える。

j \leq \frac{N}{2}

のとき、

\sum_{i<j,X_i=X_j} (\min(i-1,N-j)+1)=\sum_{i<j,X_i=X_j} i

j > \frac{N}{2}

のとき、

\begin{align*} \sum_{i<j,X_i=X_j} (\min(i-1,N-j)+1)&=\sum_{i \leq N-j,X_i=X_j} i + \sum_{N-j<i<j,X_i=X_j} (N-j+1) \\ &=\sum_{i \leq N-j,X_i=X_j} i + (N-j+1) \sum_{N-j<i<j,X_i=X_j} 1 \end{align*}

であるから、整数の値ごとに

\displaystyle\sum_{i=1}^{j-1} i

などを保持しながら

j

の昇順に求めれば、各

j

における

\displaystyle\sum_{i<j,X_i=X_j} (\min(i-1,N-j)+1)

は、

O(1)

で求められる。

よって、

f'(X)

の総和、ないし、答えは、

O(N)

で求められる。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;

    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    ll ans = 0;
    // floor(|X| / 2) の総和を求める
    for (ll i = 2; i <= n; ++i) {
        ans += i / 2 * (n + 1 - i);
    }

    vector<ll> sum(n + 1);  // 整数の値ごとの Σ i
    // 整数 A_i の sum を加算し、sum を更新
    for (int i = 0; i < n / 2; ++i) {
        ans -= sum[a[i]];
        sum[a[i]] += i + 1;
    }

    vector<ll> num(n + 1);  // 整数の値ごとの Σ 1
    if (n & 1) {
        sum[a[n / 2]] += n / 2 + 1;
        --num[a[n / 2]];
    }
    // 整数 A_i の sum と (n - i) * num を加算し、sum と num を更新
    for (int i = n / 2; i < n; ++i) {
        sum[a[n - 1 - i]] -= n - i;
        ++num[a[n - 1 - i]];
        ans -= sum[a[i]] + num[a[i]] * (n - i);
        ++num[a[i]];
    }

    cout << ans;

    return 0;
}

F - Maximum Diameter

N

頂点の木なので、

\sum X_i =2N-2

である。また、

X_i \leq 2

である

i

の個数を

k

とおくと、

f(X)=k+1

である。

すべての

i

において、

X_i \leq 1

なので、次数

N-2

を

X_i \leq 2

としたい

k

個の頂点に分配することを考える。すると、次数

N-2-k

を

k

個の頂点に、各

0

以上分配することを考えればいい。

頂点の選び方が

{}_N \text{C}_k

通りなので、

X_i \leq 2

である

i

の個数が

k

となる

X

の個数は、

{}_N \text{C}_k \sdot {}_{N-2-k} \text{H}_k \cdot (k+1)

となる。

N \geq 3

のとき、

0<k\leq N-2

なので、答えは、

\sum_{k=1}^{N-2} {}_N \text{C}_k \sdot {}_{N-2-k} \text{H}_k \cdot (k+1)

O(N)(N \leq 10^6)

なので、

T \leq 2 \times 10^5

では間に合わない。

式変形すると、

\begin{align*} \sum_{k=1}^{N-2} {}_N \text{C}_k \sdot {}_{N-2-k} \text{H}_k \cdot (k+1) &= \sum_{k=1}^{N-2} \frac{N!}{k!(N-k)!} \cdot \frac{(N-3)!}{(k-1)!(N-2-k)!} \cdot (k+1) \\ &= N!(N-3)! \sum_{k=1}^{N-2} \frac{1}{(N-k)!(N-k-2)!} \cdot \frac{k+1}{k!(k-1)!} \end{align*}

となる。

j=N-k

と置き換え、

\frac{1}{n!}=0(n<0)

と定義すれば、

\sum_{k=1}^{N-2} \frac{1}{(N-k)!(N-k-2)!} \cdot \frac{k+1}{k!(k-1)!} = \sum_{j+k=N} \frac{1}{j!(j-2)!} \cdot \frac{k+1}{k!(k-1)!}

となり、畳み込める。これを

N=10^6

まで前計算しておけば、

3 \leq N

の答えを

O(1)

で求められる。なお、

N=2

のとき、答えは

1

なので、

2 \leq N \leq 10^6

のときの答えを

O(1)

で求められる。

オーダーは、畳み込みがボトルネックで、

O(N \log N)

。

↓ こんな感じ。

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
    int t, n;
    const int maxN = 1000000;

    cin >> t;

    vector<mint> f(maxN + 1);    // i!
    vector<mint> inv(maxN + 1);  // 1 / i!
    f[0] = 1;
    for (int i = 1; i <= maxN; ++i) f[i] = f[i - 1] * i;
    inv[maxN] = f[maxN].inv();
    for (int i = maxN; i > 0; --i) inv[i - 1] = inv[i] * i;

    vector<mint> conJ(maxN + 1), conK(maxN + 1);
    for (int i = 2; i <= maxN; ++i) conJ[i] = inv[i] * inv[i - 2];
    for (int i = 1; i <= maxN; ++i) conK[i] = (i + 1) * inv[i] * inv[i - 1];

    vector<mint> con = convolution(conJ, conK);
    for (int i = 0; i < t; ++i) {
        cin >> n;
        if (n == 2) cout << 1 << '\n';
        else cout << (f[n] * f[n - 3] * con[n]).val() << '\n';
    }

    return 0;
}

G - Edge Elimination

\displaystyle\sum_{i=0}^{h-1} K^i < x \leq \displaystyle\sum_{i=0}^h K^i

となる深さ

h

の完全部分木 (つまり、深さ

D-h

の頂点を親とする完全部分木) から切り取る場合だけを考えるとダメなのね…。
コーナーケースは以下等。

とはいえ、深さ

0

の頂点を残す場合と残さない場合で、切るべき辺の数が

1

変わるせいで、コーナーケースが現れている気がする…。そうなら、公式解説は、すべての深さの計算してるけど、深さ

D

の木と、深さ

h

の完全部分木だけ計算すればよさそう。オーダーは

D

が

1

個落ちる。

証明してみる。

深さ

m

の完全部分木から、貪欲法で完全部分木を切り取って、連結成分を

X

頂点にするときに、深さ

i

の完全

K

分木を切り取る個数を

d_{m,i}(i<m)

とおく。
また、深さ

m+1

の完全部分木を用いたときに切り取る頂点の数は、深さ

m

の完全部分木を用いたときに切り取る頂点の数より、

(K-1)K^m+1

多い。

すべての $i$ で $d_{m,i} \leq K-1$ を満たすとき
深さ $m+1$ の完全部分木では、深さ $m$ の完全部分木より $(K-1)K^m+1$ 頂点多く切り取るので、深さ $m$ の完全 $K$ 分木を $(K-1)$ 個、深さ $0$ の完全 $K$ 分木を $1$ 個、余分に切り取る必要がある。

よって、

\sum_i d_{m+1,i} = \sum_i d_{m,i} + Ｋ > \sum_i d_{m,i}

ある $i$ が $d_{m,i} = K$ を満たすとき
同様に、深さ $m+1$ の完全部分木では、深さ $m$ の完全部分木より $(K-1)K^m+1$ 頂点多く切り取る必要がある。 $(K-1)K$ 頂点分は、深さ $m$ の完全 $K$ 分木を $(K-1)$ 個切り取るしかない。
しかし、残りの $1$ 頂点は、 $d_{m,i} = K$ を満たす $i$ が存在するため、 $d_{m+1,i+1}=d_{m,i+1}+1, d_{m+1,i}=0$ とすると、 $(\sum_{j=1}^{i+1} K^j - K\sum_{j=1}^i K^j=)1$ 個切り取る頂点を増やせる。

よって、

\sum_i d_{m+1,i} = \sum_i d_{m,i} +(K+1) +1 - K = \sum_i d_{m,i}

上記から、

\displaystyle\sum_i d_{h,i} \leq \displaystyle\sum_i d_{h+1,i} \leq \cdots \leq \displaystyle\sum_i d_{D,i}

を満たす。

ここで、深さ

m

の完全部分木を用いる場合、まず、その完全部分木を切り出すときに

1

回辺を切る必要があるが、元々の深さ

D

を用いる場合は、必要ない。

よって、解は、

\min\left(\min_{h \leq j \leq D-1} \left(1+\displaystyle\sum_i d_{h,i}\right), \displaystyle\sum_i d_{D,i} \right)

。

\displaystyle\sum_i d_{h,i} \leq \cdots \leq \displaystyle\sum_i d_{D,i}

を用いると、

\min\left(1+\displaystyle\sum_i d_{h,i}, \displaystyle\sum_i d_{D,i}\right)

。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 貪欲法
ll cal(ll cut, int h, vector<ll> &num) {
    ll ret = 0, qout;
    for (int i = h - 1; i >= 0; --i) {
        qout = cut / num[i];
        cut -= num[i] * qout;
        ret += qout;
    }

    return ret;
}

int main() {
    int t, d;
    ll k, x;

    cin >> t;

    for (int cases = 0; cases < t; ++cases) {
        cin >> d >> k >> x;
        vector<ll> num(d + 1);
        num[0] = 1;
        for (int i = 1; i <= d; ++i) num[i] = num[i - 1] * k + 1;

        int h;  // Σ_{i <= h - 1} K^i < x <= Σ_{i <= h} K^i となる h
        for (h = 0; h <= d; ++h) {
            if (x <= num[h]) break;
        }

        cout << min(1 + cal(num[h] - x, h, num), cal(num[d] - x, d, num)) << '\n';
    }

    return 0;
}

Ex - Bow Meow Optimization

編集中…。

青色コーダーが ABC 全問解説する【ABC290】

Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）

A - Contest Result

B - Qual B

C - Max MEX

D - Marking

E - Make it Palindrome

F - Maximum Diameter

G - Edge Elimination

Ex - Bow Meow Optimization

Discussion

コメントにはログインが必要です。