結果
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点問題のわりには難しかった。賢い方法が思い浮かばず、と制約がやけに小さかったので各竹が使用されないかのどれかに使用されるという4つの場合を持つとして全探索して解を実装した。結合のコストを考えていなかったり、使用されないところへ割り当てるときにも結合コストを足してしまったりとバグをたくさん産みながらなんとか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; } }