SRM 488 div2 hard: TheBoringGameDivTwo
解法
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; } };