SRM 664 Div2 Medium BearPlaysDiv2

問題

3つの数字があって2つの数字A, Bを選ぶ,小さい方の数を大きい方から持ってくる(A + A, B- A). この作業を繰り返して3つの数字が等しくなるかどうかを判定する問題

解答

入力の3つの数は高々500. 順序は無視して良い,かつ操作の数が限定されているとしてメモ化して全探索. 但し,操作によっては3つの数のうち,500を超える数が出てくる場合もあり, 操作の数が限定されるだろうという予想も不確かなので, 本当に大丈夫かどうかはわからないままコーディングした.

結果大丈夫だった.

class BearPlaysDiv2
{
public:
  map<vector<int>, bool> memo;
  bool calc(int A, int B, int C){
    // cout << "(" << A << "," << B << "," << C << ")=" << v << endl;
    vector<int> items = {A, B, C};
    sort(items.begin(), items.end());
    // cout << "(" << items[0] << "," << items[1] << "," << items[2] << ")" << endl;
    if (items[0] == items[1] && items[0] == items[2]){
      // cout << "found !!!!!!!!!!!!" << endl;
      memo[items] = true;
    }
    map<vector<int>, bool>::const_iterator itr = memo.find(items);
    if (itr != memo.end()) {
      // cout << "found [" << itr->second << "]" << endl;
      return itr->second;
    }
    else{
      memo[items] = false;
      memo[items] =
        calc(2*items[0], items[1]-items[0], items[2]) ||
        calc(2*items[0], items[1], items[2]-items[0]) ||
        calc(items[0], 2*items[1], items[2]-items[1]) ;
    }
    return memo[items];
  }
  string equalPiles(int A, int B, int C)
    {
      return calc(A, B, C) ? "possible" : "impossible";
    }
};