ABC 247

Table of Contents

A - Move Right

問題

$0 s_0 s_1 s_2$ を出力すればよい

void solve() {
    string s;
    cin >> s;
    cout << 0 << s.substr(0, 3) << endl;
}

提出コード

B - Unique Nicknames

人 $i$ について, 次の条件 $P$, $Q$ のうちいずれかが成り立っていればその人にあだ名をつけることは可能である.

これが全ての人に対して調べる.

void solve() {
    int n;
    cin >> n;
    vector<string> S(n), T(n);
    rep(i, n) cin >> S[i] >> T[i];

    rep(i, n) {
        int ok = 1;
        rep(j, n) {
            if (i == j)
                continue;
            if (S[i] == S[j] || S[i] == T[j])
                ok = 0;
        }
        if (ok)
            continue;

        ok = 1;
        rep(j, n) {
            if (i == j)
                continue;
            if (T[i] == S[j] || T[i] == T[j])
                ok = 0;
        }
        if (!ok) {
            cout << "No" << endl;
            return;
        }
    }

    cout << "Yes" << endl;
}

提出コード

C - 1 2 1 3 1 2 1

$S_i$ の長さを $L_i$ とすると $L_i = 2L_{i - 1} + 1$ となる. $i = 16$ のときでもおおよそ長さは $2^i$ くらい. $1 \sim N$ まで全ての要素数を列挙すると $\sum_{i=0}^N 2^i = O(2^N)$ となるので $N = 16$ ならば $2^16 = 65536$ なので TLE も MLE も特に気にしなくて良い.

$S_i$ の配列は $S_{i-1} + i + S_{i-1}$ を地道に構成すれば良い.

void solve() {
    int n;
    cin >> n;
    vvint S(n + 1);
    S[1].push_back(1);
    rep2(i, 2, n + 1) {
        S[i].insert(S[i].end(), all(S[i - 1]));
        S[i].push_back(i);
        S[i].insert(S[i].end(), all(S[i - 1]));
    }

    print(S[n]);
}

提出コード

D - Cylinder

問題

deque に数字 $x$ が $c$ 個連続しているという情報を $(x, c)$ として保存していく.

void solve() {
    int q;
    cin >> q;
    deque<P> deq;

    rep(i, q) {
        int t;
        cin >> t;
        if (t == 1) {
            ll x, c;
            cin >> x >> c;
            if (deq.empty()) {
                deq.push_back({x, c});
                continue;
            }
            auto [X, C] = deq.back();
            deq.pop_back();
            if (X == x) {
                deq.push_back({x, c + C});
            } else {
                deq.push_back({X, C});
                deq.push_back({x, c});
            }
        } else {
            ll ans = 0;
            ll c;
            cin >> c;
            while (c) {
                auto [X, C] = deq.front();
                deq.pop_front();

                ll mn = min(c, C);
                ans += X * mn;
                C -= mn;
                c -= mn;

                if (C != 0)
                    deq.push_front({X, C});
            }
            cout << ans << endl;
        }
    }
}

E - Max Min

$L$ を固定して, 条件を満たす $R$ を探すことを考える.

最小値が $Y$ となる一番右端の index を $R_i$, 最大値が $X$ となる一番右端の index を $R_j$ とすると $R$ の最大値は $R_{\mathrm{max}} = \min(R_i, R_j)$ となる.

最小値が $Y$ となる一番左端の index を $R_m$, 最大値が $X$ となる一番左端の index を $R_n$ とすると $R$ の最小値は $R_{\mathrm{min}} = \max(R_m, R_n)$ となる.

$R \in [ R_{\mathrm{min}}, R_{\mathrm{max}} ]$ のとき条件を満たすから $L$ を固定したときの $R$ の 場合の数は $R_{\mathrm{max}} - R_{\mathrm{min}} + 1$ となる.

問題は $R_{\mathrm{max}}$, $R_{\mathrm{min}}$ をどうやって高速に求めるかだが, これは segment tree で二部探索すると高速に求めることができる.

ll opmin(ll a, ll b) {
    return min(a, b);
}

ll emin() {
    return (ll)(1e9);
}

ll opmax(ll a, ll b) {
    return max(a, b);
}

ll emax() {
    return -1;
}

ll target_max;
ll target_min;

bool fmax(ll v) {
    return v <= target_max;
}

bool fmin(ll v) {
    return v >= target_min;
}

bool gmax(ll v) {
    return v < target_max;
}

bool gmin(ll v) {
    return v > target_min;
}

void solve() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    vll A(N);
    rep(i, N) cin >> A[i];

    target_max = X;
    target_min = Y;

    segtree<ll, opmin, emin> minseg(A);
    segtree<ll, opmax, emax> maxseg(A);

    ll ans = 0;
    rep(i, N) {
        // 区間最大値が X, 区間最小値が Y となるような i 以上の最大の座標
        ll x = min(minseg.max_right<fmin>(i), maxseg.max_right<fmax>(i));
        // 区間最大値が X, 区間最小値が Y となるような i 以上の最小の座標
        ll y = max(minseg.max_right<gmin>(i), maxseg.max_right<gmax>(i));
        if (x > y)
            ans += x - y;
    }
    cout << ans << endl;
}

提出コード