AtCoder Beginner Contest 117

競技プログラミング

全体

　55分(1WA)で全完の222位。D問題が解けなさ過ぎて気持ちは冷えていたし身体は熱くなっていた。400点問題がまさか解けない……！？ みたいなプレッシャーのかかり方ほんと厳しい。

A問題

　doubleを表示するときはprintfを使ってしまうね。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    double T, X;
    cin >> T >> X;
    printf("%.10f\n", T / X);
}

B問題

　accumulateとかmax_elementとかを使いたがる。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> L(N);
    for (ll i = 0; i < N; i++) {
        cin >> L[i];
    }
    ll sum = accumulate(L.begin(), L.end(), (ll)0);
    ll max = *max_element(L.begin(), L.end());
    cout << (max < (sum - max) ? "Yes" : "No") << endl;
}

C問題

　最初はN個の駒を全部端から置いていっていいのかなと思ったけど、中央に密集していて両端二つだけめちゃくちゃ離れているときにどっち端から置いていってもダメだということを考えて、じゃあ隣との差が大きいところから置いておくんだということになり、差分を取ってそれの小さい方からM-N個の和が答えということで出す、通る。今気づいたけどこういうところこそaccumulateの使いどころなんじゃないか。なんにしてもここまでは順調だったのに……。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> X(M);
    for (ll i = 0; i < M; i++) {
        cin >> X[i];
    }

    if (N >= M) {
        cout << 0 << endl;
        return 0;
    }

    sort(X.begin(), X.end());
    vector<ll> diff;
    for (ll i = 1; i < M; i++) {
        diff.push_back(X[i] - X[i - 1]);
    }
    sort(diff.begin(), diff.end());
    ll ans = 0;
    for (ll i = 0; i < M - N; i++) {
        ans += diff[i];
    }
    cout << ans << endl;
}

D問題

　本日の問題児。全然解けなくてめちゃくちゃ焦った。最初は両辺Xで排他的論理和を取れば右辺のXが全部消えるんじゃねとか考えていたけどそんなことはない。よくわからないので実験してみるがあまり法則性も見つからない。困った困ったと悩んでいると「排他的論理和は桁ごとに見る」という定跡を思い出す。そうやって考えていくとA_iを各桁で串刺しして見て、0が多い桁はXを1にしたいし、1が多い桁はその逆ということに気づく。ここまでで30分くらいかかった。

　実装でも時間がかかる。2進数にするには文字列にすればいいとかいう謎の勘違いをしたり、Xの範囲制限をすっかり忘れていたり、繰り上がりを2進数として実装しようとして悩んだり、ひどかった。最近あまり競技プログラミングをやっていないもので、実装はすぐに腕が落ちる。実装した後もなんか1WAが出てしまい、よくわからないけど方針は合っている気がしたのでリファクタリングしてコードを奇麗にしたら通った。ビットシフトのどこかだと思う。ビットシフトはバグを生みがち。

　ここで恐ろしい話。

　僕のも16が出るので嘘です。そうか、ちゃんとbitDPをやる方がまともだったかもしれないんですね。うーん、なぜbitDPの発想が出てこないのか。ガタガタだなぁ。まぁこういうこともあると切り替えていきましょう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N, K;
vector<ll> A;

int main() {
    cin >> N >> K;
    A.resize(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll ans = 0;
    bool under = false;
    for (ll i = 63; i >= 0; i--) {
        ll num1 = 0;
        for (ll j = 0; j < N; j++) {
            num1 += (A[j] & (1LL << i)) != 0;
        }

        if (!under && ((K & (1LL << i)) == 0)) {
            //0しか選べない
        } else {
            if (num1 >= N - num1) {
                //0を選んだ方が良い
                under = true;
            } else {
                //1を選んだ方が良い
                num1 = N - num1;
            }
        }
        ans += num1 * (1LL << i);
    }
    cout << ans << endl;
}