AtCoder Beginner Contest 302 感想 C問題
私はこの問題をコンテストの最中に3回もペナルティをもらって「なんでだ?」となりながら解いてました。
ランダムに入力を生成して解きました。
解き方は合っていたのにC++のlower_boundの仕様を忘れてずっと悩んでいました。
勘違いしたままACして……本番中に通した解法は本当は落ちるケースがあったかもしれない解法だったのかもしれません……。
D - Impartial Gift
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); long long N, M, D; cin >> N >> M >> D; vector<long long> A(N, 0LL); vector<long long> B(M, 0LL); for (long long i = 0LL; i < N; ++i) { cin >> A[i]; } for (long long i = 0LL; i < M; ++i) { cin >> B[i]; } sort(B.begin(), B.end()); long long ans = -1LL; for (long long i = 0LL; i < N; ++i) { long long r = upper_bound(B.begin(), B.end(), A[i] + D) - B.begin() - 1; if (r >= 0LL && abs(A[i] - B[r]) <= D) { ans = max(ans, A[i] + B[r]); } } cout << ans << endl; return 0; }
私のコードはBの数を配列で受け取ってソートしてます。
そして、Aの数を順番に見ていってBの配列の中に合致する数がないか調べて、その中で一番大きい数を探しています。
そうしていく内にその中に求めたい答えがあるのでそれを探し出せば終わりです。
口で言うとこんな感じですかね?
ややこしいようですが、分からなくもないと思います。
この問題、コンテストの最中に「なんで答えが合わないの?」とずっとヤバヤバでした。
C++の関数の仕様を忘れて迷走しました。
もっと早く解けたのにってことにもならないけど、普段から関数の使い方を忘れるとものすごく時間ロスしますね……。
どうでもいいことを書きました。
典型問題なのでやっておくと損はないと思います。
慣れていきましょう!
追記・追伸
今日のブログの更新はありません。
ABCの記事を書いているだけで力が尽き果てました。
ぐでーってなってます。
こんなに解説書こうと思ったら大変だとは……。
次からはくだらない感想をいっぱい書いていくのでご了承ください。
解説書くって難しいね!
私はもうくだらないことばっか言う方が好きです!