接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > 第二回日本最強プログラマー学生選手権

第二回日本最強プログラマー学生選手権

AtCoderBeginnerContest ABC

atcoder.jp

A - Competition

$ \frac{Y}{X} \gt \frac{i}{Z} $ を満たすような値段 $ i $ が答え
よって分母を払って $ ZY \gt Xi $ を満たす最大の $ i $ を全探索する
提出コード

void solve(){
    int X, Y, Z;
    cin >> X >> Y >> Z;
    int ma = 0;
    REP(i,1010101){
        if(Z * Y > X * i) chmax(ma, i);
    }
    cout << ma << endl;
}

B - Xor of Sequences

$ A_i, B_i $ を $ i $ が $ A, B $ に含まれる個数とすると
$ A _i > 0 $ and $ B_i = 0 $ もしくは $ A_i = 0 $ and $ B_i > 0 $ を満たす $ i $を出力すればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(1010), B(1010);
    REP(i,N){
        int a;
        cin >> a;
        A[a]++;
    }
    REP(i,M){
        int a;
        cin >> a;
        B[a]++;
    }
    vector<int> ans;
    REP(i,1010){
        if(A[i] > 0 and B[i] == 0) ans.emplace_back(i);
        if(B[i] > 0 and A[i] == 0) ans.emplace_back(i);
    }
    sort(ans.begin(), ans.end());
    REP(i,ans.size()) cout << ans[i] << " ";
    cout << endl;
}

C - Max GCD 2

難しい
$ i $ の倍数を考えたときに、 $ i $ の倍数が $ [A, B] $ の区間の中に2個以上存在すればいい
よって、$ 1 \leq i \lt B $ の範囲で $ i $ の倍数が2個以上あるもののなかで最大のものが答え
計算量は調和級数で $ \mathcal{O}(N \log N) $
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    int ma = 0;
    for(int i=1;i<B;i++){
        int cnt = 0;
        for(int j=i;j<=B;j+=i){
            if(A <= j) cnt++;
        }
        if(cnt >= 2) chmax(ma, i);
    }
    cout << ma << endl;
}

D - Nowhere P

$ A_1 $ には $ P - 1 $ 個好きに選べる
$ A_2 $ を考えると $ A_1 + A_2 \neq 0 \pmod P $ を満たせばいい
そのため、$ A_1 + A_2 = 0 \pmod P $ となるようなものは1通りしかなく、それ以降も同様なので $ (P-1)(P-2)^{N-1} $ が答え
提出コード

void solve(){
    int N, P;
    cin >> N >> P;
    cout << mint(P - 1) * modpow(mint(P-2), N-1) << endl;
}

F - Max Matrix

ある一点を変更したときの総和の変化は、その一点の変更による差分で計算できるので、総和を持ちながらクエリを処理したときの差分を計算する
クエリの先読みを行って座圧を行い、$ A, B $ に存在する整数の個数、整数ごとの和をそれぞれセグメント木で管理する
今、$ A_x $ を $ Y $ に変更したとすると$ A_x $ 以上の $ B $ に存在する整数の総和、$ A_x $ 未満の$ B $ に存在する整数の個数 $ cnt \times A_x $が答えから取り除かれる
その後、$ Y $ 以上の $ B $ に存在する整数の総和、$ Y $ 未満の$ B $ に存在する整数の個数 $ cnt \times Y $ が答えに加算される
$ B_x $ を $ Y $ に変更した場合も同様に差分更新を行い、各クエリごとにその答えを出力する
提出コード

void solve(){
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> A(N), B(M);
    Compress<ll> cmp;
    cmp.add(0);
    vector<int> T(Q), X(Q), Y(Q);
    REP(i,Q){
        cin >> T[i] >> X[i] >> Y[i];
        X[i]--;
        cmp.add(Y[i]);
    }
    cmp.build();
    int sz = cmp.size();
    segtree<S, op, e> sum_a(sz), sum_b(sz);
    segtree<S, op, e> cnt_a(sz), cnt_b(sz);
    cnt_a.set(0, N), cnt_b.set(0, M);
    ll ans = 0;
    REP(i,Q){
        int t = T[i], x = X[i], y = Y[i];
        if(t == 1){
            ans -= sum_b.prod(cmp.get(A[x]), sz);
            ans -= cnt_b.prod(0, cmp.get(A[x])) * A[x];
            ll tmp_cnt = cnt_a.get(cmp.get(A[x]));
            cnt_a.set(cmp.get(A[x]), tmp_cnt-1);
            ll tmp_sum = sum_a.get(cmp.get(A[x]));
            sum_a.set(cmp.get(A[x]), tmp_sum - A[x]);
            A[x] = y;
            ans += sum_b.prod(cmp.get(A[x]), sz);
            ans += cnt_b.prod(0, cmp.get(A[x])) * A[x];
            cnt_a.set(cmp.get(A[x]), cnt_a.get(cmp.get(A[x])) + 1);
            sum_a.set(cmp.get(A[x]), sum_a.get(cmp.get(A[x])) + A[x]);
        }
        else{
            ans -= sum_a.prod(cmp.get(B[x]), sz);
            ans -= cnt_a.prod(0, cmp.get(B[x])) * B[x];
            ll tmp_cnt = cnt_b.get(cmp.get(B[x]));
            cnt_b.set(cmp.get(B[x]), tmp_cnt-1);
            ll tmp_sum = sum_b.get(cmp.get(B[x]));
            sum_b.set(cmp.get(B[x]), tmp_sum - B[x]);
            B[x] = y;
            ans += sum_a.prod(cmp.get(B[x]), sz);
            ans += cnt_a.prod(0, cmp.get(B[x])) * B[x];
            cnt_b.set(cmp.get(B[x]), cnt_b.get(cmp.get(B[x])) + 1);
            sum_b.set(cmp.get(B[x]), sum_b.get(cmp.get(B[x])) + B[x]);
        }
        cout << ans << endl;
    }
}