AtCoder Beginner Contest 123

結果

 57分29秒(1WA)で全完。それでも135位と順位はそこそこだったので、全体として難しかったんだと思う。

A問題

 入力が多い。A問題はforループなしで解けるように、みたいな話を聞いたことがある気がするが、おとなしくループを回す。しかしコードを書き終わってから出力例1の解説を見て、隣を見るのではなくてaeを見ればいいだけなのかと気づいた。A問題で2分以上かかるのは滅多にないことだ。出力する文字列も単純ではなく、嫌な予感がし始める。

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

int main() {
    vector<ll> x(5);
    ll k;
    for (ll i = 0; i < 5; i++) {
        cin >> x[i];
    }
    cin >> k;
    bool ok = x[4] - x[0] <= k;

    cout << (ok ? "Yay!" : ":(") << endl;
}

B問題

 10の倍数はそのまま加算、そうでないものは1の位を切り上げする。10の倍数を除いて一番1の位が小さいものを最後に注文するのが最適。この辺まではパッとわかったけど結構実装に悩んでしまった。切り上げで総和を取って、一番小さいものだけ引くというのがわかりやすいかと思って実装。どこまで簡単になったかは微妙なところ。

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

int main() {
    vector<ll> x(5);
    for (ll i = 0; i < 5; i++) {
        cin >> x[i];
    }

    ll m = 10;
    ll s = 0;
    for (ll i = 0; i < 5; i++) {
        if (x[i] % 10 != 0) {
            m = min(m, x[i] % 10);
        }
        s += (x[i] % 10 == 0 ? x[i] : x[i] + 10 - x[i] % 10);
    }

    cout << s - 10 + m << endl;
}

C問題

 かなり悩む。最初は普通にシミュレーションしていけば大丈夫なのかと思っていたら各変数の最大値が10^{15}でとんでもなかった。落ち着いて1地点ずつ見ていくとなんかできそうということで書いていくとサンプル3が合わない。輸送力は前のものに制約を受けるのだなぁという感じで適当にminを取ったらそれっぽくなったので出したら通った。考察がふわふわしたままなんか通ったという感じで不完全燃焼。メモも全然取っていなかった。

f:id:tokumini:20190406223313j:plain

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

int main() {
    ll N;
    cin >> N;
    vector<ll> x(5);
    for (ll i = 0; i < 5; i++) {
        cin >> x[i];
        if (i > 0) {
            //前のものより大きくなることはない
            x[i] = min(x[i], x[i - 1]);
        }
    }

    ll ans = 0;
    for (ll i = 0; i < 5; i++) {
        //時刻ansではここにN - x[i] * (ans - i)人いる
        //それら全てを運ぶのにかかる時間をansに足す
        ans += (max((N - x[i] * (ans - i)), (ll)0) + x[i] - 1) / x[i];
    }

    cout << ans << endl;
}

D問題

 パッと見で制約が厳しく難しそう。サンプル1とか2を解いてみるけどあまり思い浮かぶものもなく、DPっぽい雰囲気を感じたけど最大値が大きいのでdp[X][Y][Z]が取れなくて断念。しばらく考えていると「ある美味しさd以上となる選び方はいくつあるか?」という問題ならi, jX,Yまでそれぞれループさせて最後の一つは二分探索で求まると気づいて、手ごたえが出てくる。dが求まればそれ以上のものを実際に作ってstd::multisetに詰めていき、K個以上溜まったら終了という感じで出す。WA。困る。

 std::multisetK個溜まった時点で打ち切っているのがダメだとはすぐ気づいた。d以上のものの中でも大小があり、後でもっと大きいものが来るかもしれないから。しかしたとえば全てのケーキが1だと、全パターンが美味しさの和3になるので、d以上のものをstd::multisetに詰めていくと計算量が大変なことになる。ちょっと悩んで、dを超えるものを詰めていって、K個まで届かなければあとはdを必要回数出力すればよいと気づいてAC。難しかった。

 メモを見返すと二分探索に気づいたところで「二分探索」という文字も書ききらずに実装へ移っていることがわかってちょっと面白かった。

f:id:tokumini:20190406223614j:plain

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

int main() {
    ll X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<ll> A(X), B(Y), C(Z);
    for (ll i = 0; i < X; i++) {
        cin >> A[i];
    }
    for (ll i = 0; i < Y; i++) {
        cin >> B[i];
    }
    for (ll i = 0; i < Z; i++) {
        cin >> C[i];
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    ll ok = 0, ng = A.back() + B.back() + C.back() + 1;
    while (ok + 1 != ng) {
        ll mid = (ok + ng) / 2;

        //mid以上のものがk個作れるか?
        ll num = 0;
        for (ll i = 0; i < X; i++) {
            for (ll j = 0; j < Y; j++) {
                ll t = mid - A[i] - B[j];
                num += (C.end() - lower_bound(C.begin(), C.end(), t));
            }
        }

        (num >= K ? ok = mid : ng = mid);
    }

    multiset<ll> st;
    for (ll i = 0; i < X; i++) {
        for (ll j = 0; j < Y; j++) {
            ll t = ok - A[i] - B[j];
            for (ll k = (upper_bound(C.begin(), C.end(), t) - C.begin()); k < Z; k++) {
                st.insert(A[i] + B[j] + C[k]);
            }
        }
    }

    for (auto itr = st.rbegin(); itr != st.rend(); itr++) {
        cout << *itr << endl;
        K--;
    }

    for (ll i = 0; i < K; i++) {
        cout << ok << endl;
    }
}