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

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

https://cdn.magicode.io/media/notebox/4b093452-0584-422b-87ff-ca523d35fc0b.jpeg

ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)

A - Majority

N

の過半数となる最小の値は、

\left\lfloor \dfrac{N}{2} \right\rfloor +1

なので、(For の数)

\geq \left\lfloor \dfrac{N}{2} \right\rfloor +1

かどうか判断すれば OK。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    int cnt = 0;
    string s;

    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> s;
        if (s == "For") ++cnt;
    }

    cout << (cnt >= n / 2 + 1 ? "Yes" : "No");

    return 0;
}

B - Postal Card

substr 関数などを用いて

S_i

の末尾

3

文字だけ残せば、あとは、比較するだけ。比較は、

2

重ループで

O(NM)

、set を使えば

O(N \log M)

とか。

S_i

1

つで、

2

以上加算しないように注意。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    int cnt = 0;

    cin >> n >> m;

    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        s[i] = s[i].substr(3, 3);  // 末尾 3 文字だけ残す
    }

    string t;
    set<string> ts;  // T_i を set に格納
    for (int i = 0; i < m; ++i) {
        cin >> t;
        ts.insert(t);
    }

    // S_i の末尾 3 文字と一致する T_i が存在するなら 1 加算
    for (int i = 0; i < n; ++i) {
        if (ts.find(s[i]) != ts.end()) ++cnt;
    }

    cout << cnt;

    return 0;
}

C - Path Graph?

ざっくり言うと、グラフが一直線になるか判断する問題。

条件は、

$M = N-1$
各頂点から出る辺がそれぞれ $2$ 本以下
すべての頂点が連結

をすべて満たすこと。これらを満たすかどうか判断すればいい。

連結判定は、DFS、BFS、Union-Find などでできる。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

void dfs(int v, int p, vector<vector<int>>& g, int& cnt) {
    ++cnt;

    for (int a : g[v]) {
        if (a != p) {
            dfs(a, v, g, cnt);
        }
    }

    return;
}

int main() {
    int n, m;

    cin >> n >> m;

    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v); g[v].push_back(u);
    }

    if (m != n - 1) {
        cout << "No";
        return 0;
    }

    for (int i = 0; i < n; ++i) {
        if (g[i].size() > 2) {
            cout << "No";
            return 0;
        }
    }

    int cnt = 0;  // 頂点 0 と連結である頂点の数 (頂点 0 を含む)
    dfs(0, -1, g, cnt);
    if (cnt != n) {
        cout << "No";
        return 0;
    }

    cout << "Yes";

    return 0;
}

D - Match or Not

S

と

T

を先頭から比較したときに一致している文字数を

front

、末尾から比較したときに一致している文字数を

back

とおくと、「

x \leq front

」かつ「

|T|-x \leq back

」なら

S'

と

T

はマッチし、そうでなければマッチしない。なので、

front

と

back

を求めれば OK。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s, t;

    cin >> s >> t;

    int sSize = s.size(), tSize = t.size();
    int front, back;
    for (front = 0; front < tSize; ++front) {
        if (!(s[front] == '?' || t[front] == '?' || s[front] == t[front])) {
            break;
        }
    }
    for (back = 0; back < tSize; ++back) {
        int sIdx = sSize - 1 - back, tIdx = tSize - 1 - back;
        if (!(s[sIdx] == '?' || t[tIdx] == '?' || s[sIdx] == t[tIdx])) {
            break;
        }
    }

    for (int i = 0; i <= tSize; ++i) {
        cout << (i <= front && tSize - i <= back ? "Yes" : "No") << '\n';
    }

    return 0;
}

E - Karuta

LCP

が最大になるのは、辞書順で隣り合う

2

つの文字列を比較したときのみであるので、それを比較すれば OK。
比較が、合計で

O(N)

、ソートが

O(N \log N)

なので、

O(N \log N)

で解ける。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

// LCP の計算
int culLCP(string s, string t) {
    int sz = min(s.size(), t.size());
    int ret;
    for (ret = 0; ret < sz; ++ret)
        if (s[ret] != t[ret]) break;

    return ret;
}

int main() {
    int n;

    cin >> n;

    // 組 (S_i, i)
    vector<pair<string, int>> s(n);
    for (int i = 0; i < n; ++i) cin >> s[i].first, s[i].second = i;

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

    vector<int> ans(n);
    for (int i = 1; i < n; ++i) {
        int LCP = culLCP(s[i - 1].first, s[i].first);
        ans[s[i - 1].second] = max(ans[s[i - 1].second], LCP);
        ans[s[i].second] = max(ans[s[i].second], LCP);
    }

    for (int i = 0; i < n; ++i) cout << ans[i] << '\n';

    return 0;
}

F - Components

木 DP わからん…。ループ数を部分木の頂点数にすると

O(N^3)

から

O(N^2)

に落ちるとか知らんよ…(´･ω･｀)

一応、

O(N^3)

だと仮定しても、

O(N^2 \log N)

に落として通すこともできる。それを解説。

dp[t][i][j]

を (頂点

i

を部分木としたとき、連結成分数が

j

であるものの通り数 (

t=1

なら

i \in V

、

t=0

なら

i \notin V

)) とおくと、公式解説と同様の考え方で、すべての

i

で初期値を

dp[0][i][0]=1

、

dp[1][i][1]=1

とすると、

v

を親、

a

を子として

\begin{align*} dp[0][v][k]&=\sum_{i+j=k} dp[0][v][i] \times (dp[0][a][j]+dp[1][a][j]) \\ dp[1][v][k]&=\sum_{i+j=k} dp[1][v][i] \times dp[0][a][j] \\ dp[1][v][k-1]&=\sum_{i+j=k} dp[1][v][i] \times dp[1][a][j] \end{align*}

で、遷移する。

k-1

を消すと、

\begin{align*} dp[0][v][k]&=\sum_{i+j=k} dp[0][v][i] \times (dp[0][a][j]+dp[1][a][j]) \\ dp[1][v][k]&=\sum_{i+j=k} dp[1][v][i] \times (dp[0][a][j]+dp[1][a][j+1]) \end{align*}

dp0[j]=dp[0][a][j]+dp[1][a][j]

、

dp1[j]=dp[0][a][j]+dp[1][a][j+1]

とおくと、

\begin{align*} dp[0][v][k]&=\sum_{i+j=k} dp[0][v][i] \times dp0[j] \\ dp[1][v][k]&=\sum_{i+j=k} dp[1][v][i] \times dp1[j] \end{align*}

なので、

dp[0][v]

と

dp0

、

dp[1][v]

と

dp1

で畳み込みできる。遷移数は、辺の数なので

O(N)

、各遷移、畳み込みで

O(N \log N)

で計算できるので、合計で

O(N^2 \log N)

。

オーダーがギリギリなので、DP の配列の大きさを部分木の頂点数で調節して高速化 (全部

N+2

とかにしたら TLE しました)。

↓ こんな感じ。

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

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int dfs(int v, int p, vector<vector<int>>& g, vector<vector<vector<mint>>>& dp) {
    if (g[v].size() == 1 && p != -1) {
        return 1;
    }

    int ret = 1;
    for (int a : g[v]) {
        if (a != p) {
            ret += dfs(a, v, g, dp);

            int dp0Size = dp[0][a].size(), dp1Size = dp[1][a].size();
            vector<mint> dp0(dp0Size), dp1(dp1Size);

            for (int i = 0; i < dp0Size; ++i) dp0[i] = dp[0][a][i] + dp[1][a][i];
            dp[0][v] = convolution(dp[0][v], dp0);
            dp[0][v].resize(ret + 2);

            for (int i = 0; i < dp1Size - 1; ++i) dp1[i] = dp[0][a][i] + dp[1][a][i + 1];
            dp[1][v] = convolution(dp[1][v], dp1);
            dp[1][v].resize(ret + 2);
        }
    }

    return ret;
}

int main() {
    int n;

    cin >> n;

    vector<vector<vector<mint>>> dp(2, vector<vector<mint>>(n, vector<mint>(2)));
    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v); g[v].push_back(u);
    }

    for (int i = 0; i < n; ++i) {
        dp[0][i][0] = 1; dp[1][i][1] = 1;
    }

    dfs(0, -1, g, dp);

    for (int i = 1; i <= n; ++i) cout << (dp[0][0][i] + dp[1][0][i]).val() << '\n';

    return 0;
}

G - Balance Update Query

BIT やセグメント木で累積和取ってにぶたんっぽいけど、カードの得点が変わるのがややこしい。

N

枚のカードのみで BIT やセグメント木を作ると、得点の変更が大変になる。

クエリ先読みして、それを含めて作ると、降順を崩さずに得点の変更ができる。

なので、あとは実装するだけ (実装が大変なのだけど…)。オーダーは

O(N \log^2 N)

。BIT やセグメント木上でにぶたんすれば

O(N \log N)

に落とせる。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template <typename T>  // 0-indexed
class BIT {
    int n;
    vector<T> data;

   public:
    BIT(int _n) : n(_n), data(n + 1, 0) {}

    void add(int a, T w) {
        for (int i = ++a; i <= n; i += i & -i) data[i] += w;
    }

    T get(int a) { return sum(a, a + 1); }

    void set(int a, T w) { add(a, w - get(a)); }

    T sum(int a) {  // [0, a)
        T ret = 0;
        for (int i = a; i > 0; i -= i & -i) ret += data[i];
        return ret;
    }

    T sum(int l, int r) {  // [l, r)
        T ret = 0;
        for (int i = r; i > 0; i -= i & -i) ret += data[i];
        for (int i = l; i > 0; i -= i & -i) ret -= data[i];
        return ret;
    }
};

int main() {
    int n, q;

    cin >> n;

    vector<pair<ll, int>> card(n);
    for (int i = 0, a, b; i < n; ++i) {
        cin >> a >> b;
        card[i] = {a, b};
    }

    cin >> q;

    vector<tuple<int, int, ll>> query(q);
    for (int i = 0, t, x, y; i < q; ++i) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y;
            query[i] = {t, --x, y};
            card.emplace_back(y, -1);
        } else if (t == 2) {
            cin >> x >> y;
            query[i] = {t, --x, y};
        } else if (t == 3) {
            cin >> x;
            query[i] = {t, x, -1};
        }
    }

    int cardSize = card.size();
    vector<int> rev(cardSize);  // 得点が i 番目に大きいカードの添え字
    iota(rev.begin(), rev.end(), 0);
    auto f = [&](int i, int j) { return card[i].first < card[j].first; };
    sort(rev.rbegin(), rev.rend(), f);

    vector<int> idx(cardSize);  // カード i の得点が何番目に大きいか
    for (int i = 0, sz = cardSize; i < sz; ++i) {
        idx[rev[i]] = i;
    }

    // num は カード枚数、score は (得点) * (カード枚数)
    BIT<ll> num(cardSize), score(cardSize);
    for (int i = 0; i < n; ++i) {
        auto [a, b] = card[i];
        num.add(idx[i], b);
        score.add(idx[i], a * b);
    }

    for (int i = 0, qi = n; i < q; ++i) {
        auto [t, x, y] = query[i];
        if (t == 1) {
            card[x].first = y;  // カードの得点を書き換え

            // カードの得点が変わるので、添え字も書き換え
            num.set(idx[x], 0);
            score.set(idx[x], 0);
            idx[x] = idx[qi++];
            num.set(idx[x], card[x].second);
            score.set(idx[x], y * card[x].second);
        } else if (t == 2) {
            card[x].second = y;  // カードの枚数を書き換え

            num.set(idx[x], y);
            score.set(idx[x], card[x].first * y);
        } else if (t == 3) {
            int ok = -1, ng = cardSize + 1;
            for (int mid = (ok + ng) / 2; abs(ok - ng) > 1; mid = (ok + ng) / 2) {
                if (num.sum(mid) < x) ok = mid;
                else ng = mid;
            }
            if (ok == cardSize) cout << -1 << '\n';
            else cout << score.sum(ok) + card[rev[ok]].first * (x - num.sum(ok)) << '\n';
        }
    }

    return 0;
}

Ex - Directed Graph and Query

ワーシャルフロイド。

O(N^3)

では間に合わないので bitset 高速化する。

ワーシャルフロイドの

1

番外側のループの添え字を昇順に遷移させる場合、添え字が

i

のときに

j \rightarrow k

への経路が存在するなら、経路上の頂点の番号の最大値は

i

以下である。
そのため、ワーシャルフロイドに、

d[j][k]

として

\text{bool}

値 (

j \rightarrow k

への経路が存在するか) を持たせることで、

d[j][k]

が

\text{false}

から

\text{true}

に切り替わったときの

i

が、頂点

j

から頂点

k

への経路のコストの最小値の候補となる。
そのような

i

を

i_{j,k}

とおくと、頂点

j

から頂点

k

への経路のコストの最小値は、経路があれば

\min(i_{j,k},j,k)

、なければ -1 である。

また、ワーシャルフロイドの遷移の計算式は

d[j][k]=d[j][k] \text{ OR } (dp[j][i] \text{ AND } dp[i][k])

なので、bitset で

d[j]= \begin{cases} d[j] \text{ OR } dp[i] & (dp[j][i] =\text{true}) \\ d[j] & (dp[j][i] =\text{false}) \end{cases}

として高速化ができる。

また、

i_{j,k}

1

つ求めるのに

O(N)

かかるので、すべての

j,k

に対して

i_{j,k}

を求めると、

O(N^3)

かかる。そのため、クエリ先読みして、

O(Q)

個のみ求める。

オーダーは、bitset 高速化が

bit

倍高速になるとして

O(N^3 / bit +NQ)

。

bit=64

から、

N^3/bit=1.25 \times 10^8

なので間に合う。

↓ こんな感じ。

#include <bits/stdc++.h>

using namespace std;

class WarshallFloyd {
   private:
    static const int bitSize = 2000;
    int n;
    vector<bitset<bitSize>> d;
    vector<pair<int, int>> query;
    vector<int> ans;

   public:
    WarshallFloyd(int v) : n(v), d(v, bitset<bitSize>()) {
        for (int i = 0; i < n; i++) d[i][i] = 0;
    }

    void edge(int from, int to, bool cost) { d[from][to] = cost; }

    vector<int> solve() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[j][i]) d[j] |= d[i];
            }
            for (int j = 0, sz = query.size(); j < sz; ++j) {
                auto [u, v] = query[j];
                if (d[u][v] && ans[j] == -1) ans[j] = i;
            }
        }
        return ans;
    }

    // クエリ読み込み
    void setQuery(vector<pair<int, int>> &q) {
        query = q;
        ans.assign(query.size(), -1);
    }
};

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

    cin >> n >> m;

    WarshallFloyd w(n);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u; --v;
        w.edge(u, v, true);
    }

    cin >> q;

    vector<pair<int, int>> query(q);
    for (int i = 0, u, v; i < q; ++i) {
        cin >> u >> v;
        --u; --v;
        query[i] = {u, v};
    }
    w.setQuery(query);

    vector<int> ans(w.solve());
    for (int i = 0, sz = ans.size(); i < sz; ++i) {
        auto [u, v] = query[i];
        cout << (ans[i] == -1 ? -1 : max({u, v, ans[i]}) + 1) << '\n';
    }

    return 0;
}

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

ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)

A - Majority

B - Postal Card

C - Path Graph?

D - Match or Not

E - Karuta

F - Components

G - Balance Update Query

Ex - Directed Graph and Query

Discussion

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