AtCoder Beginner Contest 228（ABC228）

atcoder.jp

Bondo416さんのトヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)での成績：745位
パフォーマンス：1601相当
レーティング：1458→1473 (+15) :)#AtCoder #トヨタシステムズプログラミングコンテスト2021(ABC228) https://t.co/66qqTVbYtD

— ボンド@競プロ (@bond_cmprog) November 20, 2021

A - On and Off

ループを回してチェックする

提出コード

void solve(){
    int S, T, X;
    cin >> S >> T >> X;
    for(int i=S;;i++){
        if(i == 24) i = 0;
        if(i == T){
            break;
        }
        if(i == X){
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

B - Takahashi's Secret

有向グラフで考えて、$ X $ を始点としてBFSなどで辿り着ける頂点の個数を数える

提出コード

void solve(){
    int N, X;
    cin >> N >> X;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<vector<int>> G(N);
    REP(i,N){
        G[i].emplace_back(A[i]-1);
    }
    queue<int> q;
    q.emplace(X-1);
    vector<int> used(N);
    while(!q.empty()){
        int v = q.front(); q.pop();
        if(used[v]) continue;
        used[v] = 1;
        for(auto nv : G[v]){
            q.emplace(nv);
        }
    }
    cout << accumulate(ALL(used), 0) << endl;
}

C - Final Day

4日目では、$ i $ 番目の人が $ 300 $ 点、それ以外の人が$ 0 $ 点を取ると考えていい
$ sum_i = P_{i,0} + P_{i,1} + P_{i,2} $ とすると、$ sum_i + 300 $ が $ sum $ の中で上から $ K $ 番以内に入っていればいい
BITなどで各点数の人の人数を管理し、$ K $ 番目の値を二分探索で求めればいい

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<vector<int>> P(N, vector<int>(3));
    vector<int> sum(N);
    BIT<int> bit(1222);
    REP(i,N){
        REP(j,3) cin >> P[i][j];
        sum[i] = P[i][0] + P[i][1] + P[i][2];
        bit.add(sum[i], 1);
    }
    REP(i,N){
        bit.add(sum[i], -1);
        int idx = bit.kth_element(N - K - 1) - 1;
        if(sum[i] + 300 >= idx) cout << "Yes" << endl;
        else cout << "No" << endl;
        // dump(idx);
        bit.add(sum[i], 1);
    }
}

D - Linear Probing

$ A_i \neq -1 $ である区間をsetで管理する
$ A_{N - 1} \neq -1 $ であるときの処理に気をつける

提出コード

void solve(){
    const ll N = 1LL << 20;
    int Q;
    cin >> Q;
    vector<ll> A(2*N, -1);
    RangeSet<ll> st;
    while(Q--){
        ll q, x;
        cin >> q >> x;
        ll mod_x = x % N;
        auto [l, r] = st.covered_by(mod_x);
        if(q == 1){
            if(l < 0){
                A[mod_x] = x;
                st.insert(mod_x);
            }
            else{
                if(r == N - 1){
                    auto [_l, _r] = st.covered_by(0);
                    if(_l < 0){
                        A[0] = x;
                        st.insert(0);
                    }
                    else{
                        A[_r+1] = x;
                        st.insert(_r+1);
                    }
                }
                else{
                    A[r+1] = x;
                    st.insert(r+1);
                }
            }
        }
        else{
            cout << A[mod_x] << endl;
        }
    }
}

E - Integer Sequence Fair

$ M ^ {K ^ N} $ を求めればいいが、modを取ると色々罠がある
フェルマーの小定理より $ M ^ {K ^ N} \pmod P = M ^ {K ^ N \pmod { P -1 } } \pmod P $ となる
実装によっては $ 0 ^ 0 = 1 $ になる場合があるが、実際には $ 0 $ を出力しないといけないので注意する
他にもオーバーフローしたりするので予めmodを取っておく

提出コード

void solve(){
    ll N, K, M;
    cin >> N >> K >> M;
    M %= MOD2;
    K %= (MOD2 - 1);
    cout << mod_pow(M, mod_pow(K, N, MOD2-1) + MOD2 - 1, MOD2) << endl;
}