水たまり

AtCoder Beginner Contest 119

競技プログラミング

結果

　38分47秒(1WA)で全完、109位だった。WAを出さなければ100位以内だったが、残念。

A問題

　6文字目と7文字目を見て判定。A問題のわりには一瞬思考が必要。

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

int main() {
    string S;
    cin >> S;
    if (S[5] == '1' || S[6] >= '5') {
        cout << "TBD" << endl;
    } else {
        cout << "Heisei" << endl;
    }
}

B問題

　C++にはlong doubleというものがあるらしいのでそれを使ってみたらフォーマット指定のミスなのかWAが出た。doubleに書き換えたら通った。UnratedなABCでこういうことを試してみるやつ。別にdoubleの精度が悪くて落ちた経験もないけど……。

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

int main() {
    ll N;
    cin >> N;
    double ans = 0.0;
    for (ll i = 0; i < N; i++) {
        double x;
        string u;
        cin >> x >> u;
        if (u == "JPY") {
            ans += x;
        } else {
            ans += x * 380000;
        }
    }

    printf("%.10f\n", ans);
}

C問題

　300点問題のわりには難しかった。賢い方法が思い浮かばず、 $N \le 8$ と制約がやけに小さかったので各竹が使用されないか $A, B, C$ のどれかに使用されるという4つの場合を持つとして全探索して $O(4^N)$ 解を実装した。結合のコストを考えていなかったり、使用されないところへ割り当てるときにも結合コストを足してしまったりとバグをたくさん産みながらなんとかAC。うーん、何か良い方法があったかな。

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

bool next(vector<ll>& v) {
    for (ll i = v.size() - 1; i >= 0; i--) {
        if (v[i] != 3) {
            v[i]++;
            for (ll j = i + 1; j < v.size(); j++) {
                v[j] = 0;
            }
            return true;
        }
    }
    return false;
}

int main() {
    ll N, A, B, C;
    cin >> N >> A >> B >> C;

    vector<ll> l(N);
    for (ll i = 0; i < N; i++) {
        cin >> l[i];
    }

    ll ans = LLONG_MAX;
    vector<ll> use(N, 0);
    do {
        vector<ll> len(4, 0);
        ll tmp = 0;
        for (ll i = 0; i < N; i++) {
            if (use[i] > 0 && len[use[i]]) {
                tmp += 10;
            }
            len[use[i]] += l[i];
        }

        bool empty = false;
        for (ll i = 1; i <= 3; i++) {
            if (len[i] == 0) {
                empty = true;
            }
        }
        if (empty) {
            continue;
        }

        tmp += abs(A - len[1]) + abs(B - len[2]) + abs(C - len[3]);
        ans = min(ans, tmp);
    } while (next(use));

    cout << ans << endl;
}

D問題

　まぁこんなの寺を先に回るルートか神社を先に回るルートかの2通りを考えればいいだけだよねという感じ。2分探索を何度も使うことになって頭が混乱しがちなので最初に全ての寺について最寄りの神社までの距離、全ての神社について最寄りの寺までの距離を計算しておくことで多少は見通し良くなったか。それでもif文が多くてダサいコードを書いてしまったが。三項演算子で奇麗に書くべきでしたね。

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

int main() {
    ll A, B, Q;
    cin >> A >> B >> Q;
    vector<ll> s(A), t(B), x(Q);
    for (ll i = 0; i < A; i++) {
        cin >> s[i];
    }
    for (ll i = 0; i < B; i++) {
        cin >> t[i];
    }
    for (ll i = 0; i < Q; i++) {
        cin >> x[i];
    }

    vector<ll> s_to_min(A), t_to_min(B);
    for (ll i = 0; i < A; i++) {
        ll j = lower_bound(t.begin(), t.end(), s[i]) - t.begin();
        if (j == 0) {
            s_to_min[i] = abs(t[j] - s[i]);
        } else if (j == t.size()) {
            s_to_min[i] = abs(t[j - 1] - s[i]);
        } else {
            s_to_min[i] = min(abs(t[j] - s[i]), abs(t[j - 1] - s[i]));
        }
    }
    for (ll i = 0; i < B; i++) {
        ll j = lower_bound(s.begin(), s.end(), t[i]) - s.begin();
        if (j == 0) {
            t_to_min[i] = abs(s[j] - t[i]);
        } else if (j == s.size()) {
            t_to_min[i] = abs(s[j - 1] - t[i]);
        } else {
            t_to_min[i] = min(abs(s[j] - t[i]), abs(s[j - 1] - t[i]));
        }
    }

    for (ll i = 0; i < Q; i++) {
        ll ans = LLONG_MAX;

        //寺→神社
        ll j = lower_bound(s.begin(), s.end(), x[i]) - s.begin();
        if (j == 0) {
            ans = min(ans, abs(x[i] - s[j]) + s_to_min[j]);
        } else if (j == s.size()) {
            ans = min(ans, abs(x[i] - s[j - 1]) + s_to_min[j - 1]);
        } else {
            ans = min(ans, abs(x[i] - s[j]) + s_to_min[j]);
            ans = min(ans, abs(x[i] - s[j - 1]) + s_to_min[j - 1]);
        }

        //神社→寺
        j = lower_bound(t.begin(), t.end(), x[i]) - t.begin();
        if (j == 0) {
            ans = min(ans, abs(x[i] - t[j]) + t_to_min[j]);
        } else if (j == t.size()) {
            ans = min(ans, abs(x[i] - t[j - 1]) + t_to_min[j - 1]);
        } else {
            ans = min(ans, abs(x[i] - t[j]) + t_to_min[j]);
            ans = min(ans, abs(x[i] - t[j - 1]) + t_to_min[j - 1]);
        }
        cout << ans << endl;
    }
}