AtCoder Beginner Contest 242（ABC242）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 242での成績：1259位
パフォーマンス：1389相当
レーティング：1556→1541 (-15) :(#AtCoder #ABC242 https://t.co/cHfqhJVXU7

— ボンド@競プロ (@bond_cmprog) March 5, 2022

A - T-shirt

$$ \left\{ \begin{array}{} 1 & (X \leq A) \\ \frac{C}{B - A} & (X \leq B) \\ 0 & else \end{array} \right. $$

提出コード

void solve(){
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    double ans = 0;
    if(X <= A) ans = 1.0;
    else if(X <= B) ans = (double)C / (B - (A+1) + 1);
    else ans = 0;
    printf("%.12lf\n",ans);
}

B - Minimize Ordering

文字列をソートする

提出コード

void solve(){
    string S;
    cin >> S;
    sort(ALL(S));
    cout << S << endl;
}

C - 1111gal password

$ DP[i][j] = i $ 番目まで見た時に末尾の数字が $ j $ のときの場合の数としてDPをする

提出コード

void solve(){
    int N;
    cin >> N;
    vector<mint> dp(10);
    REP(i,1,10) dp[i] = 1;
    REP(_,N-1){
        vector<mint> nxt(10);
        REP(i,1,10){
            REP(j,1,10){
                if(abs(i - j) <= 1) nxt[j] += dp[i];
            }
        }
        swap(dp, nxt);
    }
    cout << accumulate(ALL(dp), mint(0)) << endl;
}

D - ABC Transform

$ S^{(t)} $ の $ k $ 文字目を返す関数を $ f(t, k) $ とする
$ t = 0 $ のとき $ S^{(0)}_k $
$ k = 0 $ のとき $ S^{(0)}_0 $ を $ t $ だけ進めた文字（A -> B -> C -> A-> ...)
それ以外のとき、$ f(t, k) $ は $ f(t-1, \frac{k}{2}) $ を $ k \% 2 + 1 $ だけ進めた文字として再帰関数で求める

提出コード

void solve(){
    string S;
    cin >> S;
    int Q;
    cin >> Q;

    auto g = [&](char c, ll k) -> char{
        return char((c - 'A' + k) % 3 + 'A');
    };

    auto f = [&](auto &&self, ll t, ll k) -> char{
        if(t == 0) return S[k];
        if(k == 0) return g(S[0], t);
        return g(self(self, t-1, k/2), k%2+1);
    };

    while(Q--){
        ll t, k;
        cin >> t >> k;
        cout << f(f, t, k-1) << endl;
    }
}

E - (∀x∀)

$ S $ を長さ $ \lceil \frac{N}{2} \rceil $ までの文字列として桁DPをする

提出コード

void solve(){
    int N;
    string S;
    cin >> N >> S;
    string T = S;
    reverse(ALL(T));
    REP(i,N/2) T[i] = S[i];
    vector dp(N+1, vector<mint>(2));
    dp[0][0] = 1;
    REP(i,ceil_div(N,2)) REP(j,2){
        for(char c='A';c<=(j ? 'Z' : S[i]);c++){
            dp[i+1][j or (c < S[i])] += dp[i][j];
        }
    }

    cout << dp[ceil_div(N,2)][1] + (T <= S) << endl;
}

G - Range Pairing Query

Mo’s algorithmが使える
区間を伸ばした時に、$ A_i $ の個数が奇数から偶数になるとき、その区間の答えが1加算され、逆に区間を縮小したときに $ A_i $ の個数が偶数から奇数になるときその区間の答えが1減る

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    int Q;
    cin >> Q;
    vector<int> ans(Q);
    vector<int> cnt(N);
    int num = 0;
    auto add = [&](int idx){
        if(cnt[A[idx]]++ % 2 == 1) num++;
    };
    auto erase = [&](int idx){
        if(--cnt[A[idx]] % 2 == 1) num--;
    };
    auto out = [&](int idx){
        ans[idx] = num;
    };
    Mo mo(N);
    REP(i,Q){
        int l, r;
        cin >> l >> r;
        mo.add(--l, r);
    }
    mo.build(add, erase, out);
    for(auto x : ans) cout << x << '\n';
}