【Codeforces】Codeforces Round 945 (Div. 2) D. Cat, Fox and Maximum Array Split

問題

自力で解けたが、コンテスト時間内に間に合わなかった。

割と面白いので解説を書く。

解法

まず、 N 回で  \max_{i} A_{i} を特定する。

次に、 \max_{i} A_{i} の倍数を   \max_{i} A_{i} \times \left\lfloor \frac{N}{K} \right\rfloor まで調べれば良い。 各判定は  K 回でできるので、全体で  \left\lfloor \frac{N}{K} \right\rfloor \times K ( \leq N) 回でできる。

#include "my_template.hpp"
using namespace std;

void solve() {
    auto query = [](int l, int x) -> int {
        printi("?", l, x);
        INT(r);
        return r;
    };
    auto answer = [](int m) -> int {
        printi("!", m);
        INT(res);
        return res;
    };
    INT(N, K);
    int mx = 1;
    REP(x, 1, N + 1) {
        int r = query(1, x * N);
        if (r == N) {
            mx = x;
        }
    }
    i64 ans = -1;
    REP(d, 1, N / K + 1) {
        int val = mx * d;
        int l = 1, ok = 1;
        REP(t, K) {
            if (l == N + 1) {
                ok = 0;
                break;
            }
            int r = query(l, val);
            if (r == N + 1) {
                ok = 0;
                break;
            } else {
                l = r + 1;
            }
        }
        ok &= l == N + 1;
        if (ok) {
            ans = val;
        }
    }
    int res = answer(ans);
    assert(res == 1);
    return;
}

int main() {
    INT(T);
    REP(T) solve();
    return 0;
}

考察

以下のような流れで考察したと思う。

  1.  f(l, r)  l を固定すると  r について単調増加であることに気づく。

  2. 答えを決め打てば判定は  O(K) でできることに気づく。

  3. まず、部分問題として  K = N の場合を考える。 N 回で初項を特定すればあとは各項が初項と一致するか判定すれば良い。 K \lt N の場合でもとりあえず同じように初項を特定してみる。

  4. 次に、初項がわかっているときに何ができるか考える。区間幅を  2 と決め打って、? 1 2 * A[0] を投げてみると、 2 が返ってきた場合は  A_0 \geq A_1 がわかる。 N + 1 が返ってきた場合は  A_0 \lt A_1 がわかるが、 A_1 の具体的な値はわからない。 しかしこのように  A_{i} \lt A_{i+1} となるのは高々  N 回で、区間が伸びるのも  N 回なので、 2N 回で最大値が特定できる。最大値は使い道がありそうとなる。

  5. 並行して答えの上界を考える。鳩の巣原理より、長さが  \left\lfloor \frac{N}{K} \right\rfloor 以下であるような区間が必ず存在する。この区間に対する答えは   \max_{i} A_{i} \times  \left\lfloor \frac{N}{K} \right\rfloor 以下である。 さらに答えは  \max_{i} A_{i} の倍数になっているはずであり、以上より試すべき値が  \left\lfloor \frac{N}{K} \right\rfloor 通りしかないことに気づく。判定も含めて全体で  N 回でできる。

  6. 以上より  3N 回で答えはわかる。よく考えると最大値を特定するだけなら区間 N に対してのクエリを行うイメージでやると  N 回でできる。よって  2N 回になった。

感想

インタラクティブ問題難しすぎる。 典型手法のようなものを全く知らない気がする。

std::minmax は参照を返すので右辺値を渡してはいけない

ABC353 終了後にTLに流れてきた内容がためになったのでメモ。

罠について

以下のコードの実行結果について考えます。

#include <iostream>
#include <algorithm>
int main() {
    {
        int a = 1, b = 2;
        auto [mn, mx] = std::minmax(a, b);
        std::cout << mn << ", " << mx << std::endl;
    }
    {
        auto [mn, mx] = std::minmax(1, 2);
        std::cout << mn << ", " << mx << std::endl;
    }
    {
        int a = 1, b = 2;
        auto [mn, mx] = std::minmax(a + 0, b + 0);
        std::cout << mn << ", " << mx << std::endl;
    }
    return 0;
}

AtCoder のコードテストで実行すると以下のようになります。(言語は C++ 23 (gcc 12.2) を選択)

1, 2
0, 0
0, 0

3行とも 1, 2 が出力されると嬉しいですが、後半2つの実行結果が 0, 0 になってしまいました。 (なお、実行環境によっては3行とも 1, 2 となる場合もあります。)

原因

はじめに std::minmax についてですが、2つの値を渡した際には最小値と最大値への参照を、 initializer_list を渡した際には最小値と最大値を返す仕様になっています。

namespace std {
  template <class T>
  pair<const T&, const T&> minmax(const T& a, const T& b);

  template <class T>
  pair<T, T> minmax(initializer_list<T> t);
}

この参照を返すというのが原因となっています。

後半2つのケースについては、12 などの一時的な値や、a + 0b + 0 などの計算途中の値を関数に渡しています。一般にこれらを右辺値と言います。 また、std::minmax を含む式の評価が終わった時点で、参照の寿命が切れてしまいます。

したがって mnmx といった変数がすでに消えた右辺値を参照していることになり、未定義動作が発生するためにこのようなことが発生します。

なお、左辺値と右辺値について大雑把に説明すると、左辺値は変数に格納された値であり、右辺値は一時的な値であると考えれば良い気がします。

以下の記事が参考になります。

こちらは具体例も多くわかりやすいです。

対策

  • std::minmaxinitializer_list を渡す

以下のように std::minmax({}) とすれば引数として initializer_list が与えられるので大丈夫です。

#include <iostream>
#include <algorithm>
int main() {
    {
        int a = 1, b = 2;
        auto [mn, mx] = std::minmax({a, b});
        std::cout << mn << ", " << mx << std::endl;
    }
    {
        auto [mn, mx] = std::minmax({1, 2});
        std::cout << mn << ", " << mx << std::endl;
    }
    {
        int a = 1, b = 2;
        auto [mn, mx] = std::minmax({a + 0, b + 0});
        std::cout << mn << ", " << mx << std::endl;
    }
    return 0;
}
1, 2
1, 2
1, 2
  • コンパイルオプションに -fsanitize=undefined,address -g を付ける

実行時にエラーが出るので気づけると思います。

余談

ちなみに std::minmax だけではなく std::minstd::max についても、 2つの値を渡した際には最小値と最大値への参照を、 initializer_list を渡した際には最小値と最大値を返す仕様になっています。

ですがこれらは返り値が1つであり、mx = std::max(a, b) によって mx にコピーが行われてから引数 ab の寿命が切れるため、std::minmax のような罠を踏むことはありません。(このあたりは若干怪しいですが、構造化束縛の場合は参照を受け取っているだけで中身のコピーは発生していないと理解しています。)

感想

AddressSanitizer はやはり偉大。

参考文献

のいみさんのツイート

【AtCoder】Educational DP Contest / DP まとめコンテスト

コンテストのリンク

今更過ぎるけど全部解いたので提出コードや感想メモなど。

A - Frog 1

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VEC(i64, A, N);
    vector<i64> dp(N, INF<i64>);
    dp[0] = 0;
    REP(i, N - 1) {
        if (i + 1 < N) chmin(dp[i + 1], dp[i] + abs(A[i] - A[i + 1]));
        if (i + 2 < N) chmin(dp[i + 2], dp[i] + abs(A[i] - A[i + 2]));
    }
    print(dp[N - 1]);
    return;
}

int main() {
    solve();
    return 0;
}

B - Frog 2

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N, K);
    VEC(i64, A, N);
    vector<i64> dp(N, INF<i64>);
    dp[0] = 0;
    REP(i, N) {
        REP(k, 1, K + 1) {
            if (i + k < N) chmin(dp[i + k], dp[i] + abs(A[i] - A[i + k]));
        }
    }
    print(dp[N - 1]);
    return;
}

int main() {
    solve();
    return 0;
}

C - Vacation

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VV(i64, a, N, 3);
    vector dp(3, vector<i64>(N + 1, -INF<i64>));
    REP(k, 3) dp[k][0] = 0;
    REP(i, N) {
        REP(j, 3) {
            REP(k, 3) {
                if (j == k) continue;
                chmax(dp[k][i + 1], dp[j][i] + a[i][k]);
            }
        }
    }
    i64 ans = -INF<i64>;
    REP(k, 3) chmax(ans, dp[k][N]);
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

D - Knapsack 1

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N, W);
    VEC2(i64, w, v, N);
    vector dp(W + 1, -INF<i64>);
    dp[0] = 0;
    REP(i, N) RREP(j, W + 1 - w[i]) chmax(dp[j + w[i]], dp[j] + v[i]);
    print(MAX(dp));
    return;
}

int main() {
    solve();
    return 0;
}

E - Knapsack 2

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N, W);
    VEC2(i64, w, v, N);
    constexpr int V = 1000 * 100;
    vector dp(V + 1, INF<i64>);
    dp[0] = 0;
    REP(i, N) RREP(j, V + 1 - v[i]) chmin(dp[j + v[i]], dp[j] + w[i]);
    i64 ans = 0;
    REP(j, V + 1) if (dp[j] <= W) ans = j;
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

F - LCS

(この機会にLCSライブラリを作ったのは内緒。)

#include "my_template.hpp"
#include "dp/longest_common_subsequence.hpp"
using namespace std;

void solve() {
    STR(s, t);
    print(longest_common_subsequence(s, t));
    return;
}

int main() {
    solve();
    return 0;
}

G - Longest Path

DAGに対してはTopological Sortするという典型。

#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "graph/topological_sort.hpp"
using namespace std;

void solve() {
    INT(N, M);
    auto g = read_graph<int>(N, M, false, true);
    auto vs = topological_sort(g);
    vector<int> dp(N);
    FORE(v, vs) FORE(e, g[v]) chmax(dp[e.to], dp[v] + 1);
    print(MAX(dp));
    return;
}

int main() {
    solve();
    return 0;
}

H - Grid 1

#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;

void solve() {
    INT(H, W);
    VEC(string, a, H);
    vector dp(H, vector<mint>(W));
    dp[0][0] = 1;
    REP(i, H) REP(j, W) {
        if (a[i][j] == '#') continue;
        if (i + 1 < H) dp[i + 1][j] += dp[i][j];
        if (j + 1 < W) dp[i][j + 1] += dp[i][j];
    }
    print(dp[H - 1][W - 1]);
    return;
}

int main() {
    solve();
    return 0;
}

I - Coins

FPSでも解ける。

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VEC(f64, p, N);
    // 表の枚数 - 裏の枚数
    vector<f64> dp(2 * N + 1);
    dp[N] = 1;
    REP(i, N) {
        vector<f64> np(2 * N + 1);
        REP(j, 2 * N + 1) {
            if (j + 1 < 2 * N + 1) np[j + 1] += dp[j] * p[i];
            if (j - 1 >= 0) np[j - 1] += dp[j] * (1 - p[i]);
        }
        swap(dp, np);
    }
    f64 ans = 0;
    REP(i, 2 * N + 1) if (i - N > 0) ans += dp[i];
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

J - Sushi

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VEC(int, a, N);
    vector<int> x(4);
    REP(i, N) x[a[i]]++;
    vector dp(N + 1, vector(N + 1, vector<f64>(N + 1)));
    vector memo(N + 1, vector(N + 1, vector<int>(N + 1)));
    auto rec = [&](auto f, int x1, int x2, int x3) -> f64 {
        if (memo[x1][x2][x3]) return dp[x1][x2][x3];
        if (x1 == 0 and x2 == 0 and x3 == 0) return 0;
        memo[x1][x2][x3] = 1;
        if (x1 > 0) dp[x1][x2][x3] += (f(f, x1 - 1, x2, x3) + 1) * x1 / N;
        if (x2 > 0) dp[x1][x2][x3] += (f(f, x1 + 1, x2 - 1, x3) + 1) * x2 / N;
        if (x3 > 0) dp[x1][x2][x3] += (f(f, x1, x2 + 1, x3 - 1) + 1) * x3 / N;
        dp[x1][x2][x3] += (f64(N) - x1 - x2 - x3) / N;
        dp[x1][x2][x3] *= f64(N) / (x1 + x2 + x3);
        return dp[x1][x2][x3];
    };
    print(rec(rec, x[1], x[2], x[3]));
    return;
}

int main() {
    solve();
    return 0;
}

K - Stones

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N, K);
    VEC(int, A, N);
    vector<int> dp(K + 1);
    REP(k, 1, K + 1) {
        FORE(x, A) {
            if (k - x >= 0 and dp[k - x] == 0) {
                dp[k] = 1;
            }
        }
    }
    First(dp[K]);
    return;
}

int main() {
    solve();
    return 0;
}

L - Deque

区間DP。

未だに区間DPはメモ化再帰でしか書いたことがない気がする…。

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VEC(i64, A, N);
    // dp[l][r] = [l, r)
    vector dp(N + 1, vector<i64>(N + 1));
    vector memo(N + 1, vector<int>(N + 1));
    auto rec = [&](auto f, int l, int r) -> i64 {
        if (memo[l][r]) return dp[l][r];
        if (l == r) return 0;
        int used = N - (r - l);
        memo[l][r] = 1;
        if (used % 2 == 0) {
            // taro
            dp[l][r] = max(f(f, l + 1, r) + A[l], f(f, l, r - 1) + A[r - 1]);
        } else {
            // jiro
            dp[l][r] = min(f(f, l + 1, r) - A[l], f(f, l, r - 1) - A[r - 1]);
        }
        return dp[l][r];
    };
    print(rec(rec, 0, N));
    return;
}

int main() {
    solve();
    return 0;
}

M - Candies

累積和で高速化するDP。

昔は累積和の添字合わせに苦労していたけどさすがに今はかなり減ってきた。

#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;

void solve() {
    INT(N, K);
    VEC(int, A, N);
    vector<mint> dp(K + 1);
    dp[K] = 1;
    REP(i, N) {
        vector<mint> cp(K + 2);
        REP(j, K + 1) cp[j + 1] = cp[j] + dp[j];
        vector<mint> np(K + 1);
        REP(j, K + 1) {
            // np[j] = dp[j] + dp[j + 1] + ... + dp[j + A[i]]
            np[j] = cp[min(j + A[i] + 1, K + 1LL)] - cp[j];
        }
        swap(dp, np);
    }
    print(dp[0]);
    return;
}
int main() {
    solve();
    return 0;
}

N - Slimes

区間DP。

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VEC(i64, A, N);
    vector dp(N + 1, vector<i64>(N + 1, INF<i64>));
    vector memo(N + 1, vector<int>(N + 1));
    vector<i64> ac(N + 1);
    REP(i, N) ac[i + 1] = ac[i] + A[i];
    auto rec = [&](auto f, int l, int r) -> i64 {
        if (memo[l][r] == 1) return dp[l][r];
        if (r - l == 1) return dp[l][r] = 0;
        memo[l][r] = 1;
        for (int k = l + 1; k < r; k++) {
            // [l, k), [k, r) のスライムを合体
            chmin(dp[l][r], f(f, l, k) + f(f, k, r) + ac[r] - ac[l]);
        }
        return dp[l][r];
    };
    i64 ans = rec(rec, 0, N);
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

O - Matching

bitDP。

#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;

void solve() {
    INT(N);
    VV(int, A, N, N);
    const int N2 = 1 << N;
    vector<mint> dp(N2);
    dp[0] = 1;
    REP(bit, N2) {
        int pc = popcnt(bit);
        REP(i, N) {
            if (IBIT(bit, i)) continue;
            if (A[pc][i]) {
                dp[bit | (1 << i)] += dp[bit];
            }
        }
    }
    print(dp[N2 - 1]);
    return;
}

int main() {
    solve();
    return 0;
}

P - Independent Set

木DP。

#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;

void solve() {
    INT(N);
    auto g = read_graph<int>(N, N - 1);
    vector dp(2, vector<mint>(N, 1));
    auto rec = [&](auto f, int cur, int par) -> void {
        FORE(e, g[cur]) {
            if (e.to == par) continue;
            f(f, e.to, cur);
            dp[1][cur] *= dp[0][e.to];
            dp[0][cur] *= dp[0][e.to] + dp[1][e.to];
        }
    };
    rec(rec, 0, -1);
    mint ans = dp[0][0] + dp[1][0];
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

Q - Flowers

データ構造(Segment Tree)を使うDP。

#include "my_template.hpp"
#include "data_structure/segment_tree.hpp"
#include "algebra/monoid_s/monoid_max.hpp"
using namespace std;

void solve() {
    INT(N);
    VEC(int, h, N);
    VEC(i64, a, N);
    REP(i, N) h[i]--;
    SegmentTree<MonoidMax<i64>> seg(N);
    REP(i, N) {
        i64 mx = seg.prod(0, h[i]);
        chmax(mx, 0);
        seg.set(h[i], mx + a[i]);
    }
    print(seg.all_prod());
    return;
}

int main() {
    solve();
    return 0;
}

R - Walk

ダブリングを使うDP。

#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;

void solve() {
    I64(N, K);
    VV(int, A, N, N);
    vector db(60, vector(N, vector<mint>(N)));
    REP(i, N) REP(j, N) db[0][i][j] = A[i][j];
    REP(b, 59) REP(i, N) REP(j, N) REP(k, N) db[b + 1][i][j] += db[b][i][k] * db[b][k][j];
    vector dp(N, vector<mint>(N));
    REP(i, N) dp[i][i] = 1;
    REP(b, 60) {
        if (IBIT(K, b)) {
            vector np(N, vector<mint>(N));
            REP(i, N) REP(j, N) REP(k, N) np[i][j] += dp[i][k] * db[b][k][j];
            swap(dp, np);
        }
    }
    mint ans = 0;
    REP(i, N) ans += SUM(dp[i], mint(0));
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

S - Digit Sum

桁DP。

#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;

void solve() {
    STR(S);
    INT(D);
    vector dp(2, vector<mint>(D));
    dp[0][0] = 1;
    const int N = LEN(S);
    REP(i, N) {
        vector np(2, vector<mint>(D));
        REP(j, 2) {
            REP(k, D) {
                const int ud = j ? 9 : S[i] - '0';
                REP(d, ud + 1) np[j | (d < S[i] - '0')][(k + d) % D] += dp[j][k];
            }
        }
        swap(dp, np);
    }
    mint ans = dp[0][0] + dp[1][0] - 1;
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

T - Permutation

挿入DP。

昔解説ACした記憶がある。

昔はどのあたりが挿入なのかわからなかったが、今は「残っている数の集合から1つを抜き取って数列の末尾に付け加える」様子が挿入っぽいという理解をしている。

#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;

void solve() {
    INT(N);
    STR(S);
    // dp[i][j] = i 番目まで確定, i 番目の要素が残りの要素のうち j 番目
    vector<mint> dp(N);
    REP(i, N) {
        // p[0] = i
        dp[i] = 1;
    }
    REP(i, N - 1) {
        // dp = 未確定 N - 1 - i 個, 末尾要素 1 個
        // np = 未確定 N - 2 - i 個, 末尾要素 1 個
        vector<mint> np(N - 1 - i);
        vector<mint> cp(N + 1 - i);
        REP(j, N - i) cp[j + 1] = cp[j] + dp[j];
        if (S[i] == '<') {
            REP(j, N - 1 - i) {
                // 0 <= j <= N - 2 - i
                np[j] = cp[j + 1] - cp[0];
                // REP(k, 0, j + 1) np[j] += dp[k];
            }
        } else {
            // S[i] == '>'
            REP(j, N - 1 - i) {
                // 0 <= j <= N - 2 - i
                np[j] = cp[N - i] - cp[j + 1];
                // REP(k, j + 1, N - i) np[j] += dp[k];
            }
        }
        swap(dp, np);
    }
    mint ans = SUM(dp, mint(0));
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

U - Grouping

bitDP。

 n 要素からなる集合のべき集合について、各要素の部分集合を償却計算量  O( 3 ^ {n} ) で列挙するテクニックを使う。

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VV(i64, A, N, N);
    const int N2 = 1 << N;
    vector<i64> dp(N2);
    REP(bit, N2) {
        REP(j, N) {
            if (IBIT(bit, j) == 0) continue;
            REP(i, j) {
                if (IBIT(bit, i) == 0) continue;
                dp[bit] += A[i][j];
            }
        }
    }
    REP(bit, N2) FORSUB(s, bit) chmax(dp[bit], dp[bit ^ s] + dp[s]);
    print(dp[N2 - 1]);
    return;
}

int main() {
    solve();
    return 0;
}

V - Subtree

全方位木DP。

任意  \bmod であるため、この問題はDPで求めるものがモノイドであり群ではない(=逆元があるとは限らない)。 よって累積和を持つ必要があり、実装が大変。

抽象化ライブラリを作りたいなと思いつつもまだできていない。

#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "math/dynamic_modint.hpp"
using mint = mintd;
using namespace std;

void solve() {
    INT(N, M);
    mint::set_mod(M);
    auto g = read_graph<int>(N, N - 1);

    vector dp_cuml(2, vector<vector<mint>>(N));
    vector dp_cumr(2, vector<vector<mint>>(N));
    auto rec = [&](auto f, int cur, int par) -> void {
        FORE(e, g[cur]) {
            if (par == e.to) continue;
            f(f, e.to, cur);
        }
        dp_cuml[0][cur].assign(LEN(g[cur]) + 1, 1);
        dp_cuml[1][cur].assign(LEN(g[cur]) + 1, 1);
        dp_cumr[0][cur].assign(LEN(g[cur]) + 1, 1);
        dp_cumr[1][cur].assign(LEN(g[cur]) + 1, 1);
        REP(i, LEN(g[cur])) {
            auto e = g[cur][i];
            if (par == e.to) {
                dp_cuml[0][cur][i + 1] = dp_cuml[0][cur][i];
                dp_cuml[1][cur][i + 1] = dp_cuml[1][cur][i];
            } else {
                dp_cuml[0][cur][i + 1] = dp_cuml[0][cur][i] * dp_cuml[0][e.to].back();
                dp_cuml[1][cur][i + 1] = dp_cuml[1][cur][i] * (dp_cuml[0][e.to].back() + dp_cuml[1][e.to].back());
            }
        }
        RREP(i, LEN(g[cur])) {
            auto e = g[cur][i];
            if (par == e.to) {
                dp_cumr[0][cur][i] = dp_cumr[0][cur][i + 1];
                dp_cumr[1][cur][i] = dp_cumr[1][cur][i + 1];
            } else {
                dp_cumr[0][cur][i] = dp_cumr[0][cur][i + 1] * dp_cuml[0][e.to].back();
                dp_cumr[1][cur][i] = dp_cumr[1][cur][i + 1] * (dp_cuml[0][e.to].back() + dp_cuml[1][e.to].back());
            }
        }
    };

    rec(rec, 0, -1);
    vector dp_all(2, vector<mint>(N));
    auto rerooting = [&](auto f, int cur, int par, mint dp_par0, mint dp_par1) -> void {
        dp_all[0][cur] = dp_cuml[0][cur].back() * dp_par0;
        dp_all[1][cur] = dp_cuml[1][cur].back() * (dp_par0 + dp_par1);
        REP(i, LEN(g[cur])) {
            auto e = g[cur][i];
            if (par == e.to) continue;
            mint dp_cur0 = dp_cuml[0][cur][i] * dp_cumr[0][cur][i + 1] * dp_par0;
            mint dp_cur1 = dp_cuml[1][cur][i] * dp_cumr[1][cur][i + 1] * (dp_par0 + dp_par1);
            f(f, e.to, cur, dp_cur0, dp_cur1);
        }
    };
    rerooting(rerooting, 0, -1, 1, 0);
    REP(i, N) print(dp_all[1][i]);
    return;
}

int main() {
    solve();
    return 0;
}

W - Intervals

 dp_i = 文字列に含まれる 1 のうち、最も後ろにあるものが  i 文字目であるもののスコアの最大値

とし、 dp_0, dp_1, dp_2, ... と順番に計算する。

 dp_i を計算する際には、 dp_0, ... , dp_{i - 1} から遷移するが、スコアの重複加算を避ける必要がある。  i 文字目を 1 にすることによっても得られるスコア(つまり、 l_k \leq i \leq r_k である  k に対する  a_k のスコア)は  dp_{l_{k}}, ... , dp_{i - 1} にはまだ加算されていない状況にしておけば、単に  dp_{l_{k}}, ... , dp_{i - 1} の最大値を取ってきて、 a_k を加算することで求めることができる。

ところでここで求めた  dp_i についても、 dp_{i+1} 以降の計算で利用するときにはまだこの  a_k の分のスコアが加算されていない状況にしておく必要がある。

結局のところ、スコアの確定が遅れるイメージで、スコアの重複加算が発生しないところまで計算したら区間加算を行えば良い。 区間加算が必要なのでLazy Segment Treeを使う。

イメージとしてはLISやQ - Flowersに似ているのだが、こういう配列を使い回すDP全般のことをインラインDPと呼ぶらしい。

#include "my_template.hpp"
#include "data_structure/lazy_segment_tree.hpp"
#include "algebra/monoid_s_f/monoid_max_add.hpp"
using namespace std;

void solve() {
    INT(N, M);
    VEC3(i64, L, R, A, M);
    REP(i, M) L[i]--;
    LazySegmentTree<MonoidMaxAdd<i64>> seg(N + 1);
    seg.set(0, 0);
    vector<vector<int>> gr(N + 1);
    REP(i, M) gr[R[i]].push_back(i);
    REP(i, N) {
        i64 mx = seg.prod(0, i + 1);
        seg.set(i + 1, mx);
        FORE(ind, gr[i + 1]) seg.apply(L[ind] + 1, R[ind] + 1, A[ind]);
    }
    print(seg.all_prod());
    return;
}

int main() {
    solve();
    return 0;
}

X - Tower

どのブロックを使ったかを集合で管理しては状態数が多すぎるため、うまく減らすことを考える。

ある順序でブロックを並べ、各ブロックを塔の下に繋げるかを決めていくことにする。 こうすると、繋げられるかを判定する際には、それまでに使ったブロックの重さの総和だけわかれば良く、状態数の削減ができている。(順序がないものに対して順序を導入することで状態数を減らすという考え方)

ではどのような順序でブロックを並べれば良いのかというと、結論としては  s_i + w_i の小さい順に並べれば良い。

証明の方針としては

  1. 隣接するブロック i, j について、 s_i + w_i > s_j + w_j であるとき、入れ替えても損をしない

  2. 最適解の中に  s_i + w_i の小さい順に並んだものがあるので、この順番でブロックを塔の下に繋げるかを決めていくことにしても良い

という流れ。

↑本当は専門書を読んだほうが良いのだが…

入れ替えられることを示すためには、ブロック  i, j の上に積み上がっているブロックの総重量を  W として

  •  W \leq s_i
  •  W + w_i \leq s_j
  •  s_i + w_i > s_j + w_j

から

  •  W \leq s_j
  •  W + w_j \leq s_i

を示せば良い。

1つ目は  W \leq W + w_i \leq s_j より成立。

2つ目は  W + w_j = W + w_i + ( w_j - w_i ) \leq s_j + ( w_j - w_i ) \leq s_i より成立。

損をしないというのは、他のブロックが積み重ねられるかに影響を与えないことからわかる。 より正確には、ブロック  i, j より上のブロックについては下がどうなってるかはどうでも良く、ブロック  i, j より下のブロックについては入れ替え前後で自分より上のブロックの総重量は変化しないため。

ちなみにこの比較関数自体は、2つ目の条件である  W + w_j \leq s_i を示すためにはどういう条件が必要かを考えることで導出できる。

 W + w_j = W + w_i + ( w_j - w_i ) \leq s_j + ( w_j - w_i ) までは言えているわけで、最右辺の  s_j + (w_j - w_i) を睨むと出てくるように思う。

#include "my_template.hpp"
using namespace std;

void solve() {
    INT(N);
    VEC3(i64, w, s, v, N);
    vector<int> inds(N);
    iota(ALL(inds), 0);
    sort(ALL(inds), [&](int i, int j) { return s[i] + w[i] < s[j] + w[j]; });
    constexpr int W = 20000;
    vector<i64> dp(W + 1, -INF<i64>);
    dp[0] = 0;
    FORE(i, inds) {
        auto np = dp;
        REP(j, s[i] + 1) {
            if (dp[j] == -INF<i64>) continue;
            if (j + w[i] > W) continue;
            chmax(np[j + w[i]], dp[j] + v[i]);
        }
        swap(dp, np);
    }
    i64 ans = MAX(dp);
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

Y - Grid 2

解説ACした。包除原理を使う。

壁のマスを一旦無視してすべての移動経路数を数え上げ、壁マスを通る移動経路数を引けば良い。 壁マスを通る移動経路数を求める際に、初めて通る壁マスがどれかで場合分けする。

右か下にしか移動しないため、 x_i + y_i が小さい順に訪れるはずであり、その順でソートする。

あとはコード中のコメントを参照すればわかりそう。

#include "my_template.hpp"
#include "math/static_modint.hpp"
#include "math/binomial.hpp"
using mint = mint107;
using namespace std;

void solve() {
    Binomial<mint> B;
    INT(H, W, N);
    VEC2(int, x, y, N);
    REP(i, N) x[i]--, y[i]--;
    vector<int> inds(N);
    iota(ALL(inds), 0);
    sort(ALL(inds), [&](int i, int j) { return x[i] + y[i] < x[j] + y[j]; });
    // dp[i] = 初めてぶつかる壁マスが i であり (x_i, y_i) に行く場合の数
    // ans = \sum_{i} dp[i] * C(H - 1 - x[i] + W - 1 - y[i], H - 1 - x[i])
    // dp[i] = C(x[i] + y[i], x[i]) - (初めてぶつかる壁マスが i 以外で (x_i, y_i) に行く場合の数)
    // dp[i] = C(x[i] + y[i], x[i]) - \sum_{j} dp[j] * C(x[i] - x[j] + y[i] - y[j], x[i] - x[j])
    vector<mint> dp(N);
    mint ans = 0;
    REP(i, N) {
        int ind = inds[i];
        dp[i] = B.C(x[ind] + y[ind], x[ind]);
        REP(j, i) dp[i] -= dp[j] * B.C(x[ind] - x[inds[j]] + y[ind] - y[inds[j]], x[ind] - x[inds[j]]);
        ans += dp[i] * B.C(H - 1 - x[ind] + W - 1 - y[ind], H - 1 - x[ind]);
    }
    ans = B.C(H - 1 + W - 1, H - 1) - ans;
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

Z - Frog 3

Convex Hull Trickを使う。

 dp_j = dp_i + (h_j - h_i)^{2} + C を変形すると

 dp_j = -2h_i h_j + dp_i + h_i^{2} + h_j^{2} + C であり、  h_j^{2} + C i によらない。

 -2h_i h_j + dp_i + h_i^{2} は よく見ると  h_j の1次関数になっている。

ei1333さんのライブラリ を借りて実装した。

#include "my_template.hpp"
using namespace std;

// https://ei1333.github.io/library/structure/convex-hull-trick/dynamic-li-chao-tree.hpp

void solve() {
    I64(N, C);
    VEC(i64, h, N);
    DynamicLiChaoTree<i64, 0, 1000000, INF<i64>> cht;
    vector<i64> dp(N, INF<i64>);
    dp[0] = 0;
    cht.add_line(-2 * h[0], h[0] * h[0] + dp[0]);
    REP(i, 1, N) {
        i64 mn = cht.query(h[i]);
        dp[i] = mn + h[i] * h[i] + C;
        cht.add_line(-2 * h[i], dp[i] + h[i] * h[i]);
    }
    print(dp[N - 1]);
    return;
}

int main() {
    solve();
    return 0;
}

感想

TおよびV〜Zが特に勉強になった。(序盤もおそらく勉強になったのだろうけど、初めて解いた時に比べて実力が上がりすぎてもう良くわからない。) 最近は一周回ってこういう単元別問題集みたいなものを埋めていこうという気持ちになっているので、頑張りたい。

SAKANAQUARIUM 2024 "turn" 参加記

SAKANAQUARIUM 2024 "turn" に参加しました。

参加したのは2024年4月21日の幕張メッセ公演2日目です。

※内容に関するネタバレが含まれますので閲覧には十分注意してください。

前日まで

席はA注釈Lブロックでした。 事前にロッカー券(M)の購入は済ませていました。ロッカーはかなり役立ちました。

持ち物は以下のようになっています。

  • リュック
  • スマートフォン
  • 身分証明書
  • チケット
  • 予備のマスク
  • 飲料水
  • トートバッグ
  • タオル
  • モバイルバッテリー
  • 財布

反省点としては以下が挙げられます。

  • トートバッグではなく身につけるタイプのバッグをライブ会場に持っていくべきだったこと
  • 会場内はかなり暑いため、普段よりやや薄着でも良かったこと
  • 飲料水は500mlのペットボトル2本くらいあると良かったこと
  • 双眼鏡を持っていくこと
  • 折りたたみ傘を持っていくこと

当日(ライブ前)

グッズ販売に並んで体力を消耗するのが怖かったため、16:30ごろに会場に到着し、購入できそうならグッズを購入することにしました。海浜幕張駅に着いたらすでに今回のライブで販売されているタオルを首に巻いている方がたくさんいて、現地に着いたという実感が湧きました。

会場は実際のライブ会場入口と、グッズ販売コーナーやロッカーなどがある入口に分かれており、ライブ会場入口はまだ開いていなかったため、もう一つの入口に向かいました。なお、グッズの購入などを済ませ、すでにライブ会場入口の待機列(整理番号によって列が異なる)に並んでいる人も多く見られました。

グッズ販売などの入口には各団体からのお祝いの花が飾ってあり、そのすぐ近くでロッカーの鍵を受け取ることができるようになっていました。 ロッカーはおそらく余っていたため、当日の購入も可能だったと思います。

ロッカーに荷物を預け、グッズ整理券を発行し(LINEのGPS機能を使っており、会場付近でしか発行できない)、グッズを購入しました(おそらく17:00頃)。 Tシャツが売り切れていたため1500円のタオルのみ購入しましたが、その後1000円のステッカーが欲しくなってしまいました。しかし整理券は各LINEアカウントにつき1枚しか発行できないということで困っていると、程なくして整理券がなくともグッズ販売列に並ぶことができるようになったため、無事買うことができました。(ついでにもう1つタオルを保存用に購入しました。)

そうしているうちにライブ会場への案内が開始しており、自分が入るときにはすでに整理番号による列はなくなっていました。

ライブ会場入口には飲料水を法外な価格で販売している出店がありましたが、周りに自販機がなく、500mlの水1本ではやや心もとなかったため300円でオレンジジュースを購入しました。結果としては高かったですが購入して正解でした。

会場は基本的に立ち見でした。 入ったときには何人か座っている方もいましたが、人が増えてくるにつれてスタッフの方から立つように指示があり、開始前には全員立っているという状況でした。

17:40頃には準備を終え、開始をじっと待つ状況でした。

開始前に会場で流れていた曲はアレンジが中心であまりわかりませんでしたが、以前コロナ禍にYouTubeで配信したライブ映像をまとめた「LIVE FISH -COMPLETE BOX-」の付録のリアレンジアルバムに収録されている「シーラカンスと僕」「忘れられないの」「白波トップウォーター」のボーカルがないものは少なくとも流れていたと思います。

当日(ライブ中)

ライブ会場はステージ両脇に大きなスクリーンがあり、普段ライブDVDで見るような視点・切り替え方の映像を見ることができました。これは後方席の方への配慮だと思いますが、それ以上にリアルタイムで流れる映像であるにも関わらず切り替えが非常にスムーズかつ上手で驚きました。(もはやこれがライブDVDにできるレベル)

…まあ驚いたのですが、せっかくなので本人らの姿を見ようということで、あまりこれらのスクリーンは見ていなかったように思います。(A注釈Lブロックであるためはっきりと見ることはできませんでしたが。)

また、マスクを付けている人はかなり少なかったと思います。(私はライブ中はほとんど付けていました。)

以下は、終了直後にセットリストを記憶を頼りに復元し、帰りの電車で各曲の感想について書きなぐったメモをもとに作成しています。

Ame(B)

  • 最初の感想「これが1曲目か〜渋いね!」
  • 最初の「アメ」からの歓声がマジで良い
  • 1曲目ということもあり音圧がすごすぎて呆然としていた記憶

陽炎

  • 普段はサカナクションの曲の中では聴かないほうの曲
  • ただかなり楽しくてライブ化けする曲だと感じた
  • このライブを通して好きな曲になった
  • 素晴らしすぎて泣いていた
  • 多分陽炎だったと思うが、歌いながら一郎様が寝そべってて会場から笑いが起きていた(寝そべっていたのはアイデンティティかもしれない)
  • ライブ映像でよく見る「一郎様が最後のサビの前でセルフビブラートをかけるやつ」が聴けて良かった

アイデンティティ

  • 縦ノリが楽しい
  • 合いの手が楽しい
  • ラスサビの後など歌える部分も多い
  • 安定かつ至高

ルーキー

  • アイデンティティの次にルーキーが来るか多分、風。が来るかはかなり気になっていたが今回はルーキーだった
  • レーザー的な演出は多分このライブでは初登場だったこともあり、何度も後ろを振り返ってしまった

Aoi

  • ルーキーから多分、風。ではなかった
  • ただやっぱり良い曲なんだよな〜盛り上がるアツい曲がどんどん出てきて気持ちが良い

プラトー

  • ついに最近の曲が来た〜〜
  • サビに入る時の手の振り方が楽しい
  • 新旧のバランスが良い

ユリイカ

  • 𝓒𝓱𝓲𝓵𝓵 𝓩𝓸𝓷𝓮突入
  • ステージの背景が変わって、縦長の長方形が5つくらい並ぶようなものになり、東京のビルの並びを表現していた
  • スクリーンを見るといい感じに東京のビルの街並みとバンドの演奏風景がマッチしており、映像としての完成度が高い

流線

  • ライブ仕様(サビで音程が下がらないやつ)が聴けてよかった
  • ちょっと前と違い、かなり落ち着いて聴ける曲が続いて体力的にも助かる
  • ところで流線って結構マイナーな曲だよなと思ったけどどうなんでしょう

ナイロンの糸

  • 落ち着いた曲が続いている
  • しかし音圧がすごいため、地味などという感想は全く出てこず、普通に涙が出てくる
  • 背景が海の映像を丸く切り抜いたやつ(多分)だったが、これもまたスクリーンから見るとバンドの演奏風景とマッチしており、映像としてかなり完成している

ネプトゥーヌス

  • う、うおおおおおおおおおおおお!?!?!?
  • かなりマイナーな曲だが個人的にはかなり好き
  • 出ると思っていなかったため衝撃でびっくり
  • この曲は本当に高音に次ぐ高音という感じなのだが、「あ、これライブで歌えるんだ、すごすぎる」と唖然としていた
  • 正直一番感動したかも(少なくとも記事を書いている時点で一番印象に残ってます)
  • 純粋に一郎様の歌のうまさを感じることができる素晴らしいチョイス

ボイル

  • ボイルってマジでライブ化けしますよね
  • 曲自体が落ち着いた雰囲気→サビに向けて爆上げという感じであるため、盛り上がりを取り戻すための1曲として素晴らしいチョイスだと感じた
  • 1日目はさよならはエモーションだったらしく、あの曲もだんだん盛り上がる系の曲であるためそれはそれでアリだな…という気持ちに

ホーリーダンス

  • 「おっおっ おっおっ おっおおっおおっおっ」←ここ踊るの楽しい
  • サビ前の盛り上がりが良い
  • サビでは手を振りまくった

『バッハの旋律を夜に聴いたせいです。』

  • いわゆるメンバーが変身して横並びの配置になるときの曲枠
  • リミックスされておりかなり雰囲気は違った
  • 一旦幕が下りて、高めの位置で幕が開いてそこから5人登場という演出
  • 見てる時「ん、5人の位置やたら高いな」→「いや高すぎんだろ…(驚愕)」
  • 思ったよりだいぶ台が上昇しておりびっくり
  • ここだけはさすがに音がデカすぎてやや耳が痛かった
  • 視覚の演出もかなり気合が入っており、(席の都合でレーザー光は当たらなかったが)スクリーンの点滅がかなり迫力がある

ネイティブダンサー

  • 情けない話なんですが曲の終盤まで曲名が思い出せなかった
  • ライブとCDで別曲すぎるのが悪いよ(開き直り)
  • キーも違うし
  • この曲は手拍子が難しくて、みんなできてなかった

ミュージック

  • まあ5人で並んでるんだから来るでしょうという(ただそういう安心感が嬉しい)
  • やっぱり高台にいるときのこの曲→ラスサビだけバンドスタイルは何度見ても素晴らしい

ショック!

  • 懺悔するとMVを真剣に観ていなかったためダンスがあまりわからなかったが、周りを見ながらそれっぽい動きをしていた
  • この曲もライブ前後でかなり印象が変わったな〜好きになった

モス

  • 「マイノリティ」の掛け声がいい
  • ビームの色がコロコロ変わって良いね
  • 拍手ゾーンと手を振るゾーンがはっきりと分かれていて、身体に優しい曲(さすがにこの頃には疲労もある)

新宝島

  • き、きたあああああああ!!!!!!!!!
  • 王道
  • チアの人たちもちゃんといた
  • が、チアの人たちに気を取られて序盤は曲を聴けていなかった気がする

忘れられないの

  • 834.194アルバム収録曲ラッシュ
  • サビ直前のフリを真似してる人がいて、詳しいな!となった
  • 曲のタイトルにもあるが、忘れられない1日になったことを実感していた

夜の踊り子

  • アンコールなのに舞妓さん出てきてビビる
  • アンコール曲もきちんと準備しております
  • うぉうぉうぉうぉ、のコールが楽しいですね
  • アンコールの拍手が長く、出てくるまでだいぶ時間かかっていたため終わってしまったのか?と焦っていた

新宝島

  • 新宝島!?もうすでに演奏しているはずでは!?
  • 実はフリートークの中でSPEAKER+の音圧の凄さを伝えるために1番だけ再度演奏することに
  • おそらくいきなりやることになったように見えるが、きちんと背景の映像も流れていた
  • 普通のライブは90dB程度だが、今回は120dBらしい(細かい数字は間違っているかも)
  • 1番のどこかで音圧が変わったらしい(多分サビ前)
  • 前の方だったから音圧を変える前でもしっかり聴こえたが、後ろの方の席の人はより差が明確にわかったかもしれない

白波トップウォーター

  • デビューから17年経ちましたみたいなトークの流れで歌われた曲
  • デビュー曲といえば三日月サンセットじゃないのか?と思ったら昨日は三日月サンセットで、なんと変わっていたらしい
  • まあどっちも最初のアルバムの曲なので、OK

シャンディガフ

  • 目が明く藍色かな〜と思っていたが最近の曲だった〜
  • かなり落ち着いた曲
  • スタッフロールも流れ、ああ終わってしまったのか…という気持ちに
  • 本当にチームサカナクションに感謝…

こうして見ると、どうしても感想が視覚的な内容や曲に対する自分の思いがメインで、音に関する感想が少なめになってしまいますね…。 ただ、裏を返せば視覚的な感想がこんなにたくさん出てくるライブであるということでもあります。 ちゃんと音についても常に大音量でめちゃくちゃ迫力があったので、そこに関しては勘違いしないでください。

当日(ライブ後)

グッズ販売などは引き続き可能でしたが、交通機関の都合もあり、ロッカーから荷物を取り出して早々と帰宅を開始しました。ロッカーの鍵は挿しっぱなしで良いため、助かりました。

帰り道は雨が降っており、サカナクションのライブということもあり趣深いものではありましたが、折りたたみ傘は持ってきたほうが良いかもしれません。ただ周りの人の傘が当たるケースがあり、危なかったです。

海浜幕張駅では駅への入場規制が行われており、早く動き出して正解でした。また電車の本数もあまり多くはないため、グッズ販売コーナーに行く場合はホテルを取るなどの必要がありそうでした。

無事家に帰宅することができました。

感想

今までライブに行った経験はありませんでしたが、とても良いものでした。かれこれサカナクションの曲を聴き始めて7年近くが経過しようとしていますが、CDで聴く音楽とライブで聴く音楽は全く別のものであり、改めて各曲の良さを認識し直すことができました。

本当に良かったのでまた参加したいなと思います。次行くときは誰かと一緒に行くというのもアリだな…と。

【AtCoder】ABC350 G - Mediator

問題

解法1 クエリ平方分割

もしクエリが1つしかない場合、以下の方法で求められる。

森の連結成分ごとに適当に根を取り、DFSで各頂点の親を求めると、各クエリについて、 u v の親のいずれかが候補になるため、親を  p とすると、辺  (u, p) と辺  (p, v) が存在するかを、辺集合を std::set などで管理して判定すれば良い。

問題はDFSを毎回していると間に合わないことであるが、 BS 回ごとに行うことにして、代わりに候補として  u v の親だけでなく、最後にDFSを行った後に追加した辺すべてについて見れば良い。

提出コード(1391ms)

#include "my_template.hpp"
#include "data_structure/unionfind.hpp"
using namespace std;

constexpr i64 MOD = 998244353;
constexpr int BS = 300;

void solve() {
    INT(N, Q);
    set<pair<int, int>> es1, es2;
    vector<int> X(Q + 1);
    int l = 0;
    vector<vector<int>> G(N);
    vector<int> seen(N), par(N);
    UnionFind uf(N);
    REP(q, Q) {
        I64(a, b, c);
        i64 A = 1 + ((a * (1 + X[l])) % MOD) % 2;
        i64 B = ((b * (1 + X[l])) % MOD) % N;
        i64 C = ((c * (1 + X[l])) % MOD) % N;
        if (A == 1) {
            es2.insert({B, C});
            es2.insert({C, B});
        } else {
            int ans = -1;
            if (uf.same(B, C)) {
                vector<int> candidates;
                if (par[B] != -1) candidates.push_back(par[B]);
                if (par[C] != -1) candidates.push_back(par[C]);
                FORE(cans, candidates) {
                    if (es1.count({cans, B}) > 0 and es1.count({cans, C}) > 0) {
                        ans = cans;
                        break;
                    }
                }
            } else {
                vector<pair<int, int>> ces2(ALL(es2));
                FORE(e, ces2) {
                    if (e.first == B or e.first == C) {
                        int cans = e.second;
                        if ((es2.count({cans, C}) > 0 or es1.count({cans, C}) > 0) and (es2.count({cans, B}) > 0 or es1.count({cans, B}) > 0)) {
                            ans = cans;
                            break;
                        }
                    } else if (e.second == B or e.second == C) {
                        int cans = e.first;
                        if ((es2.count({cans, C}) > 0 or es1.count({cans, C}) > 0) and (es2.count({cans, B}) > 0 or es1.count({cans, B}) > 0)) {
                            ans = cans;
                            break;
                        }
                    }
                }
            }
            l++;
            X[l] = ans + 1;
            print(X[l]);
        }
        if (q % BS == 0) {
            // update
            FORE(e, es2) {
                es1.insert(e);
                G[e.first].push_back(e.second);
                uf.merge(e.first, e.second);
            }
            es2.clear();
            seen.assign(N, 0);
            par.assign(N, -1);
            REP(i, N) {
                if (seen[i] == 0) {
                    auto rec = [&](auto f, int c, int p) -> void {
                        par[c] = p;
                        seen[c] = 1;
                        FORE(e, G[c]) {
                            if (p != e) {
                                f(f, e, c);
                            }
                        }
                    };
                    rec(rec, i, -1);
                }
            }
        }
    }
    return;
}

int main() {
    solve();
    return 0;
}

解法2 マージテク

判定部分は解法1で説明したクエリが1つの場合と同じ。毎回DFSをしていると間に合わないが、 u v のうち連結成分数が小さい方が  u であるとすると、 u を根と見てDFSをして、 u の親を  v と更新する。

こうすることでマージテクによって計算量が抑えられる。

提出コード(76ms)

#include "my_template.hpp"
#include "data_structure/unionfind.hpp"
using namespace std;

constexpr i64 MOD = 998244353;

void solve() {
    INT(N, Q);
    i64 lans = 0;
    vector<set<int>> G(N);
    vector<int> par(N);
    UnionFind uf(N);
    REP(q, Q) {
        I64(a, b, c);
        i64 A = 1 + ((a * (1 + lans)) % MOD) % 2;
        i64 B = ((b * (1 + lans)) % MOD) % N;
        i64 C = ((c * (1 + lans)) % MOD) % N;
        if (A == 1) {
            auto rec = [&](auto f, int cur, int p) -> void {
                par[cur] = p;
                FORE(e, G[cur]) {
                    if (p != e) {
                        f(f, e, cur);
                    }
                }
            };
            if (uf.size(B) < uf.size(C)) {
                rec(rec, B, C);
            } else {
                rec(rec, C, B);
            }
            uf.merge(B, C);
            G[B].insert(C);
            G[C].insert(B);
        } else {
            // A == 2
            int ans = -1;
            vector<int> candidates;
            if (par[B] != -1) candidates.push_back(par[B]);
            if (par[C] != -1) candidates.push_back(par[C]);
            FORE(cans, candidates) {
                if (G[B].count(cans) > 0 and G[C].count(cans) > 0) {
                    ans = cans;
                    break;
                }
            }
            lans = ans + 1;
            print(lans);
        }
    }
    return;
}

int main() {
    solve();
    return 0;
}

感想

そもそも根付き木としてみたときの親しか候補にならないというのもはっきりとはわからず、LCAや集合の共通部分(bitset)を考えていた気がする(bitsetも平方分割するとできるらしいが)。マージテクは考えてもわからなかったが、多分上記の部分が詰められなかったことに原因がある気がする。

マージテクで実装すればかなり楽だったので、通したかったな…。

Link Cut Treeを使った方法もあとで学んでおきたい。

【AtCoder】ABC347 F - Non-overlapping Squares

問題

解法

適当に  N \times N の領域を3つの長方形に区切り、さらにそれぞれの長方形から  M \times M の正方形を取り出すと考えて良い。

その場合、3つの長方形の区切り方は以下の6つのいずれかになる。

|--------|     |--------|
|        |     |  |  |  |
|--------|     |  |  |  |
|        |     |  |  |  |
|--------|     |  |  |  |
|        |     |  |  |  |
|--------|     |--------|

|--------|     |--------|
|        |     |  |     |
|--------|     |  |     |
|    |   |     |  |-----|
|    |   |     |  |     |
|    |   |     |  |     |
|--------|     |--------|

|--------|     |--------|
|    |   |     |     |  |
|    |   |     |     |  |
|    |   |     |-----|  |
|--------|     |     |  |
|        |     |     |  |
|--------|     |--------|

この長方形の区切り方を全探索する。なお、上記の図の左側にある3つの切り方を試した後、90度回転してもう一度同様の処理を行うことで実装をやや楽にできる。

各長方形の中でマス目の総和が最大の正方形を取り出すときには、あらかじめ2次元累積和ですべての  M \times M の正方形に対するマス目の総和を求めておき、その値を2次元セグメント木に乗せることで、2次元領域に対するRMQに帰着すれば良い。

#include "my_template.hpp"
#include "data_structure/cumulative_sum_2d.hpp"
#include "data_structure/segment_tree_2d.hpp"
#include "algebra/monoid_s/monoid_max.hpp"
using namespace std;

void solve() {
    INT(N, M);
    VV(i64, A, N, N);
    i64 ans = 0;
    REP(_, 2) {
        CumulativeSum2D<i64> cum(A);
        vector B(N - M + 1, vector<i64>(N - M + 1));
        REP(i, N - M + 1) REP(j, N - M + 1) B[i][j] = cum.sum(i, j, i + M, j + M);
        SegmentTree2D<MonoidMax<i64>> seg(B);
        // [       ]
        // x-------
        // [  ]y[  ]
        REP(x, M, N + 1 - M) {
            i64 v1 = seg.prod(0, 0, x - M + 1, N - M + 1);
            REP(y, M, N + 1 - M) {
                i64 v2 = seg.prod(x, 0, N - M + 1, y - M + 1);
                i64 v3 = seg.prod(x, y, N - M + 1, N - M + 1);
                chmax(ans, v1 + v2 + v3);
            }
        }
        // [  ]y[  ]
        // x-------
        // [       ]
        REP(x, M, N + 1 - M) {
            i64 v1 = seg.prod(x, 0, N - M + 1, N - M + 1);
            REP(y, M, N + 1 - M) {
                i64 v2 = seg.prod(0, 0, x - M + 1, y - M + 1);
                i64 v3 = seg.prod(0, y, x - M + 1, N - M + 1);
                chmax(ans, v1 + v2 + v3);
            }
        }
        // [      ]
        // x------
        // [      ]
        // y------
        // [      ]
        REP(x, M, N + 1 - M) {
            i64 v1 = seg.prod(0, 0, x - M + 1, N - M + 1);
            REP(y, x + M, N + 1 - M) {
                i64 v2 = seg.prod(x, 0, y - M + 1, N - M + 1);
                i64 v3 = seg.prod(y, 0, N - M + 1, N - M + 1);
                chmax(ans, v1 + v2 + v3);
            }
        }
        // rotate
        rot(A);
    }
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

感想

Twitterを見ていたら「品目典型」と名付けられていて良いセンスだなと感心した。 類題として ABC062 C - Chocolate Bar が挙げられていたが、 1つの長方形を3つの長方形に分割する問題であり、今回のような3つの正方形を取る問題でも長方形から取り出すと考えることでこのテクニックを応用できるというのが勉強になった。

【AtCoder】パ研合宿2023 第1日「SpeedRun」D - Bishop

問題

解法

 (x, y) に操作を行うと  (x + K, y + K) または  (x + K, y - K) に移る。

つまり、 (x + y, x - y) に操作を行うと  (x + y + 2 K, x - y) または  (x + y, x - y - 2 K) に移る。

ここで  a = x + y, b = x - y という変数を導入すると

 (a, b) は操作後に  (a + 2 K, b) または  (a, b - 2K) に移るといえる。

これで  a b を独立に考えることができるようになったため、答えは  \left \lceil \frac{|a|}{2K} \right \rceil + \left \lceil \frac{|b|}{2K} \right \rceil になる。

#include "my_template.hpp"
using namespace std;

void solve() {
    I64(K, X1, Y1, X2, Y2);
    i64 x = abs(X1 - X2), y = abs(Y1 - Y2);
    i64 a = abs(x + y), b = abs(x - y);
    i64 ans = ceil(a, 2 * K) + ceil(b, 2 * K);
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

感想

無限人通していてかなり厳しい気持ちになった。

45度回転をマンハッタン距離の最大化の文脈でしか使えていないということが判明。 もうちょっと一般化して、 x+y, x-y という変数を導入することで式変形ができるようになる手法、くらいに思っておくと良さそう。

マンハッタン距離の最大化

 (x_1, y_1), (x_2, y_2), ... , (x_n, y_n) が与えられる。 点  (x_q, y_q ) とのマンハッタン距離の最大値について

 (a_i, b_i) = (x_i + y_i, x_i - y_i) とおくと

 \max_{1 \leq i \leq n} ( |x_i - x_q| + |y_i - y_q| )

 = \max_{1 \leq i \leq n} ( \max(x_i - x_q, x_q - x_i ) + \max(y_i - y_q, y_q - y_i) )

 = \max_{1 \leq i \leq n} ( x_i - x_q + y_i - y_q, x_i - x_q + y_q - y_i, x_q - x_i + y_i - y_q, x_q - x_i + y_q - y_i)

 = \max_{1 \leq i \leq n} ( a_i - a_q, b_i - b_q, b_q - b_i, a_q - a_i)

 = \max_{1 \leq i \leq n} ( \max( |a_i - a_q|, |b_i - b_q |))

となり、 a, b それぞれで最大値を求めてから大きい方を選択すれば求められるというテクニックのこと。

またこの  \max( |a_i - a_q|, |b_i - b_q |)  (a_i, b_i)  (a_q, b_q) のチェビシェフ距離と言う。