ABC 411

Table of Contents

https://atcoder.jp/contests/abc411

A. Required Length

https://atcoder.jp/contests/abc411/tasks/abc411_a

取り込んだ文字列が $L$ 文字以上か判定するだけ

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string P;
    int L;
    cin >> P >> L;
    yesno((int)P.size() >= L);
}

B. Distance Table

https://atcoder.jp/contests/abc411/tasks/abc411_b

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll D(N);
    rep2(i, 1, N) cin >> D[i];

    rep(i, N) {
        ll sum = 0;
        vll ans;
        rep2(j, i + 1, N) {
            sum += D[j];
            ans.push_back(sum);
        }
        print(ans);
    }
}

C. Black Intervals

https://atcoder.jp/contests/abc411/tasks/abc411_c

簡単のためにマスの両端に白マスを追加する。 更新するマスとの両隣含めた3つのマスの状態によって黒の区間を数を更新する。

更新するマスは真ん中のマスとする。また黒を B, 白を W とする。

$i-1$ 番目と $i+1$ 番目のマスの色が違う場合は $i$ 番目のマスが何色であっても黒区間の数は変わらない。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    int ans = 0;
    vint grid(N + 2);
    rep(_, Q) {
        int a;
        cin >> a;
        if (grid[a] == 0) {
            grid[a] = 1;
            if (grid[a - 1] == 1 && grid[a + 1] == 1) {
                ans--;
            }
            if (grid[a - 1] == 0 && grid[a + 1] == 0) {
                ans++;
            }
        } else {  // grid[a] = 1
            grid[a] = 0;
            if (grid[a - 1] == 1 && grid[a + 1] == 1) {
                ans++;
            }
            if (grid[a - 1] == 0 && grid[a + 1] == 0) {
                ans--;
            }
        }
        cout << ans << '\n';
    }
}

D. Conflict 2

https://atcoder.jp/contests/abc411/tasks/abc411_d

空文字列を保持するノードを根として木を構築していく。 各ノードには親ノードの番号とそのノードが持つ文字列を保持する。

はじめ全ての server, PC は根を指す。 type 2 のクエリでは現在 PC $p$ のノードを親とし、文字列 $s$ をもつ新しいノードを作成する。 type 1, 3 ではそれぞれ指すノードを変更する。

間隔としては 競プロフレンズ氏の図がわかりやすい

ref: https://x.com/kyopro_friends/status/1936428711584346216

struct Node {
    int id, parent;
    string data;

    Node() {
        id = 0;
        parent = -1;
        data = "";
    }

    Node(int id, int parent, string data) : id(id), parent(parent), data(data) {}
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;

    // node[0] は server
    vector<Node> nodes(N + 1), tree(1);

    rep(i, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            int p;
            cin >> p;
            nodes[p] = nodes[0];
        }
        if (t == 2) {
            int p;
            string s;
            cin >> p >> s;
            Node node(tree.size(), nodes[p].id, s);
            tree.push_back(node);
            nodes[p] = node;
        }
        if (t == 3) {
            int p;
            cin >> p;
            nodes[0] = nodes[p];
        }
    }

    string ans = "";
    Node node = nodes[0];
    while (node.parent != -1) {
        string s = node.data;
        reverse(all(s));
        ans += s;
        node = tree[node.parent];
    }
    reverse(all(ans));
    cout << ans << endl;
}

E. E [max]

https://atcoder.jp/contests/abc411/tasks/abc411_e

F. Contraction

https://atcoder.jp/contests/abc411/tasks/abc411_f

G. Count Cycles

https://atcoder.jp/contests/abc411/tasks/abc411_g