23か月前公開・22か月前更新・0 pv・19 min read

水色コーダーが ABC 全問解説する【ABC281】

AtCoder競技プログラミングAtCoderBeginnerContest

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

AtCoder Beginner Contest 281

3 完(´・ω・｀)　D 問題がぱっと思いつかなく、E 問題、F 問題が解けそうで失敗(´・ω・｀)　全部時間外で通しました。

A - Count Down

for ループを理解していれば簡単。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;

    for (int i = n; i >= 0; --i) cout << i << '\n';

    return 0;
}

B - Sandwich Number

条件を整理すると、

$S$ は $8$ 文字
$1$ 文字目と $8$ 文字目は、A ~ Z
$2$ 文字目は、1 ~ 9
$3$ ~ $7$ 文字目は、0 ~ 9

これを実装すれば OK。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;

    cin >> s;

    // S が 8 文字でない or
    // 1 文字目が、'A' ~ 'Z' でない or
    // 8 文字目が、'A' ~ 'Z' でない or
    // 2 文字目が、'1' ~ '9' でないなら
    // "No" を出力
    if (s.length() != 8 || !('A' <= s[0] && s[0] <= 'Z') ||
        !('A' <= s[7] && s[7] <= 'Z') || !('1' <= s[1] && s[1] <= '9')) {
        cout << "No";
        return 0;
    }

    // 3 ~ 7 文字目が、'0' ~ '9' でないなら
    // "No" を出力
    for (int i = 2; i < 7; ++i) {
        if (!('0' <= s[i] && s[i] <= '9')) {
            cout << "No";
            return 0;
        }
    }

    // すべての条件を満たすなら "Yes" を出力
    cout << "Yes";

    return 0;
}

C - Circular Playlist

T

が大きすぎる。曲はループするので、全曲の時間の総和で

T

を割れば、プレイリスト

1

回分未満の時間として考えられる。そうすれば

O(N)

で答えを求められる。
(二分探索で

O(\log N)

にもできるけど、入力が

N

個あるのであんまり意味ない。)

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    ll t, sum = 0;

    cin >> n >> t;

    vector<ll> a(n);

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

    t %= sum;  // 全曲の時間の総和で割る

    // 「何番目の曲が流れているか」と「流れている時間」を計算
    for (int i = 0; i < n; ++i) {
        if (t < a[i]) {
            cout << i + 1 << ' ' << t;
            break;
        }
        t -= a[i];
    }

    return 0;
}

D - Max Multiple

パッと思いつかなかった…(´・ω・｀)　

3

重ループの DP…。

dp[

個数

][

余り

]=

(総和の最大値) として、

i

ごとに、すべての、個数

cnt

、余り

rem

に対して、

dp[cnt][(rem+A_i)\bmod D]=\max (dp[cnt][(rem+A_i)\bmod D],dp[cnt-1][rem]+A_i)

で更新すればいい。オーダーは

O(N^3)

で、更新を終えたあとの最終的な

dp[K][0]

の値が答え。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

    cin >> n >> k >> d;

    vector<int> a(n);
    // dp[個数][余り] (不可能な場合は -1)
    vector<vector<ll>> dp(n + 1, vector<ll>(d, -1));
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 個数 0 は 余り 0 で最大値 0
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
        // ※ 個数の小さい順に更新すると、更新後の値でさらに更新してしまう
        for (int cnt = i + 1; cnt > 0; --cnt) {
            for (int rem = 0; rem < d; ++rem) {
                // 遷移前の状態が到達不可能な状態なら continue
                if (dp[cnt - 1][rem] == -1) continue;
                // a_i を S に入れた場合に今までの最大値を上回るなら更新
                dp[cnt][(rem + a[i]) % d] = max(dp[cnt][(rem + a[i]) % d], dp[cnt - 1][rem] + a[i]);
            }
        }
    }

    // 個数 k 余り 0 の最大値が答え。
    cout << dp[k][0];

    return 0;
}

E - Least Elements

i+1

のときの

M

個の整数は

i

のときと比べて、

A_{i+M}

が追加され、

A_i

が削除される。
なので

i=1

のときの解を求めた後、

i=2, \cdots N-M+1

までは、順番に、

A_i

と

A_{i+M}

についてだけ操作すればいい。すると、操作回数は

O(N)

で済む。

i=1

のときは、

A_1

から

A_M

までをソートし、小さい順で

K

個の要素の総和を求めればいい。このとき、小さい順で

K

個の要素の集合を、

AMins

、それ以外の

M-K

個の要素の集合を、

AOthers

とおく。

i > 1

のときは、

A_{i-1}

が

AMins

と

AOthers

のどちらにあるかで分岐する。

$A_{i-1}$ が $AMins$ にあるとき、
$A_{i-1}$ を $AMins$ から削除し、 $A_{i+M-1}$ を $AOthers$ に追加する。その後、 $AOthers$ の最小の要素を $AMins$ に移動する。
$A_{i-1}$ が $AMins$ にないとき、
$A_{i-1}$ を $AOthers$ から削除し、 $A_{i+M-1}$ を $AMins$ に追加する。その後、 $AMins$ の最大の要素を $AOthers$ に移動する。

答えは、

i-1

のときの答えから

AMins

に追加した分を足し、

AMins

から削除した分を引いた値となる。

要素の追加や削除は、multiset や、組

(A_i,i)

を要素とした set などを用いて

O(\log N)

。操作回数が

O(N)

なので、オーダーは

O(N \log N)

。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, m, k;

    cin >> n >> m >> k;

    vector<int> a(n);
    // i = 0 (問題文では 1-indexed なので 1) のときの解を求める用
    vector<int> first(m);
    // 解説の AMins と AOthers
    multiset<int> aMins, aOthers;

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

    sort(first.begin(), first.end());

    ll ans = 0;
    // i = 0 の解を求め、AMins と AOthers に要素を格納
    for (int i = 0; i < k; ++i) {
        aMins.insert(first[i]);
        ans += first[i];
    }
    for (int i = k; i < m; ++i) {
        aOthers.insert(first[i]);
    }

    // i = 0 のときの解
    cout << ans << ' ';

    // i = 1, …, N - M までの解を求める
    for (int i = m; i < n; ++i) {
        // aMins に a[i - m] があるか探す
        auto itrOut = aMins.find(a[i - m]);
        // aMins に a[i - m] があるなら
        if (itrOut != aMins.end()) {
            aMins.erase(itrOut);   // aMins から a[i - m] を削除
            ans -= a[i - m];       // 答えから引く
            aOthers.insert(a[i]);  // aOthers には a[i] を入れる

            int mov = *aOthers.begin();      // aOther の最小値
            auto itrIn = aOthers.find(mov);  // 削除用

            // aOther の最小値を aMins に移動
            aOthers.erase(itrIn);  // ※ aOthers.erase(mov);
                                   // 　だと複数の要素が削除される場合がある
            aMins.insert(mov);
            ans += mov;  // 答えに足す
        } else {
            itrOut = aOthers.find(a[i - m]);  // 削除用
            aOthers.erase(itrOut);  // aOthers から a[i - m] を削除
            aMins.insert(a[i]);     // aMins には a[i] を入れる
            ans += a[i];            // 答えに足す

            int mov = *aMins.rbegin();     // aMins の最大値
            auto itrIn = aMins.find(mov);  // 削除用

            // aMins の最大値を aOthers に移動
            aMins.erase(itrIn);  // ※ aMins.erase(mov);
                                 // 　だと複数の要素が削除される場合がある
            ans -= mov;  // 答えから引く
            aOthers.insert(mov);
        }

        cout << ans << ' ';
    }

    return 0;
}

F - Xor Minimization

ans_i=

(各要素の

2^i

の位より大きい位の値をすべて

0

にしたときの解) とおく (

ans_{-1}=0

)。すると、以下の

2

つに分岐して考えられる。

$2^i$ の位の値が $0$ である要素と $1$ である要素がある場合
どのように $x$ を選んでも、 $2^i$ の位の値が $1$ になる要素が現れるので、
$ans0_{i-1}=$ ( $2^i$ の位の値が $0$ である要素のみで考えた場合の $ans_{i-1}$ )、
$ans1_{i-1}=$ ( $2^i$ の位の値が $1$ である要素のみで考えた場合の $ans_{i-1}$ ) とおくと、

ans_i=2^i \text{ bitOR } \min(ans0_{i-1},ans1_{i-1})

すべての要素の $2^i$ の位の値が同じ場合
$x$ の $2^i$ の位の値を、すべての要素の $2^i$ の位の値と同じにすれば、すべての要素の $2^i$ の位の値を $0$ にできる。なので、

ans_i=ans_{i-1}

再帰的にこれを解けばよい。オーダーは

O(N \log A)

。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

// a は要素の集合、2 の sft 乗の位について解く
int solve(vector<int> &a, int sft) {
    if (sft < 0) return 0;

    // a0 は 2 の sft 乗の位の値が 0 である要素の集合
    // a1 は 2 の sft 乗の位の値が 1 である要素の集合
    vector<int> a0, a1;
    for (int val : a) {
        if (val & (1 << sft))
            a1.push_back(val);
        else
            a0.push_back(val);
    }

    if (a0.empty() || a1.empty()) {  // すべての要素の 2 の sft 乗の位の値が同じなら
        return solve(a, sft - 1);  // ans_sft = ans_{sft - 1}
    } else {  // 両方あるなら
        // ans_sft = (2 の sft 乗) | min(ans0_{i - 1}, ans1_{i - 1})
        return (1 << sft) | min(solve(a0, sft - 1), solve(a1, sft - 1));
    }
}

int main() {
    int n;

    cin >> n;

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

    // a_i < (2 の 30 乗) なので、2 の 29 乗の位まで調べればいい
    cout << solve(a, 29);

    return 0;
}

G - Farthest City

dp[

頂点数

][

距離が最大の頂点数

][

距離

]

の DP ならいけそう…くらいまでは考えたけど、遷移が

O(N)

あったので諦めて公式解説を確認…。
距離が違っても遷移の方法は変わらないし、条件も、頂点

1

から頂点

N

までの最短距離より真に小さければいいだけで距離の値は関係ないので、距離分の状態数は省けるみたい…。つまり、

dp[

頂点数

][

距離が最大の頂点数

]

で十分なのね…。

結局実装は、公式解説のように

dp[

頂点

1

と非連結な頂点数 (

d_u \neq \infty

の

u

の数)

][

距離が最大の頂点数

]

にしました。

以下、公式解説の操作をざっくり説明。

次の操作を $u \neq N$ かつ $d_u = \infty$ となる $u$ が存在する間繰り返す。また、整数 $n$ を $n=0$ で初期化する。
→ $d_u = \infty$ のとき、頂点 $u$ は頂点 $1$ と非連結なので、頂点 $N$ を除く全頂点が頂点 1 と連結になるまで操作を行う。
- $u \neq N$ かつ $d_u = \infty$ を満たす $u$ を $\textbf{1}$ 個以上好きな個数選び、 $u_i, \cdots, u_k$ とおく。
  → 頂点 $1$ からの距離を $n+1$ にしたい頂点を非連結な頂点の中から選ぶ ( $1$ 個は必要)。選び方は、非連結な頂点数を $n'$ とおくと、選んだ頂点の個数は $k$ 個なので、 $\dbinom{n'}{k}$ 。
- 各 $u_i$ に対し、 $d_u = n$ となる $v$ を $\textbf{1}$ 個以上好きな個数選び、それぞれに対して辺 $(v,u_i)$ を追加する。また、 $d_{u_i}$ の値を $n+1$ で置き換える。
  → 距離を $n+1$ にするために、距離が $n$ の ( $1$ 個以上の) 頂点と辺でつなぐ。辺の選び方は、各頂点 $u_i$ ごとに、距離が $n$ の頂点数を $n'$ として、 $2^{n'}-1$ 。
- $1 \leq i \leq j \leq k$ を満たす $(i,j)$ を $\textbf{0}$ 個以上好きな個数選び、それぞれに対して辺 $(u_i,u_j)$ を追加する。
  → 距離が $n+1$ の頂点同士を辺でつなぐ。辺の選び方は $2^{\frac{k(k-1)}{2}}$ 。
- $n$ の値を $1$ 増やす。
  → 距離を $1$ ずらして同じ操作をやり直す。
各 $u_i$ に対し、 $d_u = n$ となる $v$ を $\textbf{1}$ 個以上好きな個数選び、それぞれに対して辺 $(v,N)$ を追加する。また、 $d_N$ の値を $n+1$ で置き換える。
→ $d_N$ の頂点 $1$ からの距離を $n+1$ (ほかのどの頂点の頂点 $1$ からの距離よりも真に大きい) にして終了。辺の選び方は、距離が $n$ の頂点数を $n'$ として、 $2^{n'}-1$ 。

以上のことを、

dp[

頂点

1

と非連結な頂点数 (頂点

N

を除く)

][

距離が最大の頂点数

]

で表現すると、

dp[N-2][1]=1

で、

n=N-3, \cdots 0

の順に、

1 \leq k \leq N-1-n

の範囲で以下のように更新すればいい。

dp[n][k]=\sum_{i=1}^{N-1-(n+k)}dp[n+k][i] \binom{n+k}{k} (2^{i}-1)^k 2^{\frac{k(k-1)}{2}}

\dbinom{n+k}{k}, (2^{i}-1)^k, 2^{\frac{k(k-1)}{2}}

をそれぞれ前計算しておけば、

O(N^3)

で DP を計算できる。前計算のオーダ―はどれも

O(N^2)

。

答えは、

\displaystyle\sum_{k=1}^{N-2}dp[0][k] (2^{k}-1)

。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int N;
    ll M;

    cin >> N >> M;

    // 2 の累乗の前計算
    vector<ll> p2(N * N);
    p2[0] = 1;
    for (int i = 1; i < N * N; ++i) p2[i] = p2[i - 1] * 2 % M;

    // 二項係数の前計算 (パスカルの三角形)
    vector<vector<ll>> C(N, vector<ll>(N));
    C[0][0] = 1;
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j <= i; ++j) {
            (C[i + 1][j] += C[i][j]) %= M;
            (C[i + 1][j + 1] += C[i][j]) %= M;
        }
    }

    // ((2 の i 乗) - 1) の k 乗の前計算
    vector<vector<ll>> connectMinus1(N, vector<ll>(N));
    for (int i = 1; i < N; ++i) {
        connectMinus1[i][1] = (p2[i] + M - 1) % M;
        for (int j = 2; j < N; ++j) {
            connectMinus1[i][j] = connectMinus1[i][j - 1] * connectMinus1[i][1] % M;
        }
    }

    // dp[頂点 1 と非連結な頂点数 (頂点 N を除く)][距離が最大の頂点数]
    vector<vector<ll>> dp(N, vector<ll>(N));

    // dp の計算
    dp[N - 2][1] = 1;
    for (int n = N - 3; n >= 0; --n) {
        for (int k = 1; k <= N - 1 - n; ++k) {
            for (int i = 1; i <= N - 1 - (n + k); ++i) {
                dp[n][k] += dp[n + k][i] * C[n + k][k] % M *
                            connectMinus1[i][k] % M * p2[k * (k - 1) / 2] % M;
                dp[n][k] %= M;
            }
        }
    }

    ll ans = 0;

    // 答えの計算
    for (int i = 1; i <= N - 2; ++i) {
        (ans += dp[0][i] * connectMinus1[i][1]) %= M;
    }

    cout << ans;

    return 0;
}

Ex - Alchemy

多項式や形式的べき級数を使って

x^n

の係数が答え、みたいな問題、Ex で頻出？

公式解説を参考に実装。

N=i

のときの答えを

a_i

とおくと、

a_i

は、

f(x) \prod_{j=2}^{i-1} (1+a_j x) \\ \left ( f(x)=\sum_{k=0}^A \binom{A}{k}x^k \right )

の

x^i

の係数と一致する (わからなければ、maspy さんのページなどを見るとよさそう。)。

あとは、これを公式解説にあるように畳み込みと分割統治法を使って求めたい。(分割統治法自体は、クイックソートなどでも用いられる手法でそんなに難しい話ではない。)

畳み込みで、

f(x) \cdot g(x)

を求めるには、

f[i]=

(

f(x)

の

x^i

の係数)、

g[i]=

(

g(x)

の

x^i

の係数) として、

f

と

g

を畳み込みすればいい。畳み込みのライブラリは AtCoder Library にあるので、それを使うと楽。畳み込みが

O(N \log N)

で分割統治法の深さが

O(\log N)

なので、

O(N \log^2 N)

。

公式解説のコードのように分割統治法で

\displaystyle\prod_{j=l}^{r-1} (1+a_j x)

を求めていくとする。
今回の分割統治法で用いる

g(x)=f(x) \displaystyle\prod_{j=2}^{l-1} (1+a_j x)

を表す配列

g

は、分割統治の範囲を

[l,r)

としたときに、

O(r-l)

程度の大きさに落とさないと、全体で

O(N \log^2 N)

の計算量にできない。今回の配列

g

は

g(x)

の次数

[l,r)

の範囲しか必要ない。理由は以下のとおりである。

r-l=1

のとき、

\{1,g[l]\}

を返さなくてはいけないので、少なくとも、次数

[l,r)

の範囲は必要だとわかる。

分割統治の範囲が

[l,r)

のとき、分割統治の範囲が

[m,r)

のときに用いる

g

を計算する必要がある。分割統治の範囲が

[l,r)

のときの

g(x)

を

g(x)

、分割統治の範囲が

[m,r)

のときの

g(x)

を

gRight(x)

とおくと、

gRight(x)=g(x) \cdot \prod_{j=l}^{m-1} (1+a_j x)

g(x)

を

\displaystyle\sum_{i=0}^\infty \alpha_i x^i

、

\displaystyle\prod_{j=l}^{m-1} (1+a_j x)

を

\displaystyle\sum_{i=0}^{m-l} \beta_i x^i

におきかえると、

\begin{align*} gRight(x)&= \cdots + (\alpha_l \beta_{m-l} + \cdots + alpha_m \beta_0) x^m \\ &+ \cdots + (\alpha_{r-(m-l)} \beta_{m-l} + \cdots + alpha_{r-1} \beta_0) x^{r-1} + \cdots \end{align*}

である。これをよく見ると、

gRight(x)

の次数

[m,r)

の範囲で使われている

g(x)

の係数は次数

[l,r)

の範囲の係数のみであることがわかる。つまり、分割統治の範囲が

[l,r)

のとき、

g(x)

の次数

[l,r)

の範囲だけ持っていれば、分割統治の範囲が

[m,r)

のときの

g(x)

の次数

[m,r)

を欠損なく計算できる。

よって、今回の配列

g

は

g(x)

の次数

[l,r)

の範囲しか必要ない。

なので、公式解説のコードを

g(x)

の次数

[l,r)

の範囲のみ渡すように改良すればいい。

↓ こんな感じ。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;
using mint = modint998244353;

// 分割統治法で畳み込み
// g[i] は g(x) の x の (l + i) 乗の係数
vector<mint> dc(int l, int r, vector<mint> g) {
    // 範囲の大きさが 1 なら (1 + a_l x) を返す
    if (r - l == 1) return {1, g[0]};

    int m = (l + r) / 2;

    // 分割 左側 (g(x) の次数 [l, m) の範囲だけ渡す)
    vector<mint> retLeft = dc(l, m, vector<mint>(&g[0], &g[m - l]));

    // 分割 右側用の g を求める
    // {f(x) * (1 + a_2) * … * (1 + a_{l - 1})} * {(1 + a_l) * … * (1 + a_{m - 1})}
    vector<mint> gRight = convolution(g, retLeft);
    // 分割 右側 (g(x) の次数 [m, r) の範囲だけ渡す)
    vector<mint> retRight = dc(m, r, vector<mint>(&gRight[m - l], &gRight[r - l]));

    // 左側の返り値と右側の返り値を掛けたものを返す
    return convolution(retLeft, retRight);
}

int main() {
    int n, a;

    cin >> n >> a;

    // 二項係数 a C i の計算
    vector<mint> aC(n + 1);
    aC[0] = 1;
    for (int i = 1; i <= n; ++i) aC[i] = aC[i - 1] * (a + 1 - i) / i;

    if (n <= 2) {  // n <= 2 なら、解は a C n
        cout << aC[n].val();
    } else {  // そうでないなら分割統治法
        // l - 1 < 2 のとき g(x) = f(x)
        // f(x) * {(1 + a_2) * … * (1 + a_{n - 1})} の x の n 乗の係数が解
        cout << convolution(aC, dc(2, n, vector<mint>(&aC[2], &aC[n])))[n].val();
    }

    return 0;
}

水色コーダーが ABC 全問解説する【ABC281】

AtCoder Beginner Contest 281

A - Count Down

B - Sandwich Number

C - Circular Playlist

D - Max Multiple

E - Least Elements

F - Xor Minimization

G - Farthest City

Ex - Alchemy

Discussion

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