接着剤の精進日記

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

AtCoder Beginner Contest 174(ABC174)

atcoder.jp

A - Air Conditioner

 X \geq 30なら"Yes"、そうでなければ"No"
提出コード

void solve(){
    int X;
    cin >> X;
    if(X >= 30) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Distance

ルートを外してあげてx^2 + y^2 \leq D ^2ならカウントしていく
提出コード

void solve(){
    ll N, D;
    cin >> N >> D;
    int cnt = 0;
    REP(i,N){
        ll x, y;
        cin >> x >> y;
        x *= x, y *= y;
        if(x + y <= D * D) cnt++;
    }
    cout << cnt << endl;
}

C - Repsept

難しい
Kが偶数のときは絶対作れないのでそれ以外を考えてみる
愚直に求めていくことを考えると、割り算の要領で先頭からmodを取っていく
その時、mod K が0になればその桁を出力する
コンテスト中は厳密な証明出来なかったのでK桁目まで見れば十分そうだなーで投げちゃった
解説にちゃんと証明が載っていたので読みます
提出コード

void solve(){
    int K;
    cin >> K;

    int cur = 0;
    REP(i,K+1){
        cur = cur * 10 + 7;
        cur %= K;
        if(cur == 0){
            cout << i + 1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

D - Alter Altar

これも結構考えちゃったんだけど茶色difficultyらしくてびっくり
最終的な状態を考えると、
RR...RWW...W
WW...W
RR...R
のどれかになっていればいい
これを達成するには一番左にあるWと一番右にあるRをswapすることを繰り返していけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> R, W;
    REP(i,N){
        char c;
        cin >> c;
        if(c == 'R') R.emplace_back(i);
        else W.emplace_back(i);
    }
    if(size(R) == 0 or size(W) == 0){
        cout << 0 << endl;
        return;
    }
    sort(R.rbegin(), R.rend());
    int r = 0;
    int ans = 0;
    REP(i, size(W)){
        if(W[i] < R[r]){
            ans++;
            if(size(R) > r) r++;
        }
        if(size(R) == r) break;
    }
    cout << ans << endl;
}

E - Logs

最大値の最小化はにぶたん(素振り)
操作を行った後の丸太の長さの最大値をxにできるかどうか、という判定問題を考える
長さA_iの丸太を長さxで分割していくことを考えると \lceil \frac{A_i}{x} \rceil - 1回切る必要がある
そのため、この合計回数がK回以内なら達成でき、そうでないなら達成できない
あとは、このxについて二分探索をするとこの問題を解くことができる
提出コード

void solve(){
    ll N, K, ma = 0;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i,N){
        cin >> A[i];
        chmax(ma, A[i]);
    }

    auto check = [&](ll x) -> ll{
        if(x == 0) return LINF;
        ll cnt = 0;
        REP(i,N) cnt += (A[i] + x - 1)/ x - 1;
        return cnt;
    };
    ll l = 0, r = ma+1;
    while(r - l > 1){
        ll m = (r + l) >> 1;
        if(check(m) <= K) r = m;
        else l = m;
    }
    cout << l+1 << endl;
}

F - Range Set Query

以下の記事を読んだ記憶があったので「区間 種類数」みたいにググるとHitする
hama-du-competitive.hatenablog.com その後に類題でググってるとけんちょんさんの記事があったのでそれをペタりました
drken1215.hatenablog.com 典型らしいのでちゃんと中身理解しておきたいね
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    vector<int> lefts(Q), rights(Q), ids(Q);
    REP(i,Q){
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+10);
    vector<int> prev(505050, -1);
    vector<int> res(Q);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}