C-merのブログ

ザ・雑記

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;
    }
};