AtCoder Beginner Contest 266（ABC266） - 接着剤の精進日記

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 266での成績：509位
パフォーマンス：1837相当
レーティング：1514→1550 (+36) :)#AtCoder #ABC266 https://t.co/A8vTe2G9vp
— ボンド@競プロ (@bond_cmprog) August 27, 2022

A - Middle Letter

$ S_{ \lfloor \frac{|S|}{2} \rfloor } $ を出力

提出コード

void solve() {
    string S;
    cin >> S;
    int n = S.size();
    cout << S[n / 2] << endl;
}

B - Modulo Number

MOD を取る
MODを取った値が負のときはその値にMODを加算

提出コード

void solve() {
    ll N;
    cin >> N;
    N %= MOD2;
    if (N < 0) N += MOD2;
    cout << N << endl;
}

C - Convex Quadrilateral

内角を作る頂点の3つ組すべてに対して、外積を求める
外積の正負によって判定を行う

提出コード

void solve() {
    vector<int> x(4), y(4);
    REP(i, 4) cin >> x[i] >> y[i];
    bool ok = true;
    REP(i, 4) {
        int j = (i + 1) % 4;
        int k = (i + 2) % 4;
        int ax = x[i] - x[j];
        int bx = x[k] - x[j];
        int ay = y[i] - y[j];
        int by = y[k] - y[j];
        double ang = bx * ay - by * ax;
        if (ang < 0) ok = false;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

D - Snuke Panic (1D)

$ dp[i][j] : = $ 時刻 $ i $ に座標 $ j $ にいるとき、捕まえた数が最大となる値、としてDPを行う

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> T(N), X(N), A(N);
    REP(i, N) cin >> T[i] >> X[i] >> A[i];
    vector<int> spot(101020, -1);
    REP(i, N) spot[T[i]] = i;
    vector dp(101020, vector(5, -1LL));
    dp[0][0] = 0;
    REP(i, 101010) {
        REP(j, 5) {
            for (int k = -1; k <= 1; k++)
                if (dp[i][j] != -1) {
                    int nj = j + k;
                    int idx = spot[i + 1];
                    if (nj >= 5 or nj < 0) continue;
                    if (idx >= 0 and X[idx] == nj) chmax(dp[i + 1][nj], dp[i][j] + A[idx]);
                    else chmax(dp[i + 1][nj], dp[i][j]);
                }
        }
    }
    cout << *max_element(ALL(dp[101010])) << endl;
}

E - Throwing the Die

$ dp[i][j] := i $ 回ダイスを振り、今出ている目が $ j $ のときのスコアの期待値の最大としてDPを行う
今出ている目が、次に降ったときの期待値より大きい場合はゲームを終了し、そうでないならばダイスを降ればいいので、 $ dp[i][j] = \max(j, \frac{\sum_{j=1} ^ 6 dp[i+1][j]}{6}) $ としてメモ化再帰で求める

提出コード

void solve() {
    int N;
    cin >> N;
    vector dp(N + 1, vector<double>(7, 0.0));
    auto memo = [&](auto &&self, int n, int x) -> double {
        if (n == N) {
            dp[n][x] = x;
            return x;
        }
        if (dp[n][x] > 0.0) return dp[n][x];
        auto &res = dp[n][x];
        double expect = 0.0;
        REP(j, 1, 7) {
            auto nxt = self(self, n + 1, j);
            expect += nxt;
        }
        expect /= 6.0;
        if (expect < (double)x) res = x;
        else res = expect;
        return res;
    };
    printf("%.12lf\n", memo(memo, 0, 0));
}

F - Well-defined Path Queries on a Namori

$ N $ 頂点 $ N $ 辺な連結無向グラフなので1つのサイクルに毛が生えたグラフになる
サイクルのどの頂点から毛が生えているかでグループ分けをすると、同じグループ間はパスが1通り、異なるグループ間はサイクルを右回り・左回りのどちらを通るかでパスが2通りできる
そのため、各頂点のグループを求めておき、クエリの頂点が同じグループかどうかを判定すればいい

提出コード

void solve() {
    ll n;
    cin >> n;
    vector<vector<int>> g(n);
    REP(i, n) {
        int u, v;
        cin >> u >> v;
        g[--u].emplace_back(--v);
        g[v].emplace_back(u);
    }
    vector<int> v;
    int pos = -1;
    vector<bool> seen(n), finished(n);
    auto dfs = [&](auto &&self, int cur, int par = -1) {
        seen[cur] = true;
        v.emplace_back(cur);
        for (auto nv : g[cur]) {
            if (nv == par) continue;
            if (finished[nv]) continue;
            if (seen[nv] and !finished[nv]) {
                pos = nv;
                return;
            }
            self(self, nv, cur);
            if (pos != -1) return;
        }
        v.pop_back();
        finished[cur] = true;
    };
    dfs(dfs, 0);
    vector<ll> cnt(n);
    queue<tuple<int, int, int>> q;
    vector<bool> used(n);
    set<int> cycle;
    while (!v.empty()) {
        int cur = v.back();
        cycle.insert(cur);
        v.pop_back();
        if (cur == pos) break;
    }
    for (auto x : cycle) {
        q.emplace(x, -1, x);
        used[x] = true;
    }
    vector<int> groups(n);
    while (!q.empty()) {
        auto [cur, par, group] = q.front();
        q.pop();
        cnt[group]++;
        groups[cur] = group;
        for (auto nv : g[cur]) {
            if (nv == par) continue;
            if (used[nv]) continue;
            q.emplace(nv, cur, group);
        }
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        cout << (groups[u] == groups[v] ? "Yes" : "No") << endl;
    }
}