AtCoder Beginner Contest 174 ABC174 参加記

Eまでノーペナ30分だったのにF既出を検索できずにしょっぱいパフォを取ってしまいました。もったいなかったです。

jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 174での成績：1161位
パフォーマンス：1476相当
レーティング：1307→1325 (+18) :)#AtCoder #ABC174 https://t.co/94Y1w9iGl9

— naga@精進 (@longeqe) 2020年8月2日

目次

A - Air Conditioner

問題へのリンク

解説

if文を使います。C++では以下のような書き方でifを使わずに書くことができます。

実装

int main() {
    int N;
    cin >> N;
    cout << ((N >= 30) ? "Yes" :"No") << endl;
}

B - Distance

問題へのリンク

解説

ルートは外して整数で考えましょう。intだとオーバーフローするので、long longを使いましょう。

実装

int main() {
    ll N, D;
    cin >> N >> D;
    ll ans = 0;
    rep(i,N){
        ll x, y;
        cin >> x >> y;
        ans += (x*x+y*y) <= D*D;
    }
    cout << ans << endl;
}

C - Repsept

問題へのリンク

解説

modは、基本的に桁ごとにみていいです。 これ説明難しいです、エスパーして大きめに回すと解を得ます。

実装

int main() {

    ll K;
    cin >> K;
    vector<ll> v(10*K);
    v[0] = 0;
    rep(i,10*K){
        v[i+1] = (v[i]*10 % K) + 7;
        v[i+1] %= K;
        if(v[i+1] == 0){
            cout << i+1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

D - Alter Altar

問題へのリンク

解説

Rを左に寄せれば良いので、まず既存のRの個数を計算し、先頭から長さの中にあると右にあるをswapすることを考えれば良いです。これが操作回数の最小値です。

実装

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    ll cntr = 0;
    rep(i,N)cntr += S[i] == 'R';
    ll ans = 0;
    rep(i,cntr)ans += S[i] == 'W';
    cout << ans << endl;
}

E - Logs

問題へのリンク

解説

最大値の最小化問題なので、二分探索をしたくなります。いわゆる決めうち二分探索です。全てを以下にするために必要な操作回数をで求めることができれば、全体の計算量がになります。

長さを以下の長さに分けるのに必要な回数は、（切り上げ）です。

実装

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N)cin >> A[i];
    sort(all(A));
    auto check = [&](ll X) -> bool{
        ll cnt = 0;
        rep(i,N)cnt += (A[i] + X - 1) / X;
        return cnt-N <= K;
    };
    ll ng = 0;
    ll ok = A[N-1];
    while(ok - ng > 1){
        ll mid = (ok + ng) >> 1;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

F - Range Set Query

問題へのリンク

感想

既出臭がプンプンするのでぐぐると出てくるようです。私は英語でググっていたので全くヒットしませんでした。