AtCoder Beginner Contest 234（ABC234）

atcoder.jp

highestらしい
Bondo416さんのAtCoder Beginner Contest 234での成績：421位
パフォーマンス：1899相当
レーティング：1526→1569 (+43) :)
Highestを更新しました！#AtCoder #ABC234 https://t.co/ERIzNwvlNI

— ボンド@競プロ (@bond_cmprog) January 8, 2022

A - Weird Function

関数をそのまま実装する

提出コード

void solve(){
    ll t;
    cin >> t;
    auto f = [&](ll t) ->ll{
        return t*t + 2*t + 3;
    };
    cout << f(f(f(t) + t) + f(f(t))) << endl;
}

B - Longest Segment

二点間の距離を全探索する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<double> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    double ma = 0;
    REP(i,N) REP(j,i+1,N){
        chmax(ma, hypot(x[i] - x[j], y[i] - y[j]));
    }
    printf("%.12lf\n", ma);
}

C - Happy New Year!

2進数を求めたあと、1を2に置き換えて出力する

提出コード

void solve(){
    ll K;
    cin >> K;
    string ans = "";
    while(K > 0){
        ans += char(K % 2 + '0');
        K /= 2;
    }
    reverse(ALL(ans));
    for(char c : ans) cout << (c == '0' ? c : '2');
    cout << endl;
}

D - Prefix K-th Max

BITで二分探索をする

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> P(N);
    REP(i,N) cin >> P[i];
    BIT<int> bit(N+10);
    REP(i,K) bit.add(P[i], 1);
    REP(i,K,N){
        cout << bit.kth_element(i - K) - 1 << endl;
        bit.add(P[i], 1);
    }
    cout << bit.kth_element(N - K) - 1 << endl;
}

E - Arithmetic Number

あり得る等差数は少ないので全列挙をしたあと二分探索で求める

提出コード

void solve(){
    ll X;
    cin >> X;
    vector<ll> tousa;
    REP(i,1,10){// 初項
        REP(j,-9, 10){// 等差
            ll cur = i;
            ll digit = i;
            tousa.emplace_back(cur);
            REP(k,17){// 個数
                int nxt = digit + j;
                if(nxt < 0 or nxt > 9) break;
                cur = 10 * cur + nxt;
                digit = nxt;
                tousa.emplace_back(cur);
            }
        }
    }
    sort(ALL(tousa));
    cout << *lower_bound(ALL(tousa), X) << endl;
}

F - Reordering

$ dp[i][j] := i $ 番目のアルファベットまでを使って、長さ$ j $ の部分列を作ったときの並べ方の総数としてDP をする

提出コード

void solve(){
    string S;
    cin >> S;
    int N = S.size();
    bc.init(5050);
    vector<ll> cnt(27);
    REP(i,N) cnt[S[i]-'a']++;
    vector dp(27, vector<mint>(N+10));
    dp[0][0] = 1;
    REP(i,26){
        REP(j,N+1){
            REP(k,min(cnt[i], j)+1){
                dp[i+1][j] += dp[i][j-k] * bc.nCr(j, k);
            }
        }
    }
    mint ans = 0;
    REP(i,N) ans += dp[26][i+1];
    cout << ans << endl;
}