Codeforces Round #126 (Div. 2) C : Football Championship
問題概要
サッカーのグループリーグを抜けるのに要求されるスコアを求める問題。
解法
これまでの結果から得点に大差はつかないことが分かっているので、スコアについて適当な範囲で全探索する。基本的には実装ゲー。
acceptされたコード
#include <iostream> #include <string> #include <sstream> #include <algorithm> #include <map> #include <cstdio> using namespace std; const string myteam = "BERLAND"; map< pair<string, string>, pair<int,int> > results; map<string, int> cnts; pair<string, string> another; void init() { for (int i = 0; i < 5; ++i) { string line; getline(cin, line); for (int j = 0; j < (int)line.length(); ++j) { if (line[j] == ':') { line[j] = ' '; } } stringstream ss(line); string t1, t2; int p1, p2; ss >> t1 >> t2 >> p1 >> p2; ++cnts[t1]; ++cnts[t2]; results[make_pair(t1, t2)] = make_pair(p1, p2); } another.first = myteam; for (map<string, int>::iterator itr = cnts.begin(); itr != cnts.end(); ++itr) { if (itr->first != myteam) { if (itr->second == 2) { another.second = itr->first; } } } } bool check() { map<string, pair<int, pair<int,int> > > dict; for (map<string,int>::iterator itr = cnts.begin(); itr != cnts.end(); ++itr) { dict[itr->first] = make_pair(0, make_pair(0, 0)); } for (map<pair<string,string>, pair<int,int> >::iterator itr = results.begin(); itr != results.end(); ++itr) { string t1 = itr->first.first, t2 = itr->first.second; int p1 = itr->second.first, p2 = itr->second.second; dict[t1].second.first -= p1 - p2; dict[t2].second.first -= p2 - p1; dict[t1].second.second -= p1; dict[t2].second.second -= p2; if (p1 > p2) { dict[t1].first -= 3; } else if(p2 > p1) { dict[t2].first -= 3; } else { dict[t1].first -= 1; dict[t2].first -= 1; } } pair< pair<int,int>, pair<int,string> > rs[4]; int p = 0; for (map<string, pair<int, pair<int,int> > >::iterator itr = dict.begin(); itr != dict.end(); ++itr) { rs[p++] = make_pair(make_pair(itr->second.first, itr->second.second.first), make_pair(itr->second.second.second, itr->first) ); } sort(rs, rs + 4); return rs[0].second.second == myteam || rs[1].second.second == myteam; } void solve() { pair<int,int> ans(10000, 10); for (int x = 1; x < 100; ++x) { for (int y = 0; y < x; ++y) { results[another] = make_pair(x, y); bool win = check(); if (win) { ans = min( ans, make_pair(x-y, y) ); } } } if (ans.first == 10000) { puts("IMPOSSIBLE"); } else { printf("%d:%d\n", ans.first + ans.second, ans.second); } } int main() { init(); solve(); return 0; }