16か月前公開・15か月前更新・18 min read

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

AtCoder競技プログラミングAtCoderBeginnerContest

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

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

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

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

A - Pawn on a Grid

# を数えるだけ。

2

重ループとか。

↓ こんな感じ。

#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

S

の定義から、

A_1=S_1

、

A_k=S_k-S_{k-1}

(k \geq 2)

だとわかるので、それを出力すれば OK。

S_0=0

を追加すると、

A_k=S_k-S_{k-1}

(k \geq 1)

になって、場合分けがいらないので楽ちん。

ちなみに、

S

は「

A

の累積和」というやつで、

S_r-S_{l-1}=A_l+A_{l+1}+ \cdots +A_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

S

の

i-1

文字目と

T

の

i-1

文字目までが一致していて、

S

の

i

文字目と

T

の

i

文字目が一致していなければ、そこが候補のうちの

1

つ。

S

の最後の文字まで全部一致しているなら

T

の一番最後の文字が候補のうちの

1

つ。
なので、

i=0

から順に文字が一致しているか判別すればいい。

S

の末尾に絶対一致しない文字を追加すると、「

S

の最後の文字まで全部一致しているなら」を場合分けしなくてよくなる。

↓ こんな感じ。

#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[n-1])+g(dp[n-2])

みたいな形じゃなく、

dp[n-2]

f(dp[n]),dp[n-1]

g(dp[n-1])

みたいな形にしたらややこしくなった(´・ω・｀)　…今回の敗因。
一応、そのややこしいほうを解説…。

prob[i]=

(体力が

i

になる確率)、

dp[i]=\sum_k k p_{k,i}

(

p_{k,i}

k

回の攻撃で体力が

i

になる確率) (

i

が 0 未満の場合は

i=0

に含む)とすると、

\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]=0

で、

i=N, \cdots ,1

の順に、

\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]

が答えとなる。ダメージが

N

を超える場合の帳尻合わせを、公式解説は最初にやっているけど、この解説では最後にやっているので

prob

が必要になってる？

↓ こんな感じ。

#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

時間外で解けました。

到達可能かどうかはポイントと関係ない。ポイントを無視すれば無向グラフなので、「頂点

u

から頂点

v

に到達可能」

\Leftrightarrow

「頂点

u

と頂点

v

は連結」。なので、

X_i

と

Y_i

が連結でないなら、nan

X_i

と

Y_i

が連結で、正閉路とも連結なら、inf

X_i

と

Y_i

が連結で、正閉路とは連結でないならポイントの最大値

を出力すればいい。しかし、正閉路を探したり、任意の

2

点間のポイントの最大値を求めたりするために、「ポイントの正負を逆転して、ワーシャルフロイド法を使う」とかでは、

O(N^3)

で全然間に合わない。なので、別の方法を考えたい。

以下、すべての頂点が連結のグラフを考える。
ポイントの総和が

c_a,c_b

の頂点

u

から頂点

v

へのパス

{pass}_a (u,v),{pass}_b (u,v)

を考えてみる。このとき、パスの頂点を頂点

v

から頂点

u

へ逆順に移動するパス

{pass}_a (v,u),{pass}_b (v,u)

を考えると、ポイントは、それぞれ

-c_a,-c_b

。
これを踏まえると、

c_a > c_b

のとき、頂点

u

から

{pass}_a (u,v)

と

{pass}_b (v,u)

のみを使って頂点

u

に戻ると

c_a-c_b>0

となり、正閉路が存在するとわかる。

c_b > c_a

のときも同様にして、正閉路が存在するとわかる。
よって、

c_a \neq c_b

のときのみ正閉路が存在する。逆に、正閉路が存在するとき、正閉路内の

2

点を

u,v

(

u=v

も可) とすれば、

c_a \neq c_b

となるパス

{pass}_a (u,v),{pass}_b (u,v)

が存在する。なので、「正閉路が存在しない」

\Leftrightarrow

「任意の

2

頂点

(u,v)

について、頂点

u

から頂点

v

への移動によって得られるポイントは経路によらず一意」

また、「任意の

2

頂点

(u,v)

について、頂点

u

から頂点

v

への移動によって得られるポイントは経路によらず一意」であるとき、得られるポイントを

c_{u,v}

とおくと、「経路によらず一意」なので、任意の頂点

t

を用いて、

c_{u,t}+c_{t,v}=c_{u,v}

。
さらに、

c_{u,v}=-c_{v,u}

を用いると、

c_{t,u}+c_{t,v}=c_{u,v}

。
よって、ある

1

点からのポイントがわかれば、任意の

2

点間のポイントがわかる。

ある

1

点からのポイントは、「経路によらず一意」であれば、BFS や DFS で求められる。そうでなくても、一意でなかった時点でどの

2

頂点間も 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

公式解説読んでなんとなく理解。

まず、

P_i=(X_i,Y_i),P_j=(X_j,Y_j)

とし、

\Delta X_{i,j}=X_j-X_i, \Delta Y_{i,j}=Y_j-Y_i

とおくと、

$\Delta X_{i,j}$ と $\Delta Y_{i,j}$ が「ともに正」か「ともに負」のとき、
$1$ 回の移動で、 $|\Delta X_{i,j}|$ と $|\Delta Y_{i,j}|$ を最大 $1$ ずつ減らせる。
$\Delta X_{i,j}$ と $\Delta Y_{i,j}$ の「正負が違う」か「どちらかが $0$ 」のとき、
$1$ 回の移動で、 $|\Delta X_{i,j}|$ と $|\Delta Y_{i,j}|$ のどちらかを最大 $1$ 減らせる

これを踏まえると、

$\Delta X_{i,j}$ と $\Delta Y_{i,j}$ が「ともに正」か「ともに負」のとき、
距離は、 $\max(|\Delta X_{i,j}|,|\Delta Y_{i,j}|)$
$\Delta X_{i,j}$ と $\Delta Y_{i,j}$ の「正負が違う」か「どちらかが $0$ 」のとき、
距離は、 $|\Delta X_{i,j}|+|\Delta Y_{i,j}|$

ここで、

$\Delta X_{i,j}$ と $\Delta Y_{i,j}$ が「ともに正」か「ともに負」のとき、
$|\Delta X_{i,j}-\Delta Y_{i,j}| < |\Delta X_{i,j}|,|\Delta Y_{i,j}|$
$\Delta X_{i,j}$ と $\Delta Y_{i,j}$ の「正負が違う」か「どちらかが $0$ 」のとき、
$|\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}|$

であることを考慮すると、

2

つの条件をまとめて、距離を、

\max(|\Delta X_{i,j}|,|\Delta Y_{i,j}|,|\Delta X_{i,j}-\Delta Y_{i,j}|)

とすることができる。

なので、

(X,Y)

で与えられるマスの座標を、

(X,Y,X-Y)

に座標変換して、チェビシェフ距離を考えればいい。以降、

(x,y,z)=(X,Y,X-Y)

とおく。

すると、与えられたマスの部分集合それぞれが、

D \times D \times D

の立方体に収まるかを考えればよくなる。単純に考えると、立方体は

O(XY(X+Y))

個ほどあるが、このときの立方体は、部分集合の中の最小の

x

を

minX

、最小の

y

を

minY

、最小の

z

を

minZ

としたときの立方体区間

[minX,minX+D] \times [minY,minY+D] \times [minZ,minZ+D]

としてよい。
立方体の個数は

O(N^3)

個であり、それぞれに対してすべてのマスを走査すると

O(N^4)

になるが、

minX,minY

を固定して、

z

について差分更新すると

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

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

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？