SRM 503 Div 1 - Problem 250 ToastXToast
問題
SRM 503 Div 1 - Problem 250 ToastXToast
TopCoder Statistics - Problem Statement
使用言語
C++
方針
・色々やるがぐちゃぐちゃ
→・まず,undertoastedの最{小,大}値がovertoasted の最{小,大}値を上回っているのはおかしい.なぜなら,全てのトーストのタイプは,やけなすぎとやけすぎのどちらも存在しているはずだから.
・max(u1, u2, ... , ui) < max(o1, o2, ... , oi)なら
ここの間で区切れば良い.
・その他の場合は,min(u1, u2, ... , ui)より大きく,max(u1, u2, ... , ui)より小さいところで適当にmin(o1, o2, ... , oi)未満のX1を設定してしまい,X1未満のundertoastedはタイプ1,X1より大きいのundertoastedはタイプ2としてしまえば良い.同様に,min(o1, o2, ... , oi)より大きく,max(o1, o2, ... , oi)より小さいところで適当にmax(u1, u2, ... , ui)より大きいのX2を設定してしまい,X2未満のovertoastedはタイプ1,X2より大きいovertoastedはタイプ2としてしまえば良い.(例外は上で弾いている)
ex (sample4)
1 | 2 4
3 5 | 6
(X1,2の値は|の含まれる閉区間であればどこでも良い)
所感
・下手に考えるだけ無駄だった
・マクロ楽しい
コード
#define Min(a) *min_element(a.begin(), a.end()); #define Max(a) *max_element(a.begin(), a.end()); class ToastXToast { public: int bake(vector<int> undertoasted, vector<int> overtoasted) { int min_u = Min(undertoasted); int max_u = Max(undertoasted); int min_o = Min(overtoasted); int max_o = Max(overtoasted); if (min_u > min_o || max_u > max_o) return -1; else if (max_u < min_o) return 1; else return 2; } };