BOJ 15997 - 승부 예측

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1324	295	227	29.028%

문제

---

심심했던 무지와 콘은 TV를 보다가, 대한민국 선수단이 실시간으로 출전하고 있는 경기를 보게 되었다.

지금 보고 있는 경기는 조별리그가 진행 중인데, 대한민국이 속한 조는 총 4개 국가가 참가하여 경기가 진행되고 있다.

조별리그의 규칙은 다음과 같다.

• 4개의 팀이 조별리그를 진행한다.
• 한 팀은 자신을 제외한 모든 상대방과 한 번씩, 총 3번의 경기를 치른다.
• 경기의 승자는 승점 3점을 받고 비기는 경우 서로 승점 1점을 받는다. 지는 경우에는 승점을 받지 않는다.
• 조별리그를 모두 치른 후 승점 순으로 순위를 정하는데 승점이 같을 시에는 추첨으로 순위를 정하며, 추첨은 공평하게 진행된다. 순위를 정한 후 상위 2팀은 다음 라운드로 진출한다.

전문가들은 조별 리그의 6경기 전체에 대해서 어떤 팀이 승리할 확률, 비길 확률, 패배할 확률을 예측하였다. 무지와 콘은 모든 경기가 독립적으로 진행되었을 때 (어떠한 경기의 결과가 다른 경기의 결과에 영향을 주지 않음), 전문가들의 예상대로 진행된다면 각 팀이 조별리그를 통과하여 다음 라운드로 진출할 확률이 궁금해졌다. 하지만 무지와 콘은 직접 확률을 계산하지 못했고, 여러분들에게 도움을 요청하였다. 무지와 콘을 도와 이 문제를 해결해보자!

입력

---

첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다.
두 번째 줄부터 일곱 번째 줄까지는 A B W D L 순으로 주어지는데, 전문가들의 예측에 따르면 A와 B가 경기를 진행했을 때 A가 승리할 확률은 W, 비길 확률은 D, 질 확률은 L이라는 의미이다.
A, B는 각각 첫 번째 줄에 있는 국가명 중 하나이고, A와 B가 같은 경우는 주어지지 않는다. 또한 W, D, L은 최대 소수점 세 자리까지 주어지며, W + D + L = 1이 보장된다.

출력

---

i 번째 줄에, i 번째로 입력받은 국가가 다음 라운드에 진출할 확률을 출력한다.

출력한 결과와 실제 답을 비교하였을 때의 상대 오차 또는 절대 오차가 10^-6 이하인 경우에만 정답으로 인정한다.

접근

---

경기가 이루어질 경우의 수는 3^6 = 729가지로, 그냥 브루트 포스로 구하면 될 것이라 생각했다.
다만.. 구현하기가 상당히 귀찮은 문제임을 보자마자 알 수 있었다.
미루고 미루다가 결국 풀었다.

풀이

---

팀 이름을 인덱스로 가져가기 위해서, hashing이란 map을 만들어 관리해주었다.
그리고 Match란 구조체를 만들어서, 6개의 경기에 각 정보를 담아주었다.

DFS로 각 경기마다 확률과 승점을 담아서 6번째 인덱스에 도착하면 계산을 치뤄주었다.
고려해야되는 경우는 크게 5가지인데, if와 else if 문으로 처리해서 가능했다.

• 1등과 4등의 승점이 같은 경우 (4팀 모두 1/2의 확률)
• 1등과 3등의 승점이 같은 경우 (1~3등 모두 2/3의 확률)
• 2등과 4등의 승점이 같은 경우 (1등은 1의 확률, 2~4등은 1/3의 확률)
• 2등과 3등의 승점이 같은 경우 (1등은 1의 확률, 2~3등은 1/2의 확률)
• 그외 경우 (1~2등 모두 1의 확률)

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

struct Match
{
	string A, B;
	double win, draw, lose;
	friend istream& operator>>(istream&, Match& pos);
};

istream& operator>>(istream& is, Match& pos)
{
	is >> pos.A >> pos.B >> pos.win >> pos.draw >> pos.lose;
	return is;
}

Match match[6];
string team[4];
map<string, int> hashing;
double answer[4] = { 0, 0, 0, 0 };

void solve(double rate, vector<int> score)
{
	vector<pair<int, int>> rank;
	FUP(i, 0, 3)
	{
		rank.push_back({ score[i], i });
	}
	sort(ALL(rank));
	if (rank[0].first == rank[3].first)
	{
		FUP(i, 0, 3)
		{
			answer[i] += (rate * 0.5);
		}
	}
	else if (rank[1].first == rank[3].first)
	{
		FUP(i, 1, 3)
		{
			answer[rank[i].second] += (rate * 2 / 3);
		}
	}
	else if (rank[0].first == rank[2].first)
	{
		answer[rank[3].second] += rate;
		FUP(i, 0, 2)
		{
			answer[rank[i].second] += (rate / 3);
		}
	}
	else if (rank[1].first == rank[2].first)
	{
		answer[rank[3].second] += rate;
		FUP(i, 1, 2)
		{
			answer[rank[i].second] += (rate / 2);
		}
	}
	else
	{
		FUP(i, 2, 3)
		{
			answer[rank[i].second] += rate;
		}
	}
}

void DFS(int idx, double rate, vector<int> score)
{
	if (idx == 6)
	{
		solve(rate, score);
		return;
	}
	score[hashing[match[idx].A]] += 3;
	DFS(idx + 1, rate * match[idx].win, score);
	score[hashing[match[idx].A]] -= 3;
	score[hashing[match[idx].B]] += 3;
	DFS(idx + 1, rate * match[idx].lose, score);
	score[hashing[match[idx].B]] -= 3;
	score[hashing[match[idx].A]]++;
	score[hashing[match[idx].B]]++;
	DFS(idx + 1, rate * match[idx].draw, score);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	FUP(i, 0, 3)
	{
		CIN(team[i]);
		hashing[team[i]] = i;
	}
	FUP(i, 0, 5)
	{
		CIN(match[i]);
	}
	DFS(0, 1.0, { 0, 0, 0, 0 });
	COUT(fixed);
	cout.precision(8);
	FUP(i, 0, 3)
	{
		COUT(answer[i]);
		ENDL;
	}

	return 0;
}