Ccmmutty logo
Commutty IT
0 pv17 min read

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

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

A - Majority

NN の過半数となる最小の値は、N2+1\left\lfloor \dfrac{N}{2} \right\rfloor +1 なので、(For の数) N2+1\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 関数などを用いて SiS_i の末尾 33 文字だけ残せば、あとは、比較するだけ。比較は、22 重ループで O(NM)O(NM)set を使えば O(NlogM)O(N \log M) とか。
SiS_i 11 つで、22 以上加算しないように注意。
↓ こんな感じ。
#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=N1M = N-1
  • 各頂点から出る辺がそれぞれ 22 本以下
  • すべての頂点が連結
をすべて満たすこと。これらを満たすかどうか判断すればいい。
連結判定は、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

SSTT を先頭から比較したときに一致している文字数を frontfront、末尾から比較したときに一致している文字数を backback とおくと、「xfrontx \leq front」かつ「Txback|T|-x \leq back」なら SS'TT はマッチし、そうでなければマッチしない。なので、frontfrontbackback を求めれば 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

LCPLCP が最大になるのは、辞書順で隣り合う 22 つの文字列を比較したときのみであるので、それを比較すれば OK。
比較が、合計で O(N)O(N)、ソートが O(NlogN)O(N \log N) なので、O(NlogN)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(N3)O(N^3) から O(N2)O(N^2) に落ちるとか知らんよ…(´・ω・`)
一応、O(N3)O(N^3) だと仮定しても、O(N2logN)O(N^2 \log N) に落として通すこともできる。それを解説。
dp[t][i][j]dp[t][i][j] を (頂点 ii を部分木としたとき、連結成分数が jj であるものの通り数 (t=1t=1 なら iVi \in Vt=0t=0 なら iVi \notin V)) とおくと、公式解説と同様の考え方で、すべての ii で初期値を dp[0][i][0]=1dp[0][i][0]=1dp[1][i][1]=1dp[1][i][1]=1 とすると、vv を親、aa を子として
dp[0][v][k]=i+j=kdp[0][v][i]×(dp[0][a][j]+dp[1][a][j])dp[1][v][k]=i+j=kdp[1][v][i]×dp[0][a][j]dp[1][v][k1]=i+j=kdp[1][v][i]×dp[1][a][j]\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*}
で、遷移する。k1k-1 を消すと、
dp[0][v][k]=i+j=kdp[0][v][i]×(dp[0][a][j]+dp[1][a][j])dp[1][v][k]=i+j=kdp[1][v][i]×(dp[0][a][j]+dp[1][a][j+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]dp0[j]=dp[0][a][j]+dp[1][a][j]dp1[j]=dp[0][a][j]+dp[1][a][j+1]dp1[j]=dp[0][a][j]+dp[1][a][j+1] とおくと、
dp[0][v][k]=i+j=kdp[0][v][i]×dp0[j]dp[1][v][k]=i+j=kdp[1][v][i]×dp1[j]\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]dp[0][v]dp0dp0dp[1][v]dp[1][v]dp1dp1 で畳み込みできる。遷移数は、辺の数なので O(N)O(N)、各遷移、畳み込みで O(NlogN)O(N \log N) で計算できるので、合計で O(N2logN)O(N^2 \log N)
オーダーがギリギリなので、DP の配列の大きさを部分木の頂点数で調節して高速化 (全部 N+2N+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 やセグメント木で累積和取ってにぶたんっぽいけど、カードの得点が変わるのがややこしい。NN 枚のカードのみで BIT やセグメント木を作ると、得点の変更が大変になる。
クエリ先読みして、それを含めて作ると、降順を崩さずに得点の変更ができる。
なので、あとは実装するだけ (実装が大変なのだけど…)。オーダーは O(Nlog2N)O(N \log^2 N)。BIT やセグメント木上でにぶたんすれば O(NlogN)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(N3)O(N^3) では間に合わないので bitset 高速化する。
ワーシャルフロイドの 11 番外側のループの添え字を昇順に遷移させる場合、添え字が ii のときに jkj \rightarrow k への経路が存在するなら、経路上の頂点の番号の最大値は ii 以下である。
そのため、ワーシャルフロイドに、d[j][k]d[j][k] として bool\text{bool} 値 (jkj \rightarrow k への経路が存在するか) を持たせることで、d[j][k]d[j][k]false\text{false} から true\text{true} に切り替わったときの ii が、頂点 jj から頂点 kk への経路のコストの最小値の候補となる。
そのような iiij,ki_{j,k} とおくと、頂点 jj から頂点 kk への経路のコストの最小値は、経路があれば min(ij,k,j,k)\min(i_{j,k},j,k)、なければ -1 である。
また、ワーシャルフロイドの遷移の計算式は
d[j][k]=d[j][k] OR (dp[j][i] AND dp[i][k])d[j][k]=d[j][k] \text{ OR } (dp[j][i] \text{ AND } dp[i][k])
なので、bitset で
d[j]={d[j] OR dp[i](dp[j][i]=true)d[j](dp[j][i]=false)d[j]= \begin{cases} d[j] \text{ OR } dp[i] & (dp[j][i] =\text{true}) \\ d[j] & (dp[j][i] =\text{false}) \end{cases}
として高速化ができる。
また、ij,ki_{j,k} 11 つ求めるのに O(N)O(N) かかるので、すべての j,kj,k に対して ij,ki_{j,k} を求めると、O(N3)O(N^3) かかる。そのため、クエリ先読みして、O(Q)O(Q) 個のみ求める。
オーダーは、bitset 高速化が bitbit 倍高速になるとして O(N3/bit+NQ)O(N^3 / bit +NQ)bit=64bit=64 から、N3/bit=1.25×108N^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;
}

Discussion

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