SRM 664 Div2 Med BearPlaysDiv2

本番普通に解けんかった...。orz
しょげてもしょうがないので復習。復習。
ポイントは以下だと思っている。二番目に気づけたら全探索+memo化は思いつけたかも。
- 操作の前後で総和が変わらない。
- 多変数でも制約があると変数が1つ減るとみなせる。

class BearPlaysDiv2 {
public:

string equalPiles(int A, int B, int C) {
        // (x,y) -> (y-x,2*x) の操作ではトータルの個数が変わらない
        // (x+y = y-x+2*x)
        // ということは (a,b,c) = (a,b,S-(a+b)) とあらわせる。
        // 今 A,B,C <= 500 なので (a,b,c) からの遷移は最大 500*500 通り
        // よって memo 化を使って全探索してやればよい
        vector<vector<bool>> memo(1501,vector<bool>(1501,false));
        int S = A+B+C;
        function<bool(int,int)> rec = [&](int x, int y) {
            // すでに探索済み
            if (memo[x][y])
                return false;
            // 全部一致
            if (x==y && S-(x+y)==x)
                return true;

            memo[x][y] = true;
            vector<int> piles = {x,y,S-(x+y)};
            sort(RANGE(piles));

            REP(i,3)
            FOR(j,i+1,3)
            {
                if (rec(piles[j]-piles[i], 2*piles[i]))
                    return true;
            }
            return false;
        };
        // 総和はかわらないので最終的な値は総和/3のはず
        if ((A+B+C)%3 == 0)
        {
            if (rec(A,B))
                return "possible";
        }
        return "impossible";
}
};