第二回 アルゴリズム実技検定 (PAST) 全問一言解説！！

リクエストがあれば実装つきで、解説動画撮るので気軽にどうぞ

全体の感想としては、前回以上に典型色感が強い。

難易度感は前回より難しい気もする？

かなり知識で殴った感があって、想定はひょっとしたらもっと天才なのかもしれないけど。

ちなみに後で記述するので分かりますが、3問もセグ木を使い、そのうち1問はHLDです…

ちなみに個人的な難易度感は

A-G, I(本当に問題文に書いてある通りにやるだけ) < H, J, K < L(想定が分かってない) < O < N <<<<<<<<<<<<<<<< M

って感じでした。M以外までは比較的早かったんですけど、たしかMで3hぐらい使ってます(しょうもないバグにかなりはまった)(バグ抜きでも普通に悩んだ)

A - エレベーター

書いてある通りに実装しましょう。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    string s, t; cin >> s >> t;
    vector<string> vs;
    for (int i = 9; i >= 1; i--) {
        string tmp;
        tmp += 'B';
        tmp += to_string(i);
        vs.push_back(tmp);
    }
    for (int i = 1; i <= 9; i++) {
        string tmp;
        tmp += to_string(i);
        tmp += 'F';
        vs.push_back(tmp);
    }
    ll a, b;
    for (int i = 0; i < vs.size(); i++) {
        if (vs[i] == s) a = i;
        if (vs[i] == t) b = i;
    }
    cout << llabs(a - b) << endl;
    return 0;
} 

B - 多数決

これもいろいろ書き方はあると思いますが、書いてある通りに実装しましょう。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */
    string s; cin >> s;
    vector<pair<int, int>> vp(3);
    vp[0].second = 0;
    vp[1].second = 1;
    vp[2].second = 2;
    for (int i = 0; i < s.size(); i++) {
        vp[s[i] - 'a'].first++;
    }
    sort(vp.rbegin(), vp.rend());
    cout << (char)(vp[0].second + 'a') << endl;
    return 0;
} 

C - 山崩し

これも問題文に書いてある通りに実装しましょう。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int dh[3] = { 1,1,1 };
int dw[3] = { -1,0,1 };

int main()
{
    
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n; cin >> n;
    vector<string> vs(n); for (int i = 0; i < n; i++) cin >> vs[i];

    for (int h = n - 2; h >= 0; h--) {
        for (int w = 0; w < n * 2 - 1; w++) {
            if (vs[h][w] != '#') continue;
            for (int i = 0; i < 3; i++) {
                int nh = h + dh[i];
                int nw = w + dw[i];
                if (nw < 0 or nw >= n * 2 - 1) continue;
                if (vs[nh][nw] == 'X') vs[h][w] = 'X';
            }
        }
    }
    for (int i = 0; i < n; i++) cout << vs[i] << "\n";
    return 0;
} 

D - パターンマッチ

3文字以下なので全部列挙してからチェックしましょう。'.'の代わりに'#'を使っているけど気にしないで…

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int dh[3] = { 1,1,1 };
int dw[3] = { -1,0,1 };

int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    vector<char> alp;
    for (int i = 0; i < 26; i++) alp.push_back((char)('a' + i));
    alp.push_back('#');
    vector<string> vs;
    for (int i = 0; i < alp.size(); i++) {
        string s;
        s += alp[i];
        vs.push_back(s);
    }
    for (int i = 0; i < alp.size(); i++) {
        for (int j = 0; j < alp.size(); j++) {
            string s;
            s += alp[i];
            s += alp[j];
            vs.push_back(s);
        }
    }
    for (int i = 0; i < alp.size(); i++) {
        for (int j = 0; j < alp.size(); j++) {
            for (int k = 0; k < alp.size(); k++) {
                string s;
                s += alp[i];
                s += alp[j];
                s += alp[k];
                vs.push_back(s);
            }
        }
    }
    string s; cin >> s;
    ll res = 0;
    for (string t : vs) {
        bool ok = false;
        for (int i = 0; i <= (int)s.size() - (int)t.size(); i++) {
            bool flag = true;
            for (int j = i; j < i + t.size(); j++) {
                if (!(t[j - i] == '#' or s[j] == t[j - i])) {
                    flag = false;
                    break;
                }
            }
            ok |= flag;
        }
        if (ok) res++;
    }
    cout << res << endl;
    return 0;
} 

E - 順列

愚直にシュミレーションしましょう。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int solve(int i, int n, vector<int>& a) {
    int cur = a[i];
    int res = 1;
    while (cur != i) {
        res++;
        cur = a[cur];
    }
    return res;
}
int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    int n; scanf("%d", &n);
    vector<int> a(n); for (int i = 0; i < n; i++) scanf("%d", &a[i]), a[i]--;
    for (int i = 0; i < n; i++) {
        int res = solve(i, n, a);
        printf("%d", res);
        if (i + 1 == n) puts("");
        else printf(" ");
    }
    return 0;
} 

F - タスクの消化

慣れてない人には難しいかもしれません。

日目までにできる仕事の中から、一番おおきいものを使っていきましょう。

これはpriority_queueなどを用いることでできます。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    int n; scanf("%d", &n);
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        int a, b; scanf("%d %d", &a, &b);
        a--;
        g[a].push_back(b);
    }
    priority_queue<ll> pq;
    ll res = 0;
    for (int i = 0; i < n; i++) {
        for (auto e : g[i]) pq.push(e);
        res += pq.top();
        pq.pop();
        cout << res << "\n";
    }
    return 0;
} 

G - ストリング・クエリ

愚直にシミュレーションです！！とはいっても本当に個入れてると間に合いません。

文字と個数を保持しながら実装しましょう。後ろから入れて、前から出すだけなのでqueueなどのデータ構造を使いましょう(寝ぼけてたのかなぜかdequeを使っていますが同じ事です.)

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
    
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll Q; cin >> Q;
    deque<pair<ll, ll>> dq;
    while (Q--) {
        int t; cin >> t;
        if (t == 1) {
            char c;
            int x; 
            cin >> c >> x;
            dq.emplace_back(c - 'a', x);
        }
        else {
            vector<ll> cnt(26);
            int r; cin >> r;
            while (!dq.empty() and r > 0) {
                if (dq.front().second >= r) {
                    cnt[dq.front().first] += r;
                    dq.front().second -= r;
                    r = 0;
                    if (dq.front().second == 0) dq.pop_front();
                }
                else {
                    cnt[dq.front().first] += dq.front().second;
                    r -= dq.front().second;
                    dq.pop_front();
                }
            }
            ll res = 0;
            for (int i = 0; i < 26; i++) res += cnt[i] * cnt[i];
            cout << res << "\n";
        }
    }
    return 0;
} 

H - 1-9 Grid

ここから一気に難易度が上がります。

S→1→2→…→9→G

という風にいけばいいわけですね。

ということで、各グリッドをグラフと見立てて、最短経路を求めましょうという問題になります。

全てのペアのからにマンハッタン距離の辺をはると、これは重みがある最短経路問題になったので、Dijkstra法で解くことができました。

ちょっとしたコツ？なんですが、(i, j)という座標はi * W + jとすると1次元にできるのでオススメです。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

vector<ll> dijkstra(ll start, vector<vector<pair<int, ll>>>& graph) {
    vector<ll> dist(graph.size(), INF);
    dist[start] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    vector<bool> used(dist.size(), false);
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        ll d, node;
        tie(d, node) = pq.top();
        pq.pop();
        if (used[node]) continue;
        used[node] = true;
        for (pair<ll, ll> element : graph[node]) {
            ll new_d, new_node;
            tie(new_node, new_d) = element;
            new_d += d;
            if (new_d < dist[new_node]) {
                dist[new_node] = new_d;
                pq.push(make_pair(dist[new_node], new_node));
            }
        }
    }
    return dist;
}

ll H, W;
int cnv(pair<int,int> p) {
    return p.first * W + p.second;
}

int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    scanf("%lld %lld", &H, &W);
    vector<string> vs(H); for (int i = 0; i < H; i++) cin >> vs[i];
    pair<int, int> st, gl;
    vector<vector<pair<int, int>>> v(9);
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (vs[i][j] == 'S') {
                st = { i,j };
            }
            else if (vs[i][j] == 'G') {
                gl = { i,j };
            }
            else {
                v[vs[i][j] - '1'].emplace_back(i, j);
            }
        }
    }
    vector<vector<pair<int, ll>>> g(H * W);
    
    for (int i = 0; i < 8; i++) {
        for (auto fr : v[i]) {
            for (auto to : v[i + 1]) {
                g[cnv(fr)].emplace_back(cnv(to), llabs(to.second - fr.second) + llabs(fr.first - to.first));
            }
        }
    }
    for (auto to : v[0]) {
        g[cnv(st)].emplace_back(cnv(to), llabs(to.second - st.second) + llabs(to.first - st.first));
    }
    for (auto fr : v[8]) {
        g[cnv(fr)].emplace_back(cnv(gl), llabs(gl.second - fr.second) + llabs(gl.first - fr.first));
    }
    auto d = dijkstra(cnv(st), g);
    if (d[cnv(gl)] == INF) d[cnv(gl)] = -1;
    cout << d[cnv(gl)] << "\n";
    return 0;
} 

I - トーナメント

人数が毎回半分ずつになっていくので愚直にシミュレーションしましょう。これは易しい？

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    ll n; scanf("%lld", &n);
    n = (1LL << n);
    vector<pair<ll, ll>> a(n); for (int i = 0; i < n; i++) scanf("%lld", &a[i].first), a[i].second = i;
    vector<ll> res(n);
    for (int vs = 1;; vs++) {
        vector<pair<ll, ll>> b;
        for (int i = 0; i < a.size(); i += 2) {
            if (a[i].first > a[i + 1].first) {
                b.emplace_back(a[i]);
                res[a[i + 1].second] = vs;
            }
            else {
                b.emplace_back(a[i + 1]);
                res[a[i].second] = vs;
            }
        }
        if (b.size() == 1) {
            res[b[0].second] = vs;
            break;
        }
        else {
            a = b;
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%lld\n", res[i]);
    }
    return 0;
}

J - 文字列解析

構文解析と呼ばれる問題?に入るのかな?。(ちょっと微妙に違うかな？)

解けなかった人はやることは分かるのにーという感じだと思います。

( + 処理した文字列 + )があれば、処理した文字列 + rev(処理した文字列)になるので、これは再帰で書くのが楽です。

慣れていないとこれの実装は難しいと思います。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

string dfs(string s) {
    //cout << s << endl;
    string res;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            int cnt = 1;
            string tmp;
            i++;
            for (; i < s.size(); i++) {
                if (s[i] == '(') cnt++;
                else if (s[i] == ')') {
                    cnt--;
                    if (cnt == 0) {
                        break;
                    }
                }
                tmp += s[i];
            }
            tmp = dfs(tmp);
            res += tmp;
            reverse(tmp.begin(), tmp.end());
            res += tmp;
        }
        else {
            res += s[i];
        }
    }
    return res;
}
int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    string s; cin >> s;
    cout << dfs(s) << "\n";
    return 0;
} 

K - 括弧

まず括弧列が成立する条件として'('の数 - ')'の数が最終的に0で途中で負になってはいけないというのがあります。

ここまで分かってしまえば、「原始的な」DPです。

dp[i][j]:= i文字目まで見た時の'(' - ')'がjのコストの最小値

遷移は素直にそのままです(分からなければ実装を見て見てね)

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int main()
{
    
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    

    ll n; cin >> n;
    string s; cin >> s;
    vector<ll> c(n); for (int i = 0; i < n; i++) cin >> c[i];
    vector<ll> d(n); for (int i = 0; i < n; i++) cin >> d[i];
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            chmin(dp[i + 1][j], dp[i][j] + d[i]);
            if (s[i] == '(') {
                if (j < n) chmin(dp[i + 1][j + 1], dp[i][j]);
                if (j > 0) chmin(dp[i + 1][j - 1], dp[i][j] + c[i]);
            }
            else {
                if (j < n) chmin(dp[i + 1][j + 1], dp[i][j] + c[i]);
                if (j > 0) chmin(dp[i + 1][j - 1], dp[i][j]);
            }
        }
    }
    cout << dp[n][0] << endl;
    return 0;
} 

L - 辞書順最小

先に言っておくと、おそらくこの解法は想定ではないので、あまり参考にしないでください…

辞書順最小ですから、前から貪欲です。以下0-indexedで

文字目をみてるときに、残り個あるときは、

を取ればいいわけです。最小値が複数ある場合は一番左のやつを取りましょう(明らかに最適です)

区間の最小値が要求されているので、自然なのはSegment Treeなどのデータ構造でしょうか

スライド最小値を用いてもできますね。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

template< typename Monoid >
struct SegmentTree {
    using F = function< Monoid(Monoid, Monoid) >;

    int sz;
    vector< Monoid > seg;

    const F f;
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid& M1) : f(f), M1(M1) {
        sz = 1;
        while (sz < n) sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid& x) {
        seg[k + sz] = x;
    }

    void build() {
        for (int k = sz - 1; k > 0; k--) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    void update(int k, const Monoid& x) {
        k += sz;
        seg[k] = x;
        while (k >>= 1) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    Monoid query(int a, int b) {
        Monoid L = M1, R = M1;
        if (a >= b) return M1;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) L = f(L, seg[a++]);
            if (b & 1) R = f(seg[--b], R);
        }
        return f(L, R);
    }
};

pair<ll, ll> f(pair<ll, ll> a, pair<ll, ll> b) {
    return min(a, b);
}
int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    ll N, K, D; scanf("%lld %lld %lld", &N, &K, &D);
    vector<ll> a(N); for (int i = 0; i < N; i++) scanf("%lld", &a[i]);
    SegmentTree<pair<ll, ll>> seg(N, f, { INF,INF });
    for (int i = 0; i < N; i++) {
        seg.set(i, { a[i],i });
    }
    seg.build();
    if (N - 1 - (K - 1) * D < 0) {
        puts("-1");
        return 0;
    }
    int now = 0;
    vector<ll> res; res.reserve(K);
    for (ll i = K - 1; i >= 0; i--) {
        ll ed = N - i * D;
        auto p = seg.query(now, ed);
        res.push_back(p.first);
        now = p.second + D;
    }
    for (int i = 0; i < res.size(); i++) {
        printf("%lld", res[i]);
        if (i + 1 == res.size()) puts("");
        else printf(" ");
    }
    return 0;
} 

M - 食堂

おそらくこのセットの最難ですね。

好みの料理を食べる個数を固定してあげましょう。そうすると、何回食堂を利用するかが分かります。

明らかにこれは単調性があるので二部探索です。

僕は実装の際std::lower_boundがend()を返してる場合を忘れてて、かなり時間を食いました(提出デバッグしてたらほとんど同じコードなのに、ACの数が違ったので未定義と気づけた)

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

vector<ll> g[100001];
vector<ll> cnt[100001];
int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    ll D, L, N; scanf("%lld %lld %lld", &D, &L, &N);
    vector<ll> C(D); for (int i = 0; i < D; i++) scanf("%lld", &C[i]), C[i]--;
    for (int i = 0; i < D; i++) {
        g[C[i]].push_back(i);
    }

    for (int i = 0; i < 100000; i++) {
        if(g[i].size() == 0) continue;
        cnt[i].resize(g[i].size() + 1);
        for (int j = 0; j + 1 < (int)g[i].size(); j++) {
            cnt[i][j + 1] = cnt[i][j] + max((g[i][j + 1] - g[i][j] - 1), 0LL) / L;
        }
        if (g[i].size() > 0) {
            ll len = D - 1 - g[i].back();
            len += g[i][0];
            cnt[i].back() = cnt[i][(int)g[i].size() - 1] + max((len), 0LL) / L;
        }
    }

    for (int i = 0; i < N; i++) {
        ll K, F, T; scanf("%lld %lld %lld", &K, &F, &T);
        K--;
        F--;
        if (g[K].size() == 0) {
            puts("0");
            continue;
        }
        ll left = 0;
        ll right = T + 1;

        while (right - left > 1) {
            ll mid = (left + right) >> 1;
            int idx = lower_bound(g[K].begin(), g[K].end(), F) - g[K].begin();
            ll tmp = mid;
            if (idx == g[K].size()) {
                tmp += (D - F + g[K][0] - 1) / L + 1;
                idx = 0;
            }
            else {
                tmp += max((g[K][idx] - F - 1), 0LL) / L;
                if (g[K][idx] != F) tmp++;
            }
            tmp += cnt[K].back() * ((mid - 1) / g[K].size());
            ll r = (mid - 1) % g[K].size();
            if (idx + r < cnt[K].size()) {
                tmp += cnt[K][idx + r] - cnt[K][idx];
            }
            else {
                tmp += cnt[K].back() - cnt[K][idx];
                r -= (ll)g[K].size() - idx;
                tmp += cnt[K][r];
            }
            if (tmp > T) right = mid;
            else left = mid;
        }
        printf("%lld\n", left);
    }
    return 0;
}

N - ビルの建設

まず、無駄に座標がでかいので座圧してしまいましょう。(個人的に座圧はソートや二部探索でやるのが好きで、std::mapは定数倍の観点からあまり好きではない)

もう少し制約が小さければ2次元imos法とかでもいけたのでしょうけど、これはさすがに無理です。

ということでクエリを先読みしてxが小さいほうから見ていきましょう。

ここで、領域もが小さい順に並べていきましょう。

あるクエリのx座標がある領域のに入ったら、その領域のにコストを加算します。

逆に今見てるx座標がから出たら、、その領域のにコストを加算します。

これは区間加算1点取得ができるデータ構造を用いるといいです。遅延伝播SegmentTreeなどを用いて実装することができます(もう少し弱いデータ構造でも大丈夫です)

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree {
    using F = function< Monoid(Monoid, Monoid) >;
    using G = function< Monoid(Monoid, OperatorMonoid) >;
    using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

    int sz, height;
    vector< Monoid > data;
    vector< OperatorMonoid > lazy;
    const F f;
    const G g;
    const H h;
    const Monoid M1;
    const OperatorMonoid OM0;


    LazySegmentTree(int n, const F f, const G g, const H h,
        const Monoid& M1, const OperatorMonoid OM0)
        : f(f), g(g), h(h), M1(M1), OM0(OM0) {
        sz = 1;
        height = 0;
        while (sz < n) sz <<= 1, height++;
        data.assign(2 * sz, M1);
        lazy.assign(2 * sz, OM0);
    }

    void set(int k, const Monoid& x) {
        data[k + sz] = x;
    }

    void build() {
        for (int k = sz - 1; k > 0; k--) {
            data[k] = f(data[2 * k + 0], data[2 * k + 1]);
        }
    }

    inline void propagate(int k) {
        if (lazy[k] != OM0) {
            lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
            lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
            data[k] = reflect(k);
            lazy[k] = OM0;
        }
    }

    inline Monoid reflect(int k) {
        return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
    }

    inline void recalc(int k) {
        while (k >>= 1) data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1));
    }

    inline void thrust(int k) {
        for (int i = height; i > 0; i--) propagate(k >> i);
    }

    void update(int a, int b, const OperatorMonoid& x) {
        if (a >= b) return;
        thrust(a += sz);
        thrust(b += sz - 1);
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lazy[l] = h(lazy[l], x), ++l;
            if (r & 1) --r, lazy[r] = h(lazy[r], x);
        }
        recalc(a);
        recalc(b);
    }

    Monoid query(int a, int b) {
        if (a >= b) return M1;
        thrust(a += sz);
        thrust(b += sz - 1);
        Monoid L = M1, R = M1;
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = f(L, reflect(l++));
            if (r & 1) R = f(reflect(--r), R);
        }
        return f(L, R);
    }

    Monoid operator[](const int& k) {
        return query(k, k + 1);
    }

};

struct Cost {
    ll x_min, x_max, y_min, y_max, cost;
    Cost(ll a, ll b, ll c, ll d, ll e) :x_min(a), x_max(b), y_min(c), y_max(d), cost(e) {}
    bool operator<(const Cost &c) const{
        return x_min < c.x_min;
    }

};

struct Query {
    ll x, y, id;
    Query(ll _x, ll _y, ll _id) :x(_x), y(_y), id(_id) {}
    bool operator<(const Query &q) const{
        return x < q.x;
    }

};
vector<ll> comp;

int get_idx(ll x) {
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
}

pair<ll, ll> f1(pair<ll, ll> a, pair<ll, ll> b) {
    return { a.first + b.first, a.second + b.second };
}

pair<ll, ll> f2(pair<ll, ll> a, ll b) {
    return { a.first + b * a.second, a.second };
}

ll f3(ll a, ll b) {
    return a + b;
}

struct T {
    ll x, l, r, c;
    T(ll _x, ll _l, ll _r, ll _c) :x(_x), l(_l), r(_r), c(_c) {}
    bool operator<(const T &t) const{
        return x < t.x;
    }
};
int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    ll N, Q; scanf("%lld %lld",&N, &Q);
    vector<Cost> vc; vc.reserve(N);

    for (int i = 0; i < N; i++) {
        ll x, y, d, c; scanf("%lld %lld %lld %lld", &x, &y, &d, &c);
        vc.emplace_back(x, x + d, y, y + d, c);
        comp.push_back(x);
        comp.push_back(x + d);
        comp.push_back(y);
        comp.push_back(y + d);
    }
    vector<Query> query; query.reserve(Q);
    for (int i = 0; i < Q; i++) {
        ll a, b; scanf("%lld %lld", &a, &b);
        query.emplace_back(a, b, i);
        comp.push_back(a);
        comp.push_back(b);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for (int i = 0; i < N; i++) {
        vc[i].x_min = get_idx(vc[i].x_min);
        vc[i].x_max = get_idx(vc[i].x_max);
        vc[i].y_min = get_idx(vc[i].y_min);
        vc[i].y_max = get_idx(vc[i].y_max);
    }
    for (int i = 0; i < Q; i++) {
        query[i].x = get_idx(query[i].x);
        query[i].y = get_idx(query[i].y);
    }
    sort(vc.begin(), vc.end());
    sort(query.begin(), query.end());
    LazySegmentTree<pair<ll, ll>, ll> lsg(comp.size() + 5, f1, f2, f3, { 0,0 }, 0);
    for (int i = 0; i < comp.size() + 5; i++) lsg.set(i, { 0,1 });
    lsg.build();
    multiset<Cost> ms1;
    multiset<T> ms2;
    
    for (int i = 0; i < vc.size(); i++) {
        ms1.emplace(vc[i]);
    }
    vector<ll> res(Q);
    for (int i = 0; i < Q; i++) {
        while (!ms1.empty() and query[i].x >= ms1.begin()->x_min) {
            ms2.emplace(ms1.begin()->x_max, ms1.begin()->y_min, ms1.begin()->y_max, ms1.begin()->cost);
            lsg.update(ms1.begin()->y_min, ms1.begin()->y_max + 1, ms1.begin()->cost);
            ms1.erase(ms1.begin());
        }
        
        while (!ms2.empty() and query[i].x > ms2.begin()->x) {
            lsg.update(ms2.begin()->l, ms2.begin()->r + 1, -(ms2.begin()->c));
            ms2.erase(ms2.begin());
        }
        
        res[query[i].id] = lsg.query(query[i].y, query[i].y + 1).first;
    }
    for (int i = 0; i < Q; i++) {
        cout << res[i] << "\n";
    }
    return 0;
} 

O - 可変全域木

まず、適当にこのグラフの最小全域木を取ってきましょう。

当然辺がこの最小全域木に含まれていたら、そのまま最小全域木の重みの和が答えです。

では逆に含まれていない時を考えましょう。

ここで辺を使う場合を考えてみましょう。

最小全域木にを結ぶと閉路ができます。

この閉路のどこを削除しても全域木になります。

ということで以外の最大の辺を削除をしたらいいことがわかります。

これは元の最小全域木のからにおけるpathのうち最大の重みを削除するということです。

木上のpathの最大値は親の顔よりみたHeavy-Light-Decompositionを用いて解くことができました。

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

struct HLD {
    vector<int> sz, in, out, head, par;
    vector<vector<int>> g;
    HLD() {}
    HLD(vector<vector<int>>& _g) : g(_g), sz(_g.size()), in(_g.size()), out(_g.size()), head(_g.size()), par(_g.size()) {}
    void dfs_sz(int cur, int pre) {
        sz[cur] = 1;
        for (int& next : g[cur]) {
            if (next == pre) continue;
            dfs_sz(next, cur);
            par[next] = cur;
            sz[cur] += sz[next];
            if (sz[next] > sz[g[cur][0]]) swap(next, g[cur][0]);
        }
    }

    void dfs_hld(int cur, int pre, int& idx) {
        in[cur] = idx++;
        for (int& next : g[cur]) {
            if (next == pre) continue;
            if (next == g[cur][0]) head[next] = head[cur];
            else head[next] = next;
            dfs_hld(next, cur, idx);
        }
        out[cur] = idx;
    }

    void build() {
        dfs_sz(0, -1);
        int idx = 0;
        dfs_hld(0, -1, idx);
    }

    void build(vector<vector<int>>& _g) {
        g = _g;
        sz.resize(g.size());
        in.resize(g.size());
        out.resize(g.size());
        head.resize(g.size());
        par.resize(g.size());

        dfs_sz(0, -1);
        int idx = 0;
        dfs_hld(0, -1, idx);
    }
    int lca(int u, int v) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }
};

class UnionFind {
public:
    vector<ll> Parent;
    UnionFind(ll N) {
        Parent = vector<ll>(N, -1);
    }
    ll root(ll A) {
        if (Parent[A] < 0) {
            return A;
        }
        return Parent[A] = root(Parent[A]);
    }

    ll size(ll A) {
        return -Parent[root(A)];
    }

    bool connect(ll A, ll B) {
        A = root(A);
        B = root(B);
        if (A == B) {
            return false;
        }
        if (size(A) < size(B)) {
            swap(A, B);
        }

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }

};

class Edge {
public:
    ll source, target, cost;
    Edge(ll source = 0, ll target = 0, ll cost = 0) :
        source(source), target(target), cost(cost) {}
    bool operator<(const Edge& e)const {
        return cost < e.cost;
    }
};

ll kuraskal(ll N, vector<Edge>& edges, vector<vector<int>> &g1, vector<tuple<ll,ll,ll>> &vp) {
    ll totalCost = 0;
    sort(edges.begin(), edges.end());
    UnionFind uni(N + 1);
    ll source, target;
    for (ll i = 0; i < edges.size(); i++) {
        Edge e = edges[i];
        if (uni.root(e.source) != uni.root(e.target)) {
            totalCost += e.cost;
            uni.connect(e.source, e.target);
            g1[e.source].push_back(e.target);
            g1[e.target].push_back(e.source);
            if (e.source > e.target) swap(e.source, e.target);
            vp.emplace_back(e.source, e.target, e.cost);
        }
    }
    return totalCost;
}

template< typename Monoid >
struct SegmentTree {
    using F = function< Monoid(Monoid, Monoid) >;

    int sz;
    vector< Monoid > seg;

    const F f;
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid& M1) : f(f), M1(M1) {
        sz = 1;
        while (sz < n) sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid& x) {
        seg[k + sz] = x;
    }

    void build() {
        for (int k = sz - 1; k > 0; k--) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    void update(int k, const Monoid& x) {
        k += sz;
        seg[k] = x;
        while (k >>= 1) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    Monoid query(int a, int b) {
        Monoid L = M1, R = M1;
        if (a >= b) return M1;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) L = f(L, seg[a++]);
            if (b & 1) R = f(seg[--b], R);
        }
        return f(L, R);
    }
};

ll f(ll a, ll b) {
    return max(a, b);
}
int main()
{
    /*
   cin.tie(nullptr);
   ios::sync_with_stdio(false);
   */

    ll n, m; scanf("%lld %lld", &n, &m);
    vector<vector<int>> g1(n);
    vector<Edge> edges;
    vector<tuple<ll, ll, ll>> vp;
    vector<tuple<ll,ll,ll>> query;
    for (int i = 0; i < m; i++) {
        ll a, b, c; scanf("%lld %lld %lld", &a, &b, &c);
        a--; b--;
        if (a > b) swap(a, b);
        edges.emplace_back(a, b, c);
        query.emplace_back(a, b, c);
    }
    ll mst = kuraskal(n, edges, g1, vp);
    HLD hld(g1);
    hld.build();
    SegmentTree<ll> seg(n, f, 0);
    for (int i = 0; i < vp.size(); i++) {
        ll u, v, c; tie(u, v, c) = vp[i];
        if (hld.in[u] > hld.in[v]) swap(u, v);
        seg.set(hld.in[v], c);
    }
    seg.build();
    sort(vp.begin(), vp.end());
    for (int i = 0; i < m; i++) {
        if (binary_search(vp.begin(), vp.end(), query[i])) {
            printf("%lld\n", mst);
        }
        else {
            ll u, v, c; tie(u, v, c) = query[i];
            if (hld.in[u] > hld.in[v]) swap(u, v);
            int t[2] = { u,v };
            int lc = hld.lca(u, v);
            ll tmp = 0;
            for (int j = 0; j < 2; j++) {
                for (;; t[j] = hld.par[hld.head[t[j]]]) {
                    if (hld.head[lc] == hld.head[t[j]]) {
                        chmax(tmp, seg.query(hld.in[lc] + 1, hld.in[t[j]] + 1));
                        break;
                    }
                    else {
                        chmax(tmp, seg.query(hld.in[hld.head[t[j]]], hld.in[t[j]] + 1));
                    }
                }
            }
            printf("%lld\n", mst + c - tmp);
        }
    }
    return 0;
} 

まとめ

全完はもちろんエキスパートも水色だと取るのはかなり大変なセットなので、エキスパート取れたら青色って言ってもいいセットに確かに見える。

今回は前回より難しく感じたんですが、いろいろ周りの意見を聞きたいですね。