JOI'22 春合宿参加記

春合宿はまじで楽しいので全人類行きましょう。

結果

	A	B	C	日計	計	当日順位	順位
Day1	66	10	0	76	76	17	17
Day2	20	15	64	99	175	26	21
Day3	5	53	6	64	239	17	22
Day4	7	13	14	34	273	22	22

感想

さすがにやっぱりレベルが違って、全く勝負にならなかった。が、全体としてかなり楽しくて超満足なのでぜひ皆さん春合宿に行きましょう！

ほとんど解いたことのない（おい）春合宿タイプの JOI の問題は、5 時間 3 問想定なだけあって、一つの問題に対してかなり長い時間をかけてひとステップずつ考察していくので、かなり楽しい。また今度たくさん精進したいな。

また、初めての競プロ系オンサイトで割と交流できてよかった。みつばちおもろい。

Day1

B と C が全くわからなかったのでほとんど A に使った。

A: jail

まず小課題 3 の計算量が明らかに $O(QNM!)$ くらいなので、順列全探索でおそらく解けるということを考えると、ある人に対して操作を行うときは全部やってしまえばいいことがわかる。

各順列において、操作が可能かどうかを愚直に調べると、小課題 2, 3 が通る。

次に小課題 1 を見ると、列においてこの問題を解けば良いので、いい感じにやる。

ここらへんで、列において人 $i$, $j$ が干渉する条件を考えていたので、木においても同じことを考えると、$P_i$ を人 $i$ の通るパス $S_i$ $T_i$ とすると、

$P_i$ 内に $S_j$, $T_j$ がともに含まれているとき、No
$P_i$ 内に $S_j$ が含まれているときと、$P_j$ 内に $T_j$ が含まれているとき、j を i より先に動かす
上記の二つを満たさないとき、制約なし

という条件が得られるので、いい感じに処理の順番の制約を作ったらそれをトポソして判定。小課題 4 では $O(QM^{2}N)$, 小課題 5 では $O(Q(NMlogN+M^{2}logN))$ くらいで解く。

小課題 6 では $P_i$ をすべて陽に持てるが、$O(パスの長さ)$ でこれを求めなければならないので、lca を書いてちょちょっとやると解ける。実装間に合わず。

小課題を一つずつ見て行って、要求されていることを一つずつ考察していくと進んでいったので楽しかった。

f:id:RheoTommy:20220321083619p:plain

小課題 1

#include <algorithm>
#include <bits/stdc++.h>
#include <numeric>
#include <shared_mutex>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int m;
    cin >> m;
    vector<int> s(m);
    vector<int> t(m);
    for (int j = 0; j < m; j++)
        cin >> s[j] >> t[j], s[j]--, t[j]--;

    bool flag1 = true;
    {
        vector<int> si(n, -1);
        vector<int> ti(n - 1);
        for (int j = 0; j < m; j++)
            si[s[j]] = j, ti[t[j]] = j;

        set<int> t_st;
        for (int j = 0; j < m; j++)
            t_st.emplace(t[j]);

        for (int i = 0; i < n; i++) {
            if (si[i] == -1)
                continue;

            int j = si[i];
            if (s[j] > t[j])
                continue;

            flag1 &= *t_st.lower_bound(i) == t[j];
            t_st.erase(t[j]);
        }
    }

    for (int j = 0; j < m; j++)
        swap(s[j], t[j]);

    bool flag2 = true;
    {
        vector<int> si(n, -1);
        vector<int> ti(n - 1);
        for (int j = 0; j < m; j++)
            si[s[j]] = j, ti[t[j]] = j;

        set<int> t_st;
        for (int j = 0; j < m; j++)
            t_st.emplace(t[j]);

        for (int i = 0; i < n; i++) {
            if (si[i] == -1)
                continue;

            int j = si[i];
            if (s[j] > t[j])
                continue;

            flag2 &= *t_st.lower_bound(i) == t[j];
            t_st.erase(t[j]);
        }
    }

    cout << (flag1 && flag2 ? "Yes" : "No") << '\n';
}

int main() {
    int q;
    cin >> q;
    while (q--)
        solve();
}

小課題 2, 3

#include <algorithm>
#include <bits/stdc++.h>
#include <numeric>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int m;
    cin >> m;
    vector<int> s(m);
    vector<int> t(m);
    for (int j = 0; j < m; j++)
        cin >> s[j] >> t[j], s[j]--, t[j]--;

    vector<bool> staying(n, false);
    for (int j = 0; j < m; j++)
        staying[s[j]] = true;

    vector<int> p(m);
    iota(p.begin(), p.end(), 0);

    auto check_dfs = [&](auto &&dfs, int now, int par, int t) -> bool {
        if (now == t)
            return true;

        bool flag = false;
        for (auto next : graph[now]) {
            if (next == par)
                continue;

            if (!staying[next])
                flag |= dfs(dfs, next, now, t);
        }

        return flag;
    };

    bool ans = false;

    do {
        staying = vector<bool>(n, false);
        for (int j = 0; j < m; j++)
            staying[s[j]] = true;

        bool flag = true;
        for (int k = 0; k < m; k++) {
            flag &= check_dfs(check_dfs, s[p[k]], -1, t[p[k]]);
            staying[s[p[k]]] = false;
            staying[t[p[k]]] = true;
        }
        ans |= flag;
    } while (next_permutation(p.begin(), p.end()));

    cout << (ans ? "Yes" : "No") << '\n';
}

int main() {
    int q;
    cin >> q;
    while (q--)
        solve();
}

小課題 4

#include <algorithm>
#include <bits/stdc++.h>
#include <numeric>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int m;
    cin >> m;
    vector<int> s(m);
    vector<int> t(m);
    for (int j = 0; j < m; j++)
        cin >> s[j] >> t[j], s[j]--, t[j]--;

    auto get_path_set = [&](int s, int t) -> set<int> {
        vector<int> depth(n, -1);
        depth[s] = 0;
        auto dfs = [&](auto &&dfs, int now, int par) -> void {
            for (auto next : graph[now]) {
                if (next == par)
                    continue;
                if (depth[next] != -1)
                    continue;

                depth[next] = depth[now] + 1;
                dfs(dfs, next, now);
            }
        };
        dfs(dfs, s, -1);

        set<int> st;
        st.emplace(s);

        int now = t;
        while (now != s) {
            st.emplace(now);
            for (auto next : graph[now]) {
                if (depth[next] + 1 == depth[now]) {
                    now = next;
                    break;
                }
            }
        }
        return st;
    };

    vector<vector<int>> topo_graph(m);
    vector<int> degree(m);

    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            auto pi = get_path_set(s[i], t[i]);
            auto pj = get_path_set(s[j], t[j]);

            // cout << "HERE i " << pi.size() << endl;
            // cout << "HERE j " << pj.size() << endl;
            // for (auto p : pi)
            //     cout << p << ' ';
            // cout << endl;
            // for (auto p : pj)
            //     cout << p << ' ';
            // cout << endl;

            bool ng_flag = true;
            for (auto t : pj)
                ng_flag &= pi.count(t);
            if (ng_flag) {
                cout << "No" << endl;
                return;
            }

            if (pj.count(s[i]) || pi.count(t[j]))
                topo_graph[i].push_back(j), degree[j]++;
            if (pi.count(s[j]) || pj.count(t[i]))
                topo_graph[j].push_back(i), degree[i]++;
        }
    }

    vector<int> sorted;
    queue<int> que;
    for (int i = 0; i < m; i++)
        if (degree[i] == 0)
            que.emplace(i);

    while (!que.empty()) {
        int now = que.front();
        sorted.emplace_back(now);
        que.pop();
        for (auto next : topo_graph[now]) {
            degree[next]--;
            if (degree[next] == 0)
                que.emplace(next);
        }
    }

    cout << (sorted.size() == m ? "Yes" : "No") << endl;
}

int main() {
    int q;
    cin >> q;
    while (q--)
        solve();
}

小課題 5

#include <algorithm>
#include <bits/stdc++.h>
#include <numeric>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    int m;
    cin >> m;
    vector<int> s(m);
    vector<int> t(m);
    for (int j = 0; j < m; j++)
        cin >> s[j] >> t[j], s[j]--, t[j]--;

    auto get_path = [&](int s, int t) -> vector<int> {
        vector<int> depth(n, -100);
        depth[s] = 0;
        auto dfs = [&](auto &&dfs, int now, int par) -> void {
            if (now == t)
                return;

            for (auto next : graph[now]) {
                if (next == par)
                    continue;
                if (depth[next] != -100)
                    continue;

                depth[next] = depth[now] + 1;
                dfs(dfs, next, now);
            }
        };
        dfs(dfs, s, -1);

        vector<int> v;
        v.emplace_back(s);

        int now = t;
        while (now != s) {
            v.emplace_back(now);
            for (auto next : graph[now]) {
                if (depth[next] + 1 == depth[now]) {
                    now = next;
                    break;
                }
            }
        }

        sort(v.begin(), v.end());
        return v;
    };

    vector<vector<int>> paths(m);
    for (int i = 0; i < m; i++)
        paths[i] = get_path(s[i], t[i]);

    auto contains = [&](int i, int x) -> bool {
        return lower_bound(paths[i].begin(), paths[i].end(), x) !=
                   paths[i].end() &&
               *lower_bound(paths[i].begin(), paths[i].end(), x) == x;
    };

    vector<vector<int>> topo_graph(m);
    vector<int> degree(m);

    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            if ((contains(i, s[j]) && contains(i, t[j])) ||
                (contains(j, s[i]) && contains(j, t[i]))) {
                cout << "No" << '\n';
                return;
            }

            if (contains(j, s[i]) || contains(i, t[j]))
                topo_graph[i].push_back(j), degree[j]++;
            if (contains(i, s[j]) || contains(j, t[i]))
                topo_graph[j].push_back(i), degree[i]++;
        }
    }

    vector<int> sorted;
    queue<int> que;
    for (int i = 0; i < m; i++)
        if (degree[i] == 0)
            que.emplace(i);

    while (!que.empty()) {
        int now = que.front();
        sorted.emplace_back(now);
        que.pop();
        for (auto next : topo_graph[now]) {
            degree[next]--;
            if (degree[next] == 0)
                que.emplace(next);
        }
    }

    cout << (sorted.size() == m ? "Yes" : "No") << '\n';
}

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

    int q;
    cin >> q;
    while (q--)
        solve();
}

小課題 6

#include <algorithm>
#include <bits/stdc++.h>
#include <numeric>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    int m;
    cin >> m;
    vector<int> s(m);
    vector<int> t(m);
    for (int j = 0; j < m; j++)
        cin >> s[j] >> t[j], s[j]--, t[j]--;

    vector<int> depth(n, -1);
    depth[0] = 0;
    vector<int> ord(n);
    vector<int> num_to_ord(n);
    vector<vector<int>> doubling(18, vector<int>(n));
    vector<int> sz(n);
    doubling[0][0] = 0;
    int k = 0;
    auto dfs = [&](auto &&dfs, int now, int par) -> void {
        sz[now] = 1;
        ord[k] = now;
        num_to_ord[now] = k++;
        for (auto next : graph[now]) {
            if (next == par)
                continue;
            depth[next] = depth[now] + 1;
            doubling[0][next] = now;
            dfs(dfs, next, now);
            sz[now] += sz[next];
        }
    };
    dfs(dfs, 0, -1);

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

    auto lca = [&](int x, int y) {
        if (depth[x] > depth[y])
            swap(x, y);

        int diff = depth[y] - depth[x];
        for (int k = 17; k >= 0; k--) {
            if (diff >> k & 1)
                y = doubling[k][y];
        }

        if (x == y)
            return x;

        for (int k = 17; k >= 0; k--) {
            if (doubling[k][x] != doubling[k][y])
                x = doubling[k][x], y = doubling[k][y];
        }

        return doubling[0][x];
    };

    auto get_path = [&](int x, int y) {
        int l = lca(x, y);
        set<int> st;
        int lo = num_to_ord[l];
        int xo = num_to_ord[x];
        int yo = num_to_ord[y];

        while (x != l) {
            st.insert(x);
            x = doubling[0][x];
        }
        while (y != l) {
            st.insert(y);
            y = doubling[0][y];
        }
        st.insert(l);

        vector<int> v;
        for (auto si : st)
            v.push_back(si);
        sort(v.begin(), v.end());
        return v;
    };

    vector<vector<int>> paths(m);
    for (int i = 0; i < m; i++)
        paths[i] = get_path(s[i], t[i]);

    auto contains = [&](int i, int x) -> bool {
        return lower_bound(paths[i].begin(), paths[i].end(), x) !=
                   paths[i].end() &&
               *lower_bound(paths[i].begin(), paths[i].end(), x) == x;
    };

    vector<vector<int>> includes_x(n);
    for (int i = 0; i < m; i++) {
        for (auto p : paths[i])
            includes_x[p].emplace_back(i);
    }

    vector<set<int>> topo_graph(m);
    vector<int> degree(m);

    for (int i = 0; i < m; i++) {
        set<int> set_s;
        set<int> set_t;
        for (auto j : includes_x[s[i]])
            set_s.emplace(j);
        for (auto j : includes_x[t[i]])
            set_t.emplace(j);

        for (auto j : set_s) {
            if (i == j)
                continue;
            if (set_t.count(j)) {
                cout << "No" << '\n';
                return;
            }
            if (!topo_graph[i].count(j)) {
                topo_graph[i].insert(j);
                degree[j]++;
            }
        }
        for (auto j : set_t) {
            if (i == j)
                continue;
            if (!topo_graph[j].count(i)) {
                topo_graph[j].insert(i);
                degree[i]++;
            }
        }
    }

    vector<int> sorted;
    queue<int> que;
    for (int i = 0; i < m; i++)
        if (degree[i] == 0)
            que.emplace(i);

    while (!que.empty()) {
        int now = que.front();
        sorted.emplace_back(now);
        que.pop();
        for (auto next : topo_graph[now]) {
            degree[next]--;
            if (degree[next] == 0)
                que.emplace(next);
        }
    }

    cout << (sorted.size() == m ? "Yes" : "No") << '\n';
}

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

    int q;
    cin >> q;
    while (q--)
        solve();
}

B: kyoto

小課題 1 が自明なので取る。

小課題 2 がちまちま考えても一生わからず。 $A_i \leq s$, $B_j \leq t$ の時のなんか、みたいな方針も考えたけどうまくいかず。

f:id:RheoTommy:20220321083815p:plain

小課題 1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll linf = 1001001001001001001ll;

template <typename T> bool chmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    int h, w;
    cin >> h >> w;
    vector<ll> a(h);
    vector<ll> b(w);
    for (int i = 0; i < h; i++)
        cin >> a[i];
    for (int j = 0; j < w; j++)
        cin >> b[j];

    vector<vector<ll>> dp(h, vector<ll>(w, linf));

    dp[0][0] = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (i + 1 < h) {
                chmin(dp[i + 1][j], dp[i][j] + b[j]);
            }
            if (j + 1 < w) {
                chmin(dp[i][j + 1], dp[i][j] + a[i]);
            }
        }
    }

    cout << dp[h - 1][w - 1] << '\n';
}

C: misspelling

$S_i \leq S_j$ を同値変形できませんでした！！！！！隣接する文字の大小関係だけに持ち込んだら確かにある程度行けそうだけど簡単ではないだろ。

Day2

小課題をちまちまやりすぎて時間が足りなくなった。考察は小課題をちゃんと一つ一つ見て行ってもいいけど、実装はある程度まとめてやった方がよさそう（自明取らずに中途半端にバグらせて全部落とすのが怖くてついこまめに実装してしまう）

A: copypaste3

小課題 1 は普通に性質を考えて場合分け。小課題 2 は $X$, $Y$ が文字列の長さで表せるので、頂点数 $O(N^{2})$ ダイクストラをする。

小課題 3 で、$X$, $Y$ がともに $S$ の部分文字列にしかならないことに気づいたので、状態量 $O(N^{4})$, 遷移 $O(N^{2})$ のダイクストラで通す。

priority_queue のキーに tuple じゃなくて自作構造体を使おうとしたら、Ord の実装の仕方がわからなかったり、普通にバグらせたりしてここまでで 70 分かかった。

そのあとも当然考察をして、S を作る際に

$X$ が空な状態から、A か C のみを用いて適当な文字列を作る
すべて切り取って $X$ を空にし、$Y$ を更新する

のステップを繰り返すことは分かったので、いい感じの区間 DP を考えるといいなーというところまでわかる。

ここで、適当な文字列 $S_i$ を作るためのコストを $S_i$ に含まれる任意の部分文字列を作るコストが既知としてメモ化再帰する方針を立ててしまい、$Y$ の文字列と $S$ の文字列の組が状態になるような方針しか生えなくなってしまった。

すでに S を作る際の操作手順を考えていたので、

最初, $X=空文字列$, $Y=S_y$, 完成

というプロセスから素直に $X=空文字列$, $Y=S_y$ を一つの状態とする DP が思いついてもよかったと今は感じているけど、できなかった。

z_algo もロリハもかけないので DP 高速化パートで困るのはわかっていたけど、一時間くらいは考察していたので、せめて $N \leq 200$ は取りたかった。

f:id:RheoTommy:20220321192848p:plain

小課題 1

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;

int main() {
    int n;
    string s;
    ll a, b, c;
    cin >> n >> s >> a >> b >> c;

    assert(n == 3);

    if (s[0] == s[1] && s[1] == s[2]) {
        cout << min(3 * a, a + b + c * 3) << endl;
    } else if (s[0] == s[1] || s[0] == s[2] || s[1] == s[2]) {
        cout << min(a * 3, a + b + a + c * 2) << endl;
    } else {
        cout << a * 3 << endl;
    }
}

小課題 2

#include <bits/stdc++.h>
#include <cassert>
#include <queue>
#include <tuple>

using namespace std;
using ll = long long;

const ll linf = 1001001001001001001ll;

template <typename T> bool chmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    int n;
    string s;
    ll a, b, c;
    cin >> n >> s >> a >> b >> c;

    for (int i = 0; i < n; i++) assert(s[i] == 'a');

    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, linf));
    dp[0][0] = 0;
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>>
        pri;
    pri.emplace(0, 0, 0);

    while (!pri.empty()) {
        ll cost;
        int x, y;
        tie(cost, x, y) = pri.top();
        pri.pop();

        if (x + 1 <= n && chmin(dp[x + 1][y], cost + a))
            pri.emplace(cost + a, x + 1, y);

        if (chmin(dp[0][x], cost + b)) pri.emplace(cost + b, 0, x);

        if (x + y <= n && chmin(dp[x + y][y], cost + c))
            pri.emplace(cost + c, x + y, y);
    }

    ll ans = linf;

    for (int y = 0; y <= n; y++) chmin(ans, dp[n][y]);

    cout << ans << endl;
}

小課題 3

#include <bits/stdc++.h>
#include <cassert>
#include <queue>
#include <tuple>

using namespace std;
using ll = long long;

const ll linf = 1001001001001001001ll;

template <typename T> bool chmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    int n;
    string s;
    ll a, b, c;
    cin >> n >> s >> a >> b >> c;

    assert(n <= 30);

    map<pair<int, int>, string> mp;
    vector<string> subs;
    for (int l = 0; l < n; l++) {
        for (int r = l + 1; r <= n; r++) {
            mp[{l, r}] = s.substr(l, r - l);
        }
    }
    map<string, vector<pair<int, int>>> st;
    for (auto [k, v] : mp) st[v].emplace_back(k);

    vector<vector<vector<vector<ll>>>> dp(
        n + 1, vector<vector<vector<ll>>>(
                   n + 1, vector<vector<ll>>(n + 1, vector<ll>(n + 1, linf))));
    priority_queue<tuple<ll, int, int, int, int>,
                   vector<tuple<ll, int, int, int, int>>, greater<>>
        pri;

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
            dp[x][x][y][y] = 0;
            pri.emplace(0, x, x, y, y);
        }
    }

    while (!pri.empty()) {
        ll cost;
        int lx, rx, ly, ry;
        tie(cost, lx, rx, ly, ry) = pri.top();
        pri.pop();

        for (auto p : st[mp[{lx, rx + 1}]]) {
            auto [l, r] = p;
            if (chmin(dp[l][r][ly][ry], cost + a))
                pri.emplace(cost + a, l, r, ly, ry);
        }

        if (chmin(dp[0][0][lx][rx], cost + b))
            pri.emplace(cost + b, 0, 0, lx, rx);

        for (auto p : st[mp[{lx, rx}] + mp[{ly, ry}]]) {
            auto [l, r] = p;
            if (chmin(dp[l][r][ly][ry], cost + c))
                pri.emplace(cost + c, l, r, ly, ry);
        }
    }

    ll ans = linf;

    for (int ly = 0; ly < n; ly++) {
        for (int ry = 0; ry <= n; ry++) {
            chmin(ans, dp[0][n][ly][ry]);
        }
    }

    cout << ans << endl;
}

B: flights

基本的には Communication Task なので後に回していて、C が少し行き詰った時に自明だけ取りに来た。

20 bit で $X$ と $Y$ の上位 8 bit だけ送り、$Y$ の候補 $2^{8}$ すべてを送るので、$14 \times 2^{8} = 3584$ で 15 点。

バグらせて 50 分使った。

f:id:RheoTommy:20220321193715p:plain

小課題 1

#include "Ali.h"
#include <bits/stdc++.h>
#include <string>

using namespace std;

namespace {
vector<vector<int>> graph;
int n;

string num_to_bits(int x) {
    string s;
    for (int i = 0; i < 14; i++) {
        s.push_back(((x >> (13 - i)) & 1) ? '1' : '0');
    }
    return s;
}

int bits_to_num(string s) {
    int x = 0;
    for (int i = 0; i < s.size(); i++) {
        x *= 2;
        x += s[i] == '1';
    }
    return x;
}
} // namespace

void Init(int N, std::vector<int> U, std::vector<int> V) {
    for (int i = 0; i < N; i++) SetID(i, i);
    graph = vector<vector<int>>(N);
    for (int i = 0; i < N - 1; i++) {
        graph[U[i]].emplace_back(V[i]);
        graph[V[i]].emplace_back(U[i]);
    }
    n = N;
}

std::string SendA(std::string S) {
    int x = bits_to_num(S.substr(0, 14));
    int y = bits_to_num(S.substr(14, 6));
    y <<= 8;

    vector<int> depth(10000, -1);
    depth[x] = 0;

    auto dfs = [&](auto &&dfs, int now, int par) -> void {
        for (auto next : graph[now]) {
            if (next == par) continue;
            depth[next] = depth[now] + 1;
            dfs(dfs, next, now);
        }
    };

    dfs(dfs, x, -1);

    vector<int> y_list;
    for (int k = 0; k < (1 << 8); k++) y_list.emplace_back(y + k);
    map<int, int> mp;
    for (auto yi : y_list) mp[yi] = depth[yi];

    string res;
    for (auto [k, v] : mp) {
        res += num_to_bits(v);
    }
    return res;
}

#include "Benjamin.h"
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;

namespace {
int y;
string num_to_bits(int x) {
    string s;
    for (int i = 0; i < 14; i++) {
        s.push_back(((x >> (13 - i)) & 1) ? '1' : '0');
    }
    return s;
}

int bits_to_num(string s) {
    int x = 0;
    for (int i = 0; i < 14; i++) {
        x *= 2;
        x += s[i] == '1';
    }
    return x;
}

} // namespace

std::string SendB(int N, int X, int Y) {
    y = Y;
    string x = num_to_bits(X);
    string yi = num_to_bits(Y);
    return x + yi.substr(0, 6);
}

int Answer(std::string T) {
    int len = T.size() / 14;
    vector<int> y_depth;
    for (int l = 0; l < len; l++) {
        y_depth.emplace_back(bits_to_num(T.substr(l * 14, 14)));
    }
    int yz = y & ((1 << 8) - 1);
    return y_depth[yz];
}

C: team

小課題を全部愚直に考察実装していたら時間を食いつぶしてしまった。

小課題 1 で全探索。小課題 2 では、一人固定して、ソートを使って残り二人の組み合わせを $O(NlogN)$ で舐めて $O(N^{2}logN)$ で通した。

小課題 3 は $(x, y, z)$ の組み合わせ $5^{3}$ すべてに対して $O(N)$ で判定。小課題 4 は $(x, y, z)$ の組み合わせが $20^{3}$ で $N$ より小さいので、$N=20^{3}$ として小課題 2 の解法を使う。

小課題 5 は $300^{3}$ を考えたくなったので、$(x, y, z)$ それぞれの組に対して、

$X_i = x$, $Y_i < y$, $Z_i < z$
$Y_i = y$, $X_i < x$, $Z_i < z$
$Z_i = z$, $X_i < x$, $Y_i < Y$

を満たすモノが存在するかどうかを高速に求めたくなり、$X_i = x$, $Y_i < y$, $Z_i < z$ を $X_i$ ごとに $Y$, $Z$ で二次元累積和を持つことで $O(1)$ にした。

小課題 6 は $4000N$ が間に合いそうなので、$X$ を固定して各 $O(N)$ で求めればよさそう。

$X=X_i$ のとき、$X_j < X$ を満たすもののうち大抵 $Y$ が最大のものと $Z$ が最大になるものが組になる（最大値同士の $i$ でない限り）ので、$Y$ と $Z$ も同じように固定する求めることで最大値同士のペアを無視できて、$X_i=X$ で $max Y > Y_i$ かつ $max X > Z_i$ な $i$ があるかをデータ構造で高速に判定したくなる。

$4000N$ が間に合うなら $X$ を愚直に全部チェックすればいいはず。実装間に合わず。

満点解法も、これを基準にすると二次元セグ木があればできそうであることは分かったが、実装時間もなかったので不可能だった。

想定満点解法は、部分点をまじめに考えない方が出てくると思う。

f:id:RheoTommy:20220321195729p:plain

小課題 1, 2

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
const int inf = 1001001001;

template <typename T> bool chmax(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;

    assert(n <= 4000);

    vector<int> x(n);
    vector<int> y(n);
    vector<int> z(n);

    vector<tuple<int, int, int>> t;

    for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i];
    for (int i = 0; i < n; i++) t.emplace_back(x[i], y[i], z[i]);

    int ans = -inf;

    for (int i = 0; i < n; i++) {
        int xi = x[i];
        int yi = y[i];
        int zi = z[i];
        vector<pair<int, int>> yz;

        for (int j = 0; j < n; j++) {
            if (x[j] < xi && (y[j] > yi || z[j] > zi))
                yz.emplace_back(y[j], z[j]);
        }

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

        int m = yz.size();

        if (m < 2) continue;

        vector<int> mx(m + 1, -inf);
        vector<int> yy(m);
        for (int j = 0; j < m; j++) mx[j + 1] = max(mx[j], yz[j].second);
        for (int j = 0; j < m; j++) yy[j] = yz[j].first;

        for (int j = 0; j < m; j++) {
            int k = lower_bound(yy.begin(), yy.end(), yy[j]) - yy.begin();

            if (yy[j] > yi && mx[k] > zi && mx[k] > yz[j].second)
                chmax(ans, xi + yy[j] + mx[k]);
            // cout << xi << ' ' << yy[j] << ' ' << mx[k] << endl;
        }
    }

    if (ans < 0) ans = -1;
    cout << ans << endl;
}

小課題 3

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>

using namespace std;
const int inf = 1001001001;

template <typename T> bool chmax(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

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

    int n;
    cin >> n;

    vector<int> x(n);
    vector<int> y(n);
    vector<int> z(n);

    vector<tuple<int, int, int>> t;

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> z[i];
        assert(x[i] <= 20);
        assert(y[i] <= 20);
        assert(z[i] <= 20);
    }
    for (int i = 0; i < n; i++) t.emplace_back(x[i], y[i], z[i]);

    int ans = -inf;

    for (int xt = 20; xt >= 1; xt--) {
        for (int yt = 20; yt >= 1; yt--) {
            for (int zt = 20; zt >= 1; zt--) {
                if (xt + yt + zt <= ans) continue;

                bool x_flag = false;
                bool y_flag = false;
                bool z_flag = false;

                for (int i = 0; i < n; i++) {
                    x_flag |= x[i] == xt && y[i] < yt && z[i] < zt;
                    y_flag |= y[i] == yt && x[i] < xt && z[i] < zt;
                    z_flag |= z[i] == zt && x[i] < xt && y[i] < yt;
                }

                if (x_flag && y_flag && z_flag) chmax(ans, xt + yt + zt);
            }
        }
    }

    if (ans < 0) ans = -1;
    cout << ans << endl;
}

小課題 4

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#include <tuple>

using namespace std;
const int inf = 1001001001;

template <typename T> bool chmax(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;

    set<tuple<int, int, int>> st;
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        st.emplace(x, y, z);
    }

    n = st.size();

    vector<int> x;
    vector<int> y;
    vector<int> z;

    vector<tuple<int, int, int>> t;

    for (auto tup : st) {
        int xi, yi, zi;
        tie(xi, yi, zi) = tup;
        x.emplace_back(xi);
        y.emplace_back(yi);
        z.emplace_back(zi);
    }
    for (int i = 0; i < n; i++) t.emplace_back(x[i], y[i], z[i]);

    int ans = -inf;

    for (int i = 0; i < n; i++) {
        int xi = x[i];
        int yi = y[i];
        int zi = z[i];
        vector<pair<int, int>> yz;

        for (int j = 0; j < n; j++) {
            if (x[j] < xi && (y[j] > yi || z[j] > zi))
                yz.emplace_back(y[j], z[j]);
        }

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

        int m = yz.size();

        if (m < 2) continue;

        vector<int> mx(m + 1, -inf);
        vector<int> yy(m);
        for (int j = 0; j < m; j++) mx[j + 1] = max(mx[j], yz[j].second);
        for (int j = 0; j < m; j++) yy[j] = yz[j].first;

        for (int j = 0; j < m; j++) {
            int k = lower_bound(yy.begin(), yy.end(), yy[j]) - yy.begin();

            if (yy[j] > yi && mx[k] > zi && mx[k] > yz[j].second)
                chmax(ans, xi + yy[j] + mx[k]);
            // cout << xi << ' ' << yy[j] << ' ' << mx[k] << endl;
        }
    }

    if (ans < 0) ans = -1;
    cout << ans << endl;
}

小課題 5

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#include <tuple>

using namespace std;
const int inf = 1001001001;

template <typename T> bool chmax(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;

    vector<vector<vector<bool>>> yz(
        301, vector<vector<bool>>(302, vector<bool>(302, 0)));
    vector<vector<vector<bool>>> xz(
        301, vector<vector<bool>>(302, vector<bool>(302, 0)));
    vector<vector<vector<bool>>> xy(
        301, vector<vector<bool>>(302, vector<bool>(302, 0)));

    vector<int> xn(n);
    vector<int> yn(n);
    vector<int> zn(n);

    for (int i = 0; i < n; i++) {
        cin >> xn[i] >> yn[i] >> zn[i];
        assert(xn[i] <= 300 && yn[i] <= 300 && zn[i] <= 300);
        yz[xn[i]][yn[i]][zn[i]] = true;
        xz[yn[i]][xn[i]][zn[i]] = true;
        xy[zn[i]][xn[i]][yn[i]] = true;
    }

    for (int x = 1; x <= 300; x++) {
        // yz[x][0][0] = true;
        for (int y = 0; y <= 300; y++) {
            for (int z = 0; z <= 300; z++) {
                yz[x][y][z + 1] = yz[x][y][z + 1] || yz[x][y][z];
            }
        }

        for (int z = 0; z <= 300; z++) {
            for (int y = 0; y <= 300; y++) {
                yz[x][y + 1][z] = yz[x][y + 1][z] || yz[x][y][z];
            }
        }
    }

    for (int y = 1; y <= 300; y++) {
        // xz[y][0][0] = true;
        for (int x = 0; x <= 300; x++) {
            for (int z = 0; z <= 300; z++) {
                xz[y][x][z + 1] = xz[y][x][z + 1] || xz[y][x][z];
            }
        }

        for (int z = 0; z <= 300; z++) {
            for (int x = 0; x <= 300; x++) {
                xz[y][x + 1][z] = xz[y][x + 1][z] || xz[y][x][z];
            }
        }
    }

    for (int z = 1; z <= 300; z++) {
        // xy[z][0][0] = true;
        for (int x = 0; x <= 300; x++) {
            for (int y = 0; y <= 300; y++) {
                xy[z][x][y + 1] = xy[z][x][y + 1] || xy[z][x][y];
            }
        }

        for (int y = 0; y <= 300; y++) {
            for (int x = 0; x <= 300; x++) {
                xy[z][x + 1][y] = xy[z][x + 1][y] || xy[z][x][y];
            }
        }
    }

    int ans = -inf;

    for (int x = 1; x <= 300; x++) {
        for (int y = 1; y <= 300; y++) {
            for (int z = 1; z <= 300; z++) {
                if (yz[x][y - 1][z - 1] > 0 && xz[y][x - 1][z - 1] > 0 &&
                    xy[z][x - 1][y - 1] > 0)
                    chmax(ans, x + y + z);
            }
        }
    }

    // for (int x = 1; x <= 5; x++) {
    //     for (int y = 1; y <= 5; y++) {
    //         for (int z = 1; z <= 5; z++) {
    //             cerr << x << ' ' << y << ' ' << z << ' ' << yz[x][y][z] << ' '
    //                  << xz[y][x][z] << ' ' << xy[z][x][y] << endl;
    //         }
    //     }
    // }

    if (ans < 0) ans = -1;

    cout << ans << endl;
}

Day3

最初の方ずっと 3 点とかでまー－－じで焦った。結論から言うと難しい回だったっぽいけど、それにしても。

A: device2

Communication Task なので、実装でバグらせてデバッグに無限時間使うのが怖くて後回し。自明だけ取って撤退。

f:id:RheoTommy:20220326203838p:plain

小課題 1

#include "Anna.h"
#include <utility>
#include <vector>

using namespace std;

namespace {}

int Declare() { return 2000; }

std::pair<std::vector<int>, std::vector<int>> Anna(long long A) {
    vector<int> a;
    for (int i = 0; i < A; i++) a.push_back(1);
    for (int i = 0; i < 2000 - A; i++) a.push_back(0);
    vector<int> s;
    vector<int> t;
    for (int i = 0; i < 1000; i++) s.push_back(a[i]);
    for (int i = 0; i < 1000; i++) t.push_back(a[1000 + i]);
    return {s, t};
}

#include "Bruno.h"
#include <utility>
#include <vector>

using ll = long long;

namespace {

int variable_example = 0;

}

long long Bruno(std::vector<int> u) {
    ll cnt = 0;
    for (auto ui : u) cnt += ui == 1;
    return cnt;
}

B: sprinkler

これ満点取れたから悔しい。

小課題 1 はとりあえずやるだけなので消化。

小課題 2, 3 も方針は比較的早く？思いついた気もしたけど、めっちゃくっちゃバグってた。

まず、木を見たのでオイラーツアーを考えると、どうにもきれいな性質がないので、BFS 順を考えると、頂点 $v$ から深さ $d$ の区間が連続になっているので遅延セグ木で勝てる！となる。遅延セグ木事態はすぐかけたんだけれど、BFS 順を振ったため、もとの頂点番号と BFS 順における頂点番号がごっちゃになっていろいろなバグを生み、小課題 2 が通るまでにかなーり時間を使う。

小課題 3 も同じ方針ですでに思いついていたけれど、親がいないときの自分自身に対するクエリの処理でずっとバグっていて時間を食った。

小課題 4 は DFS を再帰的に呼ぶみたいなイメージですぐに解いた。

ここで、各クエリごとに自分の親頂点からそれぞれ二つの区間に対して操作をすればいい、というのに気づいたので、満点解法は $O((N+QD)logN)$ で終わるじゃん！と思い、実装。3 点しか入らず、キレ、終わり。

後から見ると、この時点で満点解法に必要な考察はすべて終わっていて、$dp[v][d] = 頂点 v から深さ d の頂点に一様にかけられた値$ を考えればもう終わりなんだけれど、木を見たら適当な順に番号を振りたくなるパターン認識的な思考に完全に敗北してしまった。

f:id:RheoTommy:20220326205142p:plain

小課題 1

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

    int n;
    ll l;
    cin >> n >> l;

    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    vector<ll> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, d;
            ll w;
            cin >> x >> d >> w;
            x--;

            auto dfs = [&](auto &&dfs, int now, int par, int dist) -> void {
                if (dist > d) return;
                h[now] *= w;
                h[now] %= l;

                for (auto next : graph[now]) {
                    if (next == par) continue;
                    dfs(dfs, next, now, dist + 1);
                }
            };

            dfs(dfs, x, -1, 0);
        } else {
            int x;
            cin >> x;
            x--;
            cout << h[x] << endl;
        }
    }
}

小課題 2, 3

#include <algorithm>
#include <bits/stdc++.h>
#include <functional>

using namespace std;
using ll = long long;

template <typename T, typename L> struct lazy_segtree {
    using F = function<T(T, T)>;
    using FL = function<L(L, L)>;
    using FM = function<T(T, L)>;

    int n;
    int height;
    vector<T> node;
    vector<L> lazy;

    T idt;
    L idl;

    F op;
    FL composition;
    FM merge;

  private:
    T propagate_at(int i) {
        if (lazy[i] != idl) {
            node[i] = merge(node[i], lazy[i]);
            if (i < n) {
                lazy[i * 2] = composition(lazy[i * 2], lazy[i]);
                lazy[i * 2 + 1] = composition(lazy[i * 2 + 1], lazy[i]);
            }
            lazy[i] = idl;
        }
        return node[i];
    }

    void propagate_topdown(int i) {
        for (int k = height; k >= 0; k--) propagate_at(i >> k);
    }

  public:
    lazy_segtree(int _n, F op, FL composition, FM merge, T idt, L idl)
        : op(op), composition(composition), merge(merge), idt(idt), idl(idl) {
        int size = 1;
        int h = 0;
        while (size < _n) size *= 2, h++;
        n = size;
        height = h;

        node = vector<T>(2 * n, idt);
        lazy = vector<L>(2 * n, idl);
    }

    T get(int i) {
        i += n;
        propagate_topdown(i);
        return node[i];
    }

    void set(int i, T x) {
        i += n;
        propagate_topdown(i);
        node[i] = x;
        while (i /= 2)
            node[i] = op(propagate_at(i * 2), propagate_at(i * 2 + 1));
    }

    void set(int a, int b, L y) {
        if (a >= b) return;
        int l = a + n, r = b + n;
        propagate_topdown(l);
        propagate_topdown(r - 1);
        for (; l < r; l /= 2, r /= 2) {
            if (l & 1) propagate_at(l), lazy[l++] = y;
            if (r & 1) propagate_at(--r), lazy[r] = y;
        }
        l = a + n, r = b + n - 1;
        while (l /= 2)
            node[l] = op(propagate_at(l * 2), propagate_at(l * 2 + 1));
        while (r /= 2)
            node[r] = op(propagate_at(r * 2), propagate_at(r * 2 + 1));
    }
};

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

    int n;
    ll l;
    cin >> n >> l;

    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    vector<ll> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    vector<int> idx(n, -1);
    vector<int> ord;
    vector<int> par(n, -1);
    vector<int> left(n, -1);
    vector<int> right(n, -1);

    queue<int> que;
    que.emplace(0);
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        idx[now] = ord.size();
        ord.emplace_back(now);
        int last = -1;
        for (auto next : graph[now]) {
            if (idx[next] != -1) continue;
            if (left[now] == -1) left[now] = next;
            par[next] = now;
            last = next;
            que.emplace(next);
        }
        if (last != -1) right[now] = last;
    }

    vector<int> par_by_idx(n);
    for (int i = 0; i < n; i++) par_by_idx[i] = idx[par[ord[i]]];

    auto op = [&](ll x, ll y) { return (x * y) % l; };

    auto composition = [&](ll x, ll y) { return (x * y) % l; };

    auto merge = [&](ll x, ll y) { return (x * y) % l; };

    auto lst = lazy_segtree<ll, ll>(n, op, composition, merge, 1, 1);

    for (int i = 0; i < n; i++) lst.set(idx[i], h[i]);

    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, d;
            ll w;
            cin >> x >> d >> w;
            x--;

            assert(d <= 2);

            if (d == 0) {
                lst.set(idx[x], idx[x] + 1, w);
            } else if (d == 1) {
                lst.set(idx[x], idx[x] + 1, w);
                if (par[x] != -1) lst.set(idx[par[x]], idx[par[x]] + 1, w);
                if (left[x] != -1) lst.set(idx[left[x]], idx[right[x]] + 1, w);
            } else {
                if (par[x] != -1 && par[par[x]] != -1)
                    lst.set(idx[par[par[x]]], idx[par[par[x]]] + 1, w);
                if (par[x] != -1) lst.set(idx[par[x]], idx[par[x]] + 1, w);
                if (par[x] != -1)
                    lst.set(idx[left[par[x]]], idx[right[par[x]]] + 1, w);
                else
                    lst.set(idx[x], idx[x] + 1, w);
                if (left[x] != -1) lst.set(idx[left[x]], idx[right[x]] + 1, w);

                if (left[x] != -1) {
                    int l = idx[left[x]];
                    int r = idx[right[x]];

                    int p =
                        lower_bound(par_by_idx.begin(), par_by_idx.end(), l) -
                        par_by_idx.begin();

                    int q =
                        upper_bound(par_by_idx.begin(), par_by_idx.end(), r) -
                        par_by_idx.begin();

                    lst.set(p, q, w);
                }
            }
        } else {
            int x;
            cin >> x;
            x--;
            cout << lst.get(idx[x]) << "\n";
        }
    }
}

小課題 4

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

    int n;
    ll l;
    cin >> n >> l;

    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    vector<ll> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    vector<vector<bool>> seen(n, vector<bool>(40, false));

    auto dfs = [&](auto &&dfs, int now, int par, int d, int w) -> void {
        if (seen[now][d]) return;
        seen[now][d] = true;
        h[now] *= w;
        h[now] %= l;
        if (d == 0) return;

        for (auto next : graph[now]) {
            if (next == par) continue;
            dfs(dfs, next, now, d - 1, w);
        }
    };

    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, d;
            ll w;
            cin >> x >> d >> w;
            x--;

            assert(w == 0);

            dfs(dfs, x, -1, d, 0);
        } else {
            int x;
            cin >> x;
            x--;
            cout << h[x] << endl;
        }
    }
}

C: suger

こんなのは、無理だよ。

maroonk さんが解説してた。

f:id:RheoTommy:20220326205833p:plain

小課題 1

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    int q, l;
    cin >> q >> l;

    map<ll, ll> suger;
    map<ll, ll> ants;

    for (int qi = 0; qi < q; qi++) {
        int t;
        ll x, a;
        cin >> t >> x >> a;
        if (t == 1)
            ants[x] += a;
        else
            suger[x] += a;

        vector<pair<ll, ll>> sv;
        vector<pair<ll, ll>> av;
        for (auto [k, v] : suger) sv.emplace_back(k, v);
        for (auto [k, v] : ants) av.emplace_back(k, v);

        ll ans = 0;
        int i = 0;
        int j = 0;
        while (i < sv.size() && j < av.size()) {
            if (abs(sv[i].first - av[j].first) <= l) {
                ll m = min(sv[i].second, av[j].second);
                sv[i].second -= m;
                av[j].second -= m;
                ans += m;
                if (sv[i].second == 0) i++;
                if (av[j].second == 0) j++;
            } else {
                if (sv[i].first < av[j].first)
                    i++;
                else
                    j++;
            }
        }

        cout << ans << endl;
    }
}

Day4

過去一点が取れなかった。終わってみると、B はみんな取れてなくて、C は 100 か 14 以下か、みたいな感じで、取れるべきは A だったなぁと。

A: dango3

Communication Task. Output Only はでなかった。傾向的に Communication Task はひらめかないと結構厳しくて、Batch に可能枠があるのでそっちを優先してしまい、自明しかとってない。

f:id:RheoTommy:20220326210415p:plain

小課題 1, 2

#include "dango3.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

int variable_example = 1;

} // namespace

void Solve(int N, int M) {
    vector<bool> checked(N * M + 1, false);
    vector<vector<int>> ids;

    // cerr << N << " " << M << endl;

    for (int ni = 0; ni < N; ni++) {
        vector<int> ask;
        for (auto v : ids) ask.emplace_back(v[0]);

        // for (auto k : ask) cerr << k << ' ';
        // cerr << endl;

        int cnt = 0;
        int id = 1;
        while (cnt < N - 1 - ni) {
            if (!checked[id]) cnt++, ask.emplace_back(id);
            id++;
        }

        vector<int> group;
        while (id <= N * M) {
            if (!checked[id]) {
                ask.emplace_back(id);
                if (Query(ask)) {
                    group.emplace_back(id);
                    ask.pop_back();
                    checked[id] = true;
                }
            }
            id++;
        }

        ids.emplace_back(group);
    }

    for (int j = 0; j < M; j++) {
        vector<int> ans(N);
        for (int i = 0; i < N; i++) ans[i] = ids[i][j];
        Answer(ans);
    }
}

B: fish2

見た目が解かれそうなやつでめっちゃ時間かけちゃった気がする。

小課題 1 は愚直に処理するだけなので、やる。

ある魚が勝てない必要十分条件は、$X\ a\ b\ c\ Y$ みたいな並びで $X > a + b + c$ かつ $a + b + c < Y$ であることなので、ある $X$ に対して $Y$ の候補は一つで、これを二分探索で求めれば小課題 2 は通る。

小課題 3 も、これを毎回やれば $O(QNlogN)$ だけど通る気がしなかったので手を付けず。

小課題 2 の実装で $X$ や $Y$ が右端、左端のときの処理をしてなかったりで、実装には苦労した。

f:id:RheoTommy:20220326211108p:plain

小課題 1

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            ll y;
            cin >> x >> y;
            x--;
            a[x] = y;
        } else {
            int l, r;
            cin >> l >> r;
            l--;

            int ans = 0;

            for (int k = l; k < r; k++) {
                int li = k - 1;
                int ri = k + 1;
                ll now = a[k];
                while (true) {
                    if (li >= l && now >= a[li])
                        now += a[li], li--;
                    else if (ri < r && now >= a[ri])
                        now += a[ri], ri++;
                    else
                        break;
                }
                ans += li < l && ri + 1 > r;
            }

            cout << ans << endl;
        }
    }
}

小課題 2

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<ll> sum(n + 1);
    for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + a[i];

    vector<ll> sum_r(n + 1);
    for (int i = n - 1; i >= 0; i--) sum_r[i] += sum_r[i + 1] + a[i];

    auto max_l = [&](int r) {
        int ok = -1;
        int ng = r;
        while (ng - ok > 1) {
            int mid = (ng + ok) / 2;

            if (sum_r[mid] - sum_r[r] >= a[r])
                ok = mid;
            else
                ng = mid;
        }
        return ok;
    };

    int q;
    cin >> q;
    assert(q == 1);
    for (int qi = 0; qi < q; qi++) {
        int t;
        cin >> t;
        assert(t == 2);
        if (t == 1) {
            int x;
            ll y;
            cin >> x >> y;
            x--;
            a[x] = y;
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            assert(l == 0 && r == n);

            vector<ll> imos(n + 1, 0);

            for (int l = 0; l < n - 1; l++) {
                int r = lower_bound(sum.begin(), sum.end(), a[l] + sum[l + 1]) -
                        sum.begin() - 1;
                int s = sum[r] - sum[l + 1];
                if (s < a[r]) {
                    imos[l + 1] += 1;
                    imos[r] -= 1;
                }
            }

            for (int r = n - 1; r > 0; r--) {
                int l = max_l(r);
                if (l == -1 || sum_r[l + 1] - sum_r[r] < a[l])
                    imos[l + 1] += 1, imos[r] -= 1;
            }

            for (int i = 1; i < n; i++) {
                if (sum[i] < a[i]) imos[0] += 1, imos[i] -= 1;
            }

            for (int k = 1; k < n; k++) {
                if (sum[n] - sum[n - k] < a[n - k - 1])
                    imos[n - k] += 1, imos[n] -= 1;
            }

            for (int i = 0; i < n; i++) imos[i + 1] += imos[i];
            int cnt = 0;
            for (int i = 0; i < n; i++) cnt += imos[i] == 0;

            cout << cnt << endl;
        }
    }
}

C: reconstruction

可能枠よりに見えたけど、自明なクラスカル法から抜け出せなかった。

ある辺が採用される必要十分条件を考えるような方針にまずあんまりならなかったのがまずい。

小課題 3 ですべての辺を使う場合をやったので、ある辺が使われる条件を考える流れにもっていかないとだけど、小課題 4 とかで、グラフの差分が高速に計算できるんじゃないか的な発想に支配され、ダメだった。

f:id:RheoTommy:20220326211912p:plain

小課題 1, 2

#include <algorithm>
#include <bits/stdc++.h>
#include <shared_mutex>
#include <tuple>

using namespace std;
using ll = long long;


template <typename T> bool chmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

struct union_find {
    int n;
    vector<int> par;

    explicit union_find(int n) : n(n), par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (x > y) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    bool is_same(int x, int y) { return root(x) == root(y); }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, ll>> edges;
    for (int i = 0; i < m; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        a--, b--;
        edges.emplace_back(a, b, w);
    }

    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        ll x;
        cin >> x;

        auto uf = union_find(n);
        ll ans = 0;

        vector<tuple<ll, int, int>> diff;
        for (int i = 0; i < m; i++) {
            int a, b;
            ll w;
            tie(a, b, w) = edges[i];
            diff.emplace_back(abs(w - x), a, b);
        }

        sort(diff.begin(), diff.end());
        for (auto [w, a, b] : diff)
            if (uf.unite(a, b)) ans += w;

        cout << ans << endl;
    }
}

小課題 3

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;
const ll linf = 1001001001001001001ll;

template <typename T> bool chmin(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<ll>> edge(n - 1);
    for (int j = 0; j < m; j++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        a--, b--;
        assert(a + 1 == b);
        edge[a].push_back(w);
    }

    for (int i = 0; i < n - 1; i++) sort(edge[i].begin(), edge[i].end());

    vector<int> inds(n - 1, 0);

    int q;
    cin >> q;
    for (int qi = 0; qi < q; qi++) {
        ll x;
        cin >> x;

        ll ans = 0;
        for (int i = 0; i < n - 1; i++) {
            while (inds[i] + 1 < edge[i].size() && edge[i][inds[i] + 1] < x)
                inds[i]++;

            ll t = abs(x - edge[i][inds[i]]);
            if (inds[i] + 1 < edge[i].size())
                chmin(t, abs(edge[i][inds[i] + 1] - x));

            ans += t;
        }

        cout << ans << endl;
    }
}

競プロメモ

競プロなど

JOI'22 春合宿参加記

JOI'22 春合宿参加記

結果

感想

Day1

A: jail

B: kyoto

C: misspelling

Day2

A: copypaste3

B: flights

C: team

Day3

A: device2

B: sprinkler

C: suger

Day4

A: dango3

B: fish2

C: reconstruction