Ccmmutty logo
Commutty IT
0 pv18 min read

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

https://cdn.magicode.io/media/notebox/80867ac6-c7b5-44cd-a741-2a6f91173e41.jpeg

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)

E 問題手こずるし、D 問題通らないしで 4 完。下ギリギリの水パフォ。よくない(´・ω・`)

A - Pawn on a Grid

# を数えるだけ。22 重ループとか。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int h, w;
    int ans = 0;

    cin >> h >> w;

    string s;
    for (int i = 0; i < h; ++i) {
        cin >> s;
        for (int j = 0; j < w; ++j) {
            if (s[j] == '#') ++ans;
        }
    }

    cout << ans;

    return 0;
}

B - Inverse Prefix Sum

SS の定義から、A1=S1A_1=S_1Ak=SkSk1A_k=S_k-S_{k-1} (k2)(k \geq 2) だとわかるので、それを出力すれば OK。S0=0S_0=0 を追加すると、Ak=SkSk1A_k=S_k-S_{k-1} (k1)(k \geq 1) になって、場合分けがいらないので楽ちん。
ちなみに、SS は 「AA の累積和」というやつで、SrSl1=Al+Al+1++ArS_r-S_{l-1}=A_l+A_{l+1}+ \cdots +A_r (l<r)(l<r) になります。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;

    vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        cout << s[i] - s[i - 1] << ' ';
    }

    return 0;
}

C - Extra Character

SSi1i-1 文字目と TTi1i-1 文字目までが一致していて、SSii 文字目と TTii 文字目が一致していなければ、そこが候補のうちの 11 つ。SS の最後の文字まで全部一致しているなら TT の一番最後の文字が候補のうちの 11 つ。
なので、i=0i=0 から順に文字が一致しているか判別すればいい。
SS の末尾に絶対一致しない文字を追加すると、「SS の最後の文字まで全部一致しているなら」を場合分けしなくてよくなる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    string s, t;

    cin >> s >> t;

    s.push_back(' ');  // s の末尾に絶対一致しない文字を追加
    for (int i = 0, len = s.length(); i < len; ++i) {
        if (s[i] != t[i]) {
            cout << i + 1;
            return 0;
        }
    }

    return 0;
}

D - Factorial and Multiple

難しかった気がする (私が素因数分解に慣れていなかったのもあるけど)。公式解説の解き方がわかりやすそう。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    ll k;
    ll ans = 1;

    cin >> k;

    int sqrtK = sqrt(k);  // √K

    for (int i = 2; i <= sqrtK; ++i) {
        // i が k の素因数でないなら continue
        if (k % i) continue;
        // ※ i が合成数なら k % i != 0
        //  なぜならその前に割り切れなくなるまで
        //  i の素因数で k を割っているから

        int index = 0;  // k が持つ素因数 i の数 (指数)
        while (k % i == 0) {  // 割り切れなくなるまで
            ++index;  // 数を加算
            k /= i;   // k を i で割る
        }

        // j! が i の index 乗の倍数となるような最小の j の計算
        int j, multiple;
        for (j = i;; j += i) {  // i の倍数を小さい順に調べる
            multiple = j;
            while (multiple % i == 0) {
                --index;
                multiple /= i;
            }
            // j! が i の index 乗の倍数になったら終了
            if (index <= 0) break;
        }

        ans = max(ans, (ll)j);
    }

    // この段階で k = 1 または k は √K より大きい素数
    ans = max(ans, k);

    cout << ans;

    return 0;
}

E - Critical Hit

この公式解説みたいに解きたかった…。dp[n]=f(dp[n1])+g(dp[n2])dp[n]=f(dp[n-1])+g(dp[n-2]) みたいな形じゃなく、dp[n2]dp[n-2] += f(dp[n]),dp[n1]f(dp[n]),dp[n-1] += g(dp[n1])g(dp[n-1]) みたいな形にしたらややこしくなった(´・ω・`) …今回の敗因。
一応、そのややこしいほうを解説…。
prob[i]=prob[i]= (体力が ii になる確率)、dp[i]=kkpk,idp[i]=\sum_k k p_{k,i} (pk,ip_{k,i}: kk 回の攻撃で体力が ii になる確率) (ii が 0 未満の場合は i=0i=0 に含む)とすると、
prob[i]=prob[i+1]×(1P)+prob[i+2]×Pdp[i]=(1P)k(k+1)pk,i+1+Pk(k+1)pk,i+2=(1P)(kkpk,i+1+kpk,i+1)+P(kkpk,i+2+kpk,i+2)=(1P)(dp[i+1]+prob[i+1])+P(dp[i+2]+prob[i+2])\begin{align*} prob[i]&=prob[i+1] \times (1-P) + prob[i+2] \times P \\ dp[i]&= (1-P)\sum_k (k+1) p_{k,i+1}+P \sum_k (k+1) p_{k,i+2} \\ &=(1-P)(\sum_k k p_{k,i+1} + \sum_k p_{k,i+1}) + P(\sum_k k p_{k,i+2} + \sum_k p_{k,i+2}) \\ &=(1-P)(dp[i+1]+prob[i+1])+P(dp[i+2]+prob[i+2]) \end{align*}
なので、prob[N]=1,dp[N]=0prob[N]=1,dp[N]=0 で、i=N,,1i=N, \cdots ,1 の順に、
prob[i1] += prob[i]×(1P)prob[max(0,i2)] += prob[i]×Pdp[i1] += (dp[i]+prob[i])×(1P)dp[max(0,i2)] += (dp[i]+prob[i])×P\begin{align*} prob[i-1] &\text{ += } prob[i] \times (1-P) \\ prob[\max (0,i-2)] &\text{ += } prob[i] \times P \\ dp[i-1] &\text{ += } (dp[i]+prob[i]) \times (1-P) \\ dp[\max (0,i-2)] &\text{ += } (dp[i]+prob[i]) \times P \\ \end{align*}
とすればよく、dp[0]dp[0] が答えとなる。ダメージが NN を超える場合の帳尻合わせを、公式解説は最初にやっているけど、この解説では最後にやっているので probprob が必要になってる?
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 法 mod での累乗
long long pow(long long n, long long m, long long mod) {
    long long ans = 1;
    while (m) {
        if (m & 1) ans = ans * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return ans;
}

int main() {
    ll n, p;
    const int mod = 998244353;

    cin >> n >> p;

    vector<ll> dp(n + 1);
    vector<ll> prob(n + 1);
    // 体力が 2 減る確率
    ll critical = p * pow(100, mod - 2, mod) % mod;
    // 体力が 1 減る確率
    ll notCritical = 1 + mod - critical;

    // 式のとおり
    dp[n] = 0;
    prob[n] = 1;
    for (int i = n; i >= 1; --i) {
        (prob[i - 1] += prob[i] * notCritical) %= mod;
        (prob[max(0, i - 2)] += prob[i] * critical) %= mod;
        (dp[i - 1] += (dp[i] + prob[i]) * notCritical) %= mod;
        (dp[max(0, i - 2)] += (dp[i] + prob[i]) * critical) %= mod;
    }

    cout << dp[0];

    return 0;
}

F - Pay or Receive

時間外で解けました。
到達可能かどうかはポイントと関係ない。ポイントを無視すれば無向グラフなので、「頂点 uu から頂点 vv に到達可能」 \Leftrightarrow 「頂点 uu と頂点 vv は連結」。なので、
XiX_iYiY_i が連結でないなら、nan
XiX_iYiY_i が連結で、正閉路とも連結なら、inf
XiX_iYiY_i が連結で、正閉路とは連結でないならポイントの最大値
を出力すればいい。しかし、正閉路を探したり、任意の 22 点間のポイントの最大値を求めたりするために、「ポイントの正負を逆転して、ワーシャルフロイド法を使う」とかでは、O(N3)O(N^3) で全然間に合わない。なので、別の方法を考えたい。
以下、すべての頂点が連結のグラフを考える。
ポイントの総和が ca,cbc_a,c_b の頂点 uu から頂点 vv へのパス passa(u,v),passb(u,v){pass}_a (u,v),{pass}_b (u,v) を考えてみる。このとき、パスの頂点を頂点 vv から頂点 uu へ逆順に移動するパス passa(v,u),passb(v,u){pass}_a (v,u),{pass}_b (v,u) を考えると、ポイントは、それぞれ ca,cb-c_a,-c_b
これを踏まえると、ca>cbc_a > c_b のとき、頂点 uu から passa(u,v){pass}_a (u,v)passb(v,u){pass}_b (v,u) のみを使って頂点 uu に戻ると cacb>0c_a-c_b>0 となり、正閉路が存在するとわかる。cb>cac_b > c_a のときも同様にして、正閉路が存在するとわかる。
よって、cacbc_a \neq c_b のときのみ正閉路が存在する。逆に、正閉路が存在するとき、正閉路内の 22 点を u,vu,v (u=vu=v も可) とすれば、cacbc_a \neq c_b となるパス passa(u,v),passb(u,v){pass}_a (u,v),{pass}_b (u,v) が存在する。なので、「正閉路が存在しない」 \Leftrightarrow 「任意の 22 頂点 (u,v)(u,v) について、頂点 uu から頂点 vv への移動によって得られるポイントは経路によらず一意」
また、「任意の 22 頂点 (u,v)(u,v) について、頂点 uu から頂点 vv への移動によって得られるポイントは経路によらず一意」であるとき、得られるポイントを cu,vc_{u,v} とおくと、「経路によらず一意」なので、任意の頂点 tt を用いて、cu,t+ct,v=cu,vc_{u,t}+c_{t,v}=c_{u,v}
さらに、cu,v=cv,uc_{u,v}=-c_{v,u} を用いると、ct,u+ct,v=cu,vc_{t,u}+c_{t,v}=c_{u,v}
よって、ある 11 点からのポイントがわかれば、任意の 22 点間のポイントがわかる。
ある 11 点からのポイントは、「経路によらず一意」であれば、BFS や DFS で求められる。そうでなくても、一意でなかった時点でどの 22 頂点間も inf なので BFS や DFS で問題ない。
ここまで、すべての頂点が連結のグラフを考えていたが、すべての頂点が連結でなくても、連結している部分グラフごとに同様に考えればいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

    cin >> n >> m >> q;

    // コストありグラフ
    vector<vector<pair<int, ll>>> g(n);
    // group の値が同じなら連結 (Union-Find とかを使うのもあり)
    vector<int> group(n);

    const ll notVisited = 1ll << 60;
    // ポイント (頂点 i に訪れていないなら notVisited)
    vector<ll> d(n, notVisited);

    // グラフ生成
    for (ll i = 0, u, v, c; i < m; ++i) {
        cin >> u >> v >> c;
        --u; --v;  // 0-indexed
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, -c);
    }

    // 連結グラフの数
    int cnt = 0;
    // 連結グラフ i に正閉路があるか
    vector<bool> isInf;
    // 連結グラフごとに BFS
    for (int i = 0; i < n; ++i) {
        // 訪れている (別の連結グラフの頂点) なら continue
        if (d[i] != notVisited) continue;

        // 連結グラフ cnt (cnt はグラフ番号) について調べる
        // BFS (i からのポイントを求める)
        queue<int> que;
        que.push(i);
        d[i] = 0;  // i から i のポイントは 0

        // i は連結グラフ cnt の頂点
        group[i] = cnt;
        // 連結グラフ cnt に正閉路があるかを false で初期化
        isInf.push_back(false);
        while (!que.empty()) {
            int v = que.front();
            que.pop();

            for (auto [to, cost] : g[v]) {
                if (d[to] == notVisited) {  // 訪れていないなら
                    group[to] = cnt;  // to は連結グラフ cnt の頂点
                    d[to] = d[v] + cost;
                    que.push(to);
                } else if (d[to] != d[v] + cost) {  // ポイントの総和が違うパスがあるなら
                    isInf[cnt] = true;  // 連結グラフ cnt には正閉路あり
                }
            }
        }
        ++cnt;  // グラフの数 (グラフの番号) を加算
    }

    // クエリへの回答
    for (int i = 0, x, y; i < q; ++i) {
        cin >> x >> y;
        --x; --y;  // 0-indexed
        if (group[x] != group[y]) {  // 違う連結グラフなら (連結でないなら)
            cout << "nan\n";
        } else if (isInf[group[x]]) {  // 正閉路があるなら
            cout << "inf\n";
        } else {  // 連結で正閉路がないなら
            cout << d[y] - d[x] << '\n';
        }
    }

    return 0;
}

G - Do Use Hexagon Grid 2

公式解説読んでなんとなく理解。
まず、Pi=(Xi,Yi),Pj=(Xj,Yj)P_i=(X_i,Y_i),P_j=(X_j,Y_j) とし、ΔXi,j=XjXi,ΔYi,j=YjYi\Delta X_{i,j}=X_j-X_i, \Delta Y_{i,j}=Y_j-Y_i とおくと、
  • ΔXi,j\Delta X_{i,j}ΔYi,j\Delta Y_{i,j} が「ともに正」か「ともに負」のとき、
    11 回の移動で、ΔXi,j|\Delta X_{i,j}|ΔYi,j|\Delta Y_{i,j}| を最大 11 ずつ減らせる。
  • ΔXi,j\Delta X_{i,j}ΔYi,j\Delta Y_{i,j} の「正負が違う」か「どちらかが 00」のとき、
    11 回の移動で、ΔXi,j|\Delta X_{i,j}|ΔYi,j|\Delta Y_{i,j}| のどちらかを最大 11 減らせる
これを踏まえると、
  • ΔXi,j\Delta X_{i,j}ΔYi,j\Delta Y_{i,j} が「ともに正」か「ともに負」のとき、
    距離は、max(ΔXi,j,ΔYi,j)\max(|\Delta X_{i,j}|,|\Delta Y_{i,j}|)
  • ΔXi,j\Delta X_{i,j}ΔYi,j\Delta Y_{i,j} の「正負が違う」か「どちらかが 00」のとき、
    距離は、ΔXi,j+ΔYi,j|\Delta X_{i,j}|+|\Delta Y_{i,j}|
ここで、
  • ΔXi,j\Delta X_{i,j}ΔYi,j\Delta Y_{i,j} が「ともに正」か「ともに負」のとき、
    ΔXi,jΔYi,j<ΔXi,j,ΔYi,j|\Delta X_{i,j}-\Delta Y_{i,j}| < |\Delta X_{i,j}|,|\Delta Y_{i,j}|
  • ΔXi,j\Delta X_{i,j}ΔYi,j\Delta Y_{i,j} の「正負が違う」か「どちらかが 00」のとき、
    ΔXi,j+ΔYi,j=ΔXi,jΔYi,jΔXi,j,ΔYi,j|\Delta X_{i,j}|+|\Delta Y_{i,j}|=|\Delta X_{i,j}-\Delta Y_{i,j}| \geq |\Delta X_{i,j}|,|\Delta Y_{i,j}|
であることを考慮すると、22 つの条件をまとめて、距離を、max(ΔXi,j,ΔYi,j,ΔXi,jΔYi,j)\max(|\Delta X_{i,j}|,|\Delta Y_{i,j}|,|\Delta X_{i,j}-\Delta Y_{i,j}|) とすることができる。
なので、(X,Y)(X,Y) で与えられるマスの座標を、(X,Y,XY)(X,Y,X-Y) に座標変換して、チェビシェフ距離を考えればいい。以降、(x,y,z)=(X,Y,XY)(x,y,z)=(X,Y,X-Y) とおく。
すると、与えられたマスの部分集合それぞれが、D×D×DD \times D \times D の立方体に収まるかを考えればよくなる。単純に考えると、立方体は O(XY(X+Y))O(XY(X+Y)) 個ほどあるが、このときの立方体は、部分集合の中の最小の xxminXminX、最小の yyminYminY、最小の zzminZminZ としたときの立方体区間 [minX,minX+D]×[minY,minY+D]×[minZ,minZ+D][minX,minX+D] \times [minY,minY+D] \times [minZ,minZ+D] としてよい。
立方体の個数は O(N3)O(N^3) 個であり、それぞれに対してすべてのマスを走査すると O(N4)O(N^4) になるが、minX,minYminX,minY を固定して、zz について差分更新すると O(N3)O(N^3) で収まる。
(公式解説のコードが公式解説の説明と若干違う (実質的には同じ) ので説明通りに組んでみました。)
(map を走査したら時間ギリギリだった…。公式解説のように map の中身を vector に移したほうがいいかも。)
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 正方形区間は [minX, minX + d] x [minY, minY + d] に固定して z はずらす
int cal(ll minX, ll minY, map<ll, vector<array<ll, 2>>> &p_zAll, ll d, vector<ll> &p2, const int mod) {
    ll maxX = minX + d, maxY = minY + d;
    ll ans = 0;

    // 「x = minX か」「y = minY か」「z = minZ か」の 8 通りに分けた
    // 立方体区間内のマスの数
    vector<int> cnt(8);
    // 添え字の 2 の 0 乗ビットは 「x = minX か」
    //      2 の 1 乗ビットは 「y = minY か」
    //      2 の 2 乗ビットは 「z = minZ か」

    // minZ + d まで走査するイテレータ
    auto itrZ = p_zAll.begin();
    // minZ をずらしながら
    for (auto itrMinZ = p_zAll.begin(); itrMinZ != p_zAll.end(); ++itrMinZ) {
        ll minZ = itrMinZ->first;
        ll maxZ = minZ + d;
        
        // [minX, minX + d] x [minY, minY + d] x [minZ, minZ + d] のマスをカウント
        for (; itrZ != p_zAll.end(); ++itrZ) {
            ll z = itrZ->first;

            if (z > maxZ) break;  // minZ + d まで

            // [minX, minX + d] x [minY, minY + d] のマスをカウント
            for (auto [x, y] : itrZ->second) {
                if (minX <= x && x <= maxX && minY <= y && y <= maxY) {
                    // z == minZ の場合もとりあえず z != minZ のところでカウント
                    ++cnt[(x == minX) | (y == minY) << 1];
                }
            }
        }

        // z == minZ のパターンは初期化
        for (int i = 4; i < 8; ++i) cnt[i] = 0;

        // z == minZ である [minX, minX + d] x [minY, minY + d] のマスをカウント
        for (auto [x, y] : itrMinZ->second) {
            if (minX <= x && x <= maxX && minY <= y && y <= maxY) {
                int flag = (x == minX) | (y == minY) << 1;
                // z != minZ でカウントしてたので入れ替え
                --cnt[flag];
                ++cnt[flag | 4];
            }
        }

        // x == minX, y == minY, z == minZ が true のマスがそれぞれ 1 つ以上必要
        // 7 があるなら、それ以外は自由
        ans += (p2[cnt[7]] - 1) * p2[cnt[0] + cnt[1] + cnt[2] + cnt[3] + cnt[4] + cnt[5] + cnt[6]] % mod;
        // 7 がなくて 6 があるなら x == minX が true の満たすマスが必要
        ans += (p2[cnt[6]] - 1) * (p2[cnt[1] + cnt[3] + cnt[5]] - 1) % mod * p2[cnt[0] + cnt[2] + cnt[4]] % mod;
        // 7, 6 がなくて 5 があるなら y == minY が true のマスが必要
        ans += (p2[cnt[5]] - 1) * (p2[cnt[2] + cnt[3]] - 1) % mod * p2[cnt[0] + cnt[1] + cnt[4]] % mod;
        // 7, 6, 5 がなくて 3 があるなら z == minZ が true のマスが必要
        ans += (p2[cnt[3]] - 1) * (p2[cnt[4]] - 1) % mod * p2[cnt[0] + cnt[1] + cnt[2]] % mod;
        // 7, 6, 5, 3 がないなら 1, 2, 4 全部必要
        ans += (p2[cnt[4]] - 1) * (p2[cnt[2]] - 1) % mod * (p2[cnt[1]] - 1) %  mod * p2[cnt[0]] % mod;
        ans %= mod;
    }

    return ans;
}

int main() {
    int n;
    ll d;
    const int mod = 998244353;
    int ans = 0;

    cin >> n >> d;

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

    // 座標変換 (X, Y) -> (x, y, z) ((x, y, z) = (X, Y, X - Y))
    // z ごとに座標変換後のマスの値 ({x, y}) を格納
    map<ll, vector<array<ll, 2>>> p_zAll;
    // 座標変換後のマスの x, y の値を格納
    set<ll> xAll, yAll;
    for (int i = 0, X, Y, z; i < n; ++i) {
        cin >> X >> Y;
        z = X - Y;
        p_zAll[z].push_back({X, Y});
        xAll.insert(X);
        yAll.insert(Y);
    }

    // すべての組 (x, y) に対して z をずらしながら
    // 立方体区間 [x, x + d] x [y, y + d] x [z, z + d] を走査
    for (ll x : xAll) {
        for (ll y : yAll) {
            (ans += cal(x, y, p_zAll, d, p2, mod)) %= mod;
        }
    }

    cout << ans;
}

Ex - Substring Sort

編集中…。

Discussion

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