AtCoder Beginner Contest 238（ABC238）

atcoder.jp

Bondo416さんのモノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）での成績：2117位
パフォーマンス：1076相当
レーティング：1590→1548 (-42) :(#AtCoder #モノグサプログラミングコンテスト2022（ABC238） https://t.co/hrF1qjAoc3

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

A - Exponential or Quadratic

$ n \geq 60 $ のとき、必ず成り立つので $ n = \min(n, 60) $ として比較を行う

提出コード

void solve(){
    ll n;
    cin >> n;
    ll N = n * n;
    ll two = 1LL << (min(n, 60LL));
    if(two > N) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Pizza

実際に切れ込みの入る位置を求めたあと、その間の角度の最大を求める

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    set<int> st;
    int cur = 0;
    st.insert(0);
    st.insert(360);
    REP(i,N){
        cur += A[i];
        cur %= 360;
        st.insert(cur);
    }
    int dir = 0;
    int ans = 0;
    for(auto x : st){
        chmax(ans, x - cur);
        cur = x;
    }
    cout << ans << endl;
}

C - digitnum

$ i $ 桁の数字ごとに分けて考える
それぞれの桁数ごとで考えると、その和は等差数列になるのでその総和が答え

提出コード

void solve(){
    ll N;
    cin >> N;
    ll cur = 9;
    ll pre = 1;
    mint ans = 0;
    REP(i,18){
        if(N <= cur){
            cur = N;
        }
        mint n = cur - pre + 1;
        ans += n * (n + 1) / 2;
        if(N <= cur) break;
        cur = 10 * cur + 9;
        pre *= 10;
    }
    cout << ans << endl;
}

D - AND and SUM

$ x + y = 2(x \& y) + x \oplus y $ であるので、$ s - 2a = x \oplus y $ となりこれを満たす $ (x, y) $ が存在すればいい
これは $ s - 2a \geq 0 $ かつ $ (s - 2a) \& a = 0 $ を満たせばいい

提出コード

void solve(){
    ll a, s;
    cin >> a >> s;
    ll n = s - 2 * a;
    if(n >= 0 and (n & a) == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

E - Range Sums

$ a $ の累積和 $ b $ を考える
各クエリは $ b_{r} - b_{l - 1} $ と言い換えることができ、片方がわかっていればもう片方の値もわかるのでこの二頂点を連結にするとクエリと考える
そうすると、$ b $ の要素を頂点として考えると、$ b_0 $ から $ b_N $ にたどり着ければ良いことになる
よって各クエリに対してUnionFindなどで頂点を連結させ、$ b_0 $ と $ b_N $ が連結かどうかを判定すればいい

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    UnionFind uf(N+1);
    REP(i,Q){
        int l, r;
        cin >> l >> r;
        uf.unite(--l, r);
    }
    cout << (uf.issame(0, N) ? "Yes" : "No") << endl;
}

F - Two Exams

$ dp[i][j][k] := i $ 番目まで見た時に、$ j $ 人選び、選んでいない人の中で最小の順位が $ k $ のときの選び方の場合の数としてDPを行う

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> P(N), Q(N);
    REP(i,N){
        cin >> P[i];
        --P[i];
    }
    REP(i,N){
        cin >> Q[i];
        --Q[i];
    }
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int a, int b){
        return P[a] < P[b];
    });
    vector dp(K+10, vector<mint>(N+10));
    dp[0][N] = 1;
    for(auto i : idx){
        vector nxt(K+10, vector<mint>(N+10));
        REP(x,K+1) REP(y,N+1){
            if(Q[i] < y) nxt[x+1][y] += dp[x][y];
            nxt[x][min(y, (ll)Q[i])] += dp[x][y];
        }
        swap(nxt, dp);
    }
    mint ans = 0;
    REP(i,N+1) ans += dp[K][i];
    cout << ans << endl;
}