問題
パンがいくつかの種類に分かれている。ある種類のパンは分でちょうど焼き上がり、それより短い焼き時間だとundertoasted、長い焼き時間だとovertoastedとなる。
いくらかの種類のパンに対してundertoastedとなった焼き時間の列、overtoastedとなった焼き時間の列があたえられたとき、ありうるパンの種類数として最小値を求めよ。
解法
可能性としてあるのは-1,1,2の3通りなのでundertoastedとovertoastedの最大、最小値を見て場合分けしていく。
反省
30分ほどでAC。変に2分探索してずらしながら……とか考えていたので問題の仕組みに気づくのが遅かった。
気づいてからもu_max >= o_max
の条件を入れ忘れていて1WA、入れたときに不等号の向きを逆にしてしまいさらに1WAという感じでひどかった。
コード
#include"bits/stdc++.h" using namespace std; using ll = long long; class ToastXToast { public: int bake(vector<int> undertoasted, vector<int> overtoasted) { auto u_min = *min_element(undertoasted.begin(), undertoasted.end()); auto u_max = *max_element(undertoasted.begin(), undertoasted.end()); auto o_min = *min_element(overtoasted.begin(), overtoasted.end()); auto o_max = *max_element(overtoasted.begin(), overtoasted.end()); if (u_min >= o_min || u_max >= o_max) { return -1; } else if (u_max < o_min) { return 1; } else { return 2; } } };