AtCoder Beginner Contest 174 - zeronosu77108’s blog

はい． AtCoder Beginner Contest 174 です
ABC149 からブログ書いていなかった見たいです…

E問題は無限にバグらせて驚愕の21ペナでした。

f:id:zeronosu77108:20200806004758p:plain

ただ、なんとか水色に戻ることが出来ました。 +3 でぴったし 1200 になりました。

A - Air Conditioner

30以上かどうか判定して Yes/No を出力します。

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

B - Distance

問題文

原点からの距離を求める問題です。 sqrt の計算しても良かったのですが、 hypot() を使いました。

int main() {
    int n,d;
    cin >> n >> d;

    int ans = 0;
    for (int i=0; i<n; i++) {
        int x,y;
        cin >> x >> y;
        if (hypot(x,y) <= d) ans++;
    }
    cout << ans << endl;
}

C - Repsept

問題文

7,77,777,… という数列の何番目に K の倍数が登場するかという問題。サンプル2から K が 2の倍数であると現れないことが分かり、サンプル3は最大値っぽい値だったので雑に全探索すれば良いなというお気持ちになりました。

解説を読むと等比数列の和から式が整理できて、2の倍数または5の倍数以外では解が存在し、全探索しても間に合うようです。

int main() {
    int k;
    cin >> k;

    if (k%2 == 0) {
        cout << -1 << endl;
        return 0;
    }

    int i = 7;
    int ans = 1;
    while(i != 0) {
        if (i%k == 0) break;
        i %= k;
        i *= 10;
        i += 7;
        ans++;
        if (ans > 1000000) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
}

D - Alter Altar

問題文

最初は、「前から "WR" の所を "RR" にするやつと、後ろから "WW" にするやつを書いて小さい方！」とか思って考えていたのですが、よく考えたら一番最初に出てくる 'W' と一番後ろの 'R' を入れ替える操作を災いが起きなくなるまでやれば操作回数が少なくなることが分かりました。

そこで、'W' と 'R' を数えて、 'R' の個数から既に手前にある'R' の個数を引いてあげると答えが出ます。

int main() {
    int n;
    string s;
    cin >> n >> s;

    map<char,int> mp;
    for (int i=0; i<n; i++) mp[s[i]]++;

    int cnt = count(s.begin(), s.begin() + mp['R'], 'R');
    cout << mp['R'] - cnt << endl;
}

E - Logs

問題文

バグり散らかしました。最初 priority_queue を使って大きい奴を半分にしていくのかと思ったのですが、問題をよく読んだら一番長い丸太の長さを最小化したいという問題だったので、二分探索かとすぐ思いつきました（長さを i 以下にしたいときそれで割れば切る回数が分かるので）。

最初の提出で 2ケース以外は通っていたのですが、 t += a[i] / m; の部分が本当はダメで、 (a[i] -1 ) / m などをするべきでした。例えば長さ12 の丸太を長さ3 以下に切り分けたい場合は、 12/3 で 4回の切断ではなく、3回の切断で済むのでその分を減らしてあげる必要があります。それに気付くのにとても時間がかかりました。気付いて if (a[i] % m == 0) t—; を入れたら通りました。次からはこういうミスがないように何回切るとか丁寧に考えたいです_(:3」∠)_

int main() {
    int64 n,k;
    cin >> n >> k;
    vector<int64> a(n);
    for (int i=0; i<n; i++) cin >> a[i];


    int64 l = 0;
    int64 r = a[0];
    for (int i=1; i<n; i++) r=max(r,a[i]);

    while(l+1 < r) {
        int64 m = (l+r)/2;

        int64 t = 0;
        for (int i=0; i<n; i++) {
            t += a[i] / m;
            if (a[i] % m == 0) t--;
            if (t > k) break;
        }

        if (t <= k) r = m;
        else l = m;
    }
    cout << r << endl;
}