SRM 488 div2 hard: TheBoringGameDivTwo

問題

TopCoder Statistics - Problem Statement

解法

1 ラウンドの終わり方は 9 種類あります。(F が J を kill した後 B に kill される… etc)

それぞれの回数を p1, p2, ..., p9 とすると, scoreJ, killedJ, ... がその値によって一意に決まります。

p1 〜 p9 のうち, 4 つの値を決めると O(1) で他の値も決定できるので, がんばります。

class TheBoringGameDivTwo {
public:
    vector <int> find(int scoreJ, int killedJ, int scoreB, int killedB, int scoreF, int killedF) {
        const int INF = 10000;
        vector<int> ret(2);
        ret[0] = INF, ret[1] = -INF;
        for (int p3 = 0; p3 < 50; p3++) for (int p4 = 0; p4 < 50; p4++) {
            for (int p5 = 0; p5 < 50; p5++) for (int p6 = 0; p6 < 50; p6++) {
                int p7 = -(scoreJ-p3-p5);
                int p8 = -(scoreB-p4-p6);
                int p9 = scoreF-p3-p4-p7-p8;
                if (p9%2) continue;
                p9 /= 2;
                int p1 = killedB - p3-p7-p8-p9;
                int p2 = killedF-p1-p3-p4-p5-p6;
                if (p2+p4+p7+p8+p9 != killedJ) continue;
                if (p1 < 0 || p2 < 0 || p7 < 0 || p8 < 0 || p9 < 0) continue;
                int sum = p1+p2+p3+p4+p5+p6+p7+p8+p9;
                ret[0] = min(ret[0], sum);
                ret[1] = max(ret[1], sum);
            }
        }
        if (ret[0] == INF) ret.clear();
        return ret;
    }
};