06 Circle Splits

問題

$2$ 次元平面上に始め何も置かれていません。

$N$ 個の円 (中心が $(x_{i}, y_{i})$ で、半径が $r_{i}$)を $2$ 次元平面上に順に置きます。それぞれの円を置くたびに、平面が幾つの領域に分割されるかを出力してください。

ただし、$N$ 個の円は全て異なり、どの $3$ つの円も $1$ 点で交わることはありません。

$1\leq N\leq 1000$

他の値域は $10^{9}$ 以下

解説

答えだけをいうと、$i$ 番目を追加した後、平面は以下の式の形に分割されます。

$$1 + 交点の数 + 円の連結成分の数$$

円の連結成分の数というのは、円を頂点として、交わっている円同士には辺が張られているグラフの連結成分のことです。

この式でいい理由は、オイラーの多面体定理で証明が可能です。

なので、円同士の交点の数を求めた後に、Union Find を用いて答えを求めることができます。

void solve(){
    int N;
    cin >> N;
    vector<ll> X(N), Y(N), R(N);
    rep(i, 0, N) cin >> X[i] >> Y[i] >> R[i];
    auto f = [&](int a, int b) -> int {
        if (R[a] > R[b]) swap(a, b);
        ll dist = (X[a] - X[b]) * (X[a] - X[b]) + (Y[a] - Y[b]) * (Y[a] - Y[b]);
        ll C = (R[a] + R[b]) * (R[a] + R[b]);
        ll IN = (R[b] - R[a]) * (R[b] - R[a]);
        if (dist < IN) return 0;
        if (dist == IN) return 1;
        if (C > dist) return 2;
        if (C == dist) return 1;
        return 0;
    };
    int ans = 1;
    UF T(N);
    rep(i, 0, N){
        rep(j, 0, i){
            int tmp = f(i, j);
            if (tmp == 0) continue;
            T.unite(i, j);
            ans += tmp;
        }
        cout << ans + T.component - (N - i - 1) << "\n";
    }
}

07 Momo's Tour

問題文

整数 $N, D$ が与えられます。以下の条件を満たす長さ $N + 1$ の整数列 $A =(A_{0}, A_{1}, \dots , A_{N})$ の数を $\pmod{998244353}$ で求めてください。

$A_{0} = 0$
$A$ は広義単調増加
$(0, 1, \dots , N)$ の順列 $P$ であって、全ての整数 $i$ に対して $|A_{P_{i}} - A_{P_{i + 1}}| \leq D$ を満たすものが存在する。ただし、$i = N + 1 + i$ とする。

$1\leq N\leq 10^{10}$

$0\leq D\leq 100$

解説

結局 $A$ の $3$ つめの条件は以下のように置き換えられます。

$0\leq i \leq N - 2$ に対して、$A_{i + 2} - A_{i} \leq D$ が成り立つ。
$A_{1}\leq D$

$dp[i][j]$ を長さが $i + 1$ で $A_{i + 1} - A_{i} = j$ が成り立つ数列 $A$ の総数とすると、$O(ND^{2})$ で求まり、この遷移は行列累乗に乗るので $O(D^{3} \log(N))$ です。

以下の実装はテンプレを削除してますが雰囲気でわかると思います。

void solve(){
    ll N, D;
    cin >> N >> D;
    vector base(D + 1, vector<mint>(D + 1));
    rep(i, 0, D + 1) rep(j, 0, D + 1){
        if (i + j <= D) base[i][j] = 1;
    }
    auto ans = pow_matrix<calc>(base, N);
    cout << vec_sum(ans[0]).val() << "\n";
}

08 minimum linear ordering

問題

長さ $A$ の正整数列が $2$ つ $X, Y$ と長さ $B$ の正整数列が $2$ つ $Z, W$ が与えられます。

以下の条件を全て満たす長さ $N$ の正整数列 $f = (f(1), f(2), \dots f(N))$ が存在するか判定し、存在するなら $\max{f}$ の最小値を出力してください。

全ての整数 $1\leq i \leq A$ に対して $f(X_{i}) \leq f(Y_{i})$ が成り立つ。
全ての整数 $1\leq i \leq B$ に対して $f(Z_{i}) \leq f(W_{i})$ が成り立つ。

値域は全部 $10^{5}$

解説

まず、条件は以下のように書き換えられます。

$f(X_{i}) - f(Y_{i}) \leq 0$
$f(Z_{i}) - f(W_{i}) \leq 1$

これを見ると、答えは以下と同じであることがわかります。

$N$ 頂点のグラフであって、重さが $0$ の $Y_{i} \to X_{i}$ の辺と、重さが $1$ の $W_{i}\to Z_{i}$ の辺が張られたグラフの最長路に $1$ を足した数。ただし、重みの和が正の閉路がある場合は $f$ が存在しない。

これを頑張って判定します。

具体的には、重みが $0$ の辺だけ張ったグラフの強連結成分の数と、全ての辺を張ったグラフの強連結成分の数が一緒かつ、同じ連結成分を結ぶ重み $1$ の辺が存在しなければ良いです。

DAG の最長路は dp で簡単に求まります。

void solve(){
    int N, A, B;
    cin >> N >> A >> B;
    vector<vector<int>> X(2), Y(2);
    X[0].resize(A);
    Y[0].resize(A);
    X[1].resize(B);
    Y[1].resize(B);
    rep(i, 0, A){
        cin >> X[0][i] >> Y[0][i];
        X[0][i]--, Y[0][i]--;
    }
    rep(i, 0, B){
        cin >> X[1][i] >> Y[1][i];
        X[1][i]--, Y[1][i]--;
    }
    atcoder::scc_graph G0(N);
    rep(i, 0, A){
        G0.add_edge(Y[0][i], X[0][i]);
    }
    auto tp = G0.scc();
    vector<int> same(N);
    int M = tp.size();
    rep(i, 0, M){
        for (auto x : tp[i]) same[x] = i;
    }
    rep(i, 0, B){
        if (same[Y[1][i]] == same[X[1][i]]){
            cout << "impossible\n";
            return;
        }
    }
    atcoder::scc_graph G1(N);
    rep(i, 0, B){
        G1.add_edge(Y[1][i], X[1][i]);
    }
    rep(i, 0, A){
        G1.add_edge(Y[0][i], X[0][i]);
    }
    auto tp1 = G1.scc();
    if (tp.size() != tp1.size()){
        cout << "impossible\n";
        return;
    }
    rep(i, 0, M){
        for (auto x : tp1[i]) same[x] = i;
    }
    // vec_out(same);
    // cout << M << endl;
    vector<vector<pair<int, int>>> H(M);
    rep(i, 0, A){
        assert(same[Y[0][i]] <= same[X[0][i]]);
        H[same[Y[0][i]]].push_back({same[X[0][i]], 0});
    }
    rep(i, 0, B){
        assert(same[Y[1][i]] < same[X[1][i]]);
        H[same[Y[1][i]]].push_back({same[X[1][i]], -1});
    }
    vector<ll> dp(M);
    rep(i, 0, M){
        for (auto [to, w] : H[i]){
            chmin(dp[to], dp[i] + w);
        }
    }
    cout << 1 - vec_min(dp) << "\n";
}

終わり

$3$ 位でした。

$7$ 問目で大しくじり

簡単だけど考えさせる問題が多くて、後ろ $3$ 問の理論値は逃してしまいました。