Ccmmutty logo
Commutty IT
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

i=1MABi\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

KK 個目の 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)[i,i+K) かと勘違いしてタイムロス…。任意の KK 個だった…(´・ω・`)
BB は、AA の順序を保っているらしいけど、MEXMEX は順序関係ないので気にしなくてもいい。
KKMEX(A)MEX(A) の大小別に考えてみる。
  • K<MEX(A)K < MEX(A) のとき
    0,1,,MEX(A)10,1, \cdots, MEX(A)-1 と、任意の KMEX(A)K-MEX(A) 個の要素を選んで BB としたときが最大となる。答えは、MEX(A)MEX(A)
  • KMEX(A)K \geq MEX(A) のとき
    0,1,,K10,1, \cdots, K-1 を選んで BB としたときが最大となる。答えは、KK
よって、答えは、min(K,MEX(A))\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

xx(x+1)modN(x+1) \bmod N に更新しなければ、xx は、Ngcd(N,D)\frac{N}{\text{gcd}(N,D)} 回でループする。
つまり、
0,DmodN,,(Ngcd(N,D)1)DmodN,1,(1+D)modN,,(1+(Ngcd(N,D)1)D)modN,N1,,(N1+(Ngcd(N,D)1)D)modN0, 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
の順に、印をつけることになる。
よって、(K1)(K-1)Ngcd(N,D)\frac{N}{\text{gcd}(N,D)} で割ったときの商を quotquot、余りを remrem とおくと、答えは、
(quot+rem×D)modN(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

XXii 番目の要素を XiX_i とおく。また、XX の連続部分列 {XL,,XR}\{X_L, \cdots, X_R\}X[L,R]X[L,R] とおく。
f(X)f(X) の値は、XiXX+1iX_i \neq X_{|X|+1-i} となる i(X2)i(\leq \frac{|X|}{2}) の数と等しい。
そのため、f(X)=(Xi=XX+1if'(X)=(X_i = X_{|X|+1-i} となる i(X2)i(\leq \frac{|X|}{2}) の数)) とおくと、f(X)=X2f(X)f(X)=\left\lfloor \frac{|X|}{2}\right\rfloor-f'(X)
AA の連続部分列 XX における f(X)f'(X) の総和を考える。
i<ji<j となる i,ji,j について考えると、X[i,j],X[i1,j+1],,X[imin(i1,Nj),j+min(i1,Nj)]X[i,j],X[i-1,j+1], \cdots, X[i-\min(i-1,N-j),j+\min(i-1,N-j)] において、j=X+1ij=|X|+1-i が成立する。
そのため、Xi=XjX_i=X_j のとき、 f(X)f'(X) の総和は、XiXjX_i \neq X_j のときと比べて min(i1,Nj)+1\min(i-1,N-j)+1 大きくなる。
すべての i,j(i<j)i,j(i < j)XiXjX_i \neq X_j なら、f(X)=0f'(X)=0 なので、f(X)f'(X) の総和は、
i<j,Xi=Xj(min(i1,Nj)+1)\sum_{i<j,X_i=X_j} (\min(i-1,N-j)+1)
となる。
ここで、jj を固定した場合を考える。
jN2j \leq \frac{N}{2} のとき、
i<j,Xi=Xj(min(i1,Nj)+1)=i<j,Xi=Xji\sum_{i<j,X_i=X_j} (\min(i-1,N-j)+1)=\sum_{i<j,X_i=X_j} i
j>N2j > \frac{N}{2} のとき、
i<j,Xi=Xj(min(i1,Nj)+1)=iNj,Xi=Xji+Nj<i<j,Xi=Xj(Nj+1)=iNj,Xi=Xji+(Nj+1)Nj<i<j,Xi=Xj1\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*}
であるから、整数の値ごとに i=1j1i\displaystyle\sum_{i=1}^{j-1} i などを保持しながら jj の昇順に求めれば、各 jj における i<j,Xi=Xj(min(i1,Nj)+1)\displaystyle\sum_{i<j,X_i=X_j} (\min(i-1,N-j)+1) は、O(1)O(1) で求められる。
よって、f(X)f'(X) の総和、ないし、答えは、O(N)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

NN 頂点の木なので、Xi=2N2\sum X_i =2N-2 である。また、Xi2X_i \leq 2 である ii の個数を kk とおくと、f(X)=k+1f(X)=k+1 である。
すべての ii において、Xi1X_i \leq 1 なので、次数 N2N-2Xi2X_i \leq 2 としたい kk 個の頂点に分配することを考える。 すると、次数 N2kN-2-kkk 個の頂点に、各 00 以上分配することを考えればいい。
頂点の選び方が NCk{}_N \text{C}_k 通りなので、Xi2X_i \leq 2 である ii の個数が kk となる XX の個数は、
NCkN2kHk(k+1){}_N \text{C}_k \sdot {}_{N-2-k} \text{H}_k \cdot (k+1)
となる。
N3N \geq 3 のとき、0<kN20<k\leq N-2 なので、答えは、
k=1N2NCkN2kHk(k+1)\sum_{k=1}^{N-2} {}_N \text{C}_k \sdot {}_{N-2-k} \text{H}_k \cdot (k+1)
O(N)(N106)O(N)(N \leq 10^6) なので、T2×105T \leq 2 \times 10^5 では間に合わない。
式変形すると、
k=1N2NCkN2kHk(k+1)=k=1N2N!k!(Nk)!(N3)!(k1)!(N2k)!(k+1)=N!(N3)!k=1N21(Nk)!(Nk2)!k+1k!(k1)!\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=Nkj=N-k と置き換え、1n!=0(n<0)\frac{1}{n!}=0(n<0) と定義すれば、
k=1N21(Nk)!(Nk2)!k+1k!(k1)!=j+k=N1j!(j2)!k+1k!(k1)!\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=106N=10^6 まで前計算しておけば、3N3 \leq N の答えを O(1)O(1) で求められる。なお、N=2N=2 のとき、答えは 11 なので、2N1062 \leq N \leq 10^6 のときの答えを O(1)O(1) で求められる。
オーダーは、畳み込みがボトルネックで、O(NlogN)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

i=0h1Ki<xi=0hKi\displaystyle\sum_{i=0}^{h-1} K^i < x \leq \displaystyle\sum_{i=0}^h K^i となる深さ hh の完全部分木 (つまり、深さ DhD-h の頂点を親とする完全部分木) から切り取る場合だけを考えるとダメなのね…。
コーナーケースは以下等。
とはいえ、深さ 00 の頂点を残す場合と残さない場合で、切るべき辺の数が 11 変わるせいで、コーナーケースが現れている気がする…。そうなら、公式解説 は、すべての深さの計算してるけど、深さ DD の木と、深さ hh の完全部分木だけ計算すればよさそう。オーダーは DD11 個落ちる。
証明してみる。
深さ mm の完全部分木から、貪欲法で完全部分木を切り取って、連結成分を XX 頂点にするときに、深さ ii の完全 KK 分木を切り取る個数を dm,i(i<m)d_{m,i}(i<m) とおく。
また、深さ m+1m+1 の完全部分木を用いたときに切り取る頂点の数は、深さ mm の完全部分木を用いたときに切り取る頂点の数より、(K1)Km+1(K-1)K^m+1 多い。
  • すべての iidm,iK1d_{m,i} \leq K-1 を満たすとき
    深さ m+1m+1 の完全部分木では、深さ mm の完全部分木より (K1)Km+1(K-1)K^m+1 頂点多く切り取るので、深さ mm の完全 KK 分木を (K1)(K-1) 個、深さ 00 の完全 KK 分木を 11 個、余分に切り取る必要がある。
    よって、
idm+1,i=idm,i+>idm,i\sum_i d_{m+1,i} = \sum_i d_{m,i} + K > \sum_i d_{m,i}
  • ある iidm,i=Kd_{m,i} = K を満たすとき
    同様に、深さ m+1m+1 の完全部分木では、深さ mm の完全部分木より (K1)Km+1(K-1)K^m+1 頂点多く切り取る必要がある。(K1)K(K-1)K 頂点分は、深さ mm の完全 KK 分木を (K1)(K-1) 個切り取るしかない。
    しかし、残りの 11 頂点は、dm,i=Kd_{m,i} = K を満たす ii が存在するため、dm+1,i+1=dm,i+1+1,dm+1,i=0d_{m+1,i+1}=d_{m,i+1}+1, d_{m+1,i}=0 とすると、(j=1i+1KjKj=1iKj=)1(\sum_{j=1}^{i+1} K^j - K\sum_{j=1}^i K^j=)1 個切り取る頂点を増やせる。
    よって、
idm+1,i=idm,i+(K+1)+1K=idm,i\sum_i d_{m+1,i} = \sum_i d_{m,i} +(K+1) +1 - K = \sum_i d_{m,i}
上記から、idh,iidh+1,iidD,i\displaystyle\sum_i d_{h,i} \leq \displaystyle\sum_i d_{h+1,i} \leq \cdots \leq \displaystyle\sum_i d_{D,i} を満たす。
ここで、深さ mm の完全部分木を用いる場合、まず、その完全部分木を切り出すときに 11 回辺を切る必要があるが、元々の深さ DD を用いる場合は、必要ない。
よって、解は、min(minhjD1(1+idh,i),idD,i)\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)
idh,iidD,i\displaystyle\sum_i d_{h,i} \leq \cdots \leq \displaystyle\sum_i d_{D,i} を用いると、min(1+idh,i,idD,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;
}

Discussion

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