AtCoder Beginner Contest 172 ABC172 参加記

72分5完2ペナで青パフォでした。数え上げを少し練習してたのがよかったんだと思います。

C - Tsundoku

解説

令和ABC-Cなのでとで小さい方を取っていく貪欲解を考えますが、すぐに反例が見つけられます。下にたくさん小さいものがあるときにそちらに到達できない場合です。よって全探索したくなります。

で境界を全探索すると間に合いません。 ここで、冊数の最大値を求める問題なので、単調性があることを考えます。冊数を二分探索します。冊数の解の範囲はなので、その間を二分探索します。ここにかかる計算量はです。

全体で読む冊数を決めたら、それをとに振り分け方を全探索できます。から冊読むとしたら、からは冊読むことになるので、それにかかる計算量は累積和の前処理によりになります。 全体ででこの問題を解くことができます。

以上のように解を決めうって二分探索する手法を俗に「解決めうち二分探索」と呼びます（少なくとも私は）。

実装

int main() {

    ll N, M, K;
    cin >> N >> M >> K;
    vector<ll> A(N),B(M);
    rep(i, N)cin >> A[i];
    rep(i, M)cin >> B[i];
    vector<ll> cumA(N+1,0);
    vector<ll> cumB(M+1,0);
    rep(i,N)cumA[i+1] = cumA[i] + A[i];
    rep(i,M)cumB[i+1] = cumB[i] + B[i];
    //X冊読むとしたときにK分以内にできるか(O(N));
    auto check = [&](ll X){
        ll minn = INFLL;
        rep(i,N+1){
            ll j = X - i;
            if(j > M)continue;
            if(j < 0)continue;
            chmin(minn, cumA[i] + cumB[j]);
        }
        return minn <= K;
    };
    //めぐる式二分探索
    ll ok = 0;
    ll ng = N+M+1;
    while(ng - ok > 1){
        ll mid = (ok + ng) >> 1;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

D - Sum of Divisors

解説

整数の約数の個数は、素因数分解をすることででできますが、今回はそれでは間に合いません。約数の個数を約数視点で数える方法として、計算量が調和級数となる方法が存在するので、それを行うことでになりギリギリ間に合います。今回はTLが3 secなので。

実装

int main() {
    ll N;
    cin >> N;
    vector<ll> v(N+1,0);
    for(int j = 1; j <= N; j++){
        for(int k = j; k <= N; k+= j){
            v[k]++;
        }
    }
    ll ans = 0;
    for(ll i = 1; i <= N; i++){
        ans += i * v[i];
    }
    cout << ans << endl;
}   

E - NEQ

包除原理を使います。詳しく書くと長くなりそうなので記事を分けたいと思います。

-> わけました

coonevo.hatenablog.com

F - Unfair Nim

Nimの事前知識が必要な問題でした。勉強してからもう一度考えたいと思います。