ABC139 E - League (500)

概要

下記の制約があるNプレイヤーの総当たり対戦を考える。

• 各プレイヤーは1日1回しか試合できない
• プレイヤーiがj番目に対戦する相手はA[i][j]

このとき、全ての試合が終わるまで必要な日数の最小値を求めよ。なお、制約下で総当たり対戦ができない場合は-1を出力せよ。

制約

3 ≦ N ≦ 1000

方針

各プレイヤーのその時点での対戦相手を確認し、対戦日程を組んでゆく。

プレイヤーiのその時点での対戦相手がプレイヤーjで、かつプレイヤーjのその時点での対戦相手がプレイヤーiなら対戦成立である。
別のケースとして、プレイヤーiのその時点での対戦相手がプレイヤーjで、かつプレイヤーjのその時点での対戦相手がプレイヤーkなら、プレイヤーiは、プレイヤーjがプレイヤーkと対戦したのちにプレイヤーjと対戦することになる。

基本的には、その時点で対戦可能である対戦を順番に組んでゆけばよい。ただし、プレイヤーの探索方法に気を付けないと、計算量が増加してしまう。

効率的な計算方法として、「前日に試合があったプレイヤー」をqueueに入れてゆき、そのqueueの中のプレイヤーのみを探索する方法がある。この場合、上記のようにプレイヤーiがプレイヤーjとプレイヤーkの対戦を待たなければいけないケースは、プレイヤーiは対戦が組まれなかった場合一旦queueから抜けてしまうが、プレイヤーjの探索での対戦相手として選ばれるため、うまく計算される。

感想

kmjpさんのブログを参考にしました。
kmjp.hatenablog.jp

解答

・コンテスト後のAC解答
Submission #7300415 - AtCoder Beginner Contest 139

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	queue<int> a[n];
	rep(i, n) rep(j, n-1){
		int x;
		cin >> x;
		x--;
		a[i].push(x);
	}
 
	queue<int> q;
	rep(i, n) q.push(i);
 
	int cnt = 0;
	bool updated = true;
 
	queue<int> q2;
	while(updated){
		updated = false;
 
		vector<bool> used(n, false);
		while(q.size() > 0){
			int i = q.front();
			q.pop();
 
			if(!used[i] && !a[i].empty()){
				int j = a[i].front();
				if(!used[j] && !a[j].empty() && a[j].front() == i){
					// cout << cnt << "," << i << "," << j << endl;
					updated = true;
					a[i].pop();
					a[j].pop();
					q2.push(i);
					q2.push(j);
					used[i] = true;
					used[j] = true;
				}
			}
		}
 
		if(updated) cnt++;
		swap(q, q2);
	}
 
	rep(i, n){
		if(!a[i].empty()){
			cout << -1 << endl;
			return 0;
		}
	}
 
	cout << cnt << endl;
}

・コンテスト中の1TLE解答。上記解答とは異なり、プレイヤーを探索する際に冗長なForループにしてしまっている。
Submission #7278866 - AtCoder Beginner Contest 139

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	queue<int> a[n];
	rep(i, n) rep(j, n-1){
		int x;
		cin >> x;
		x--;
		a[i].push(x);
	}
 
	bool updated = true;
	int cnt = 0;
	while(updated){
		updated = false;
		bool used[n] = {};
		
		for(int i = 0; i < n; i++){
			if(used[i] || a[i].empty()) continue;
			int j = a[i].front();
			if(!used[j] && a[j].front() == i){
				// cout << cnt << "," << i << "," << j << endl;
				updated = true;
				a[i].pop();
				a[j].pop();
				used[i] = true;
				used[j] = true;
			}
		}
		if(updated) cnt++;
	}
 
	rep(i, n){
		if(!a[i].empty()){
			cout << -1 << endl;
			return 0;
		}
	}
 
	cout << cnt << endl;
}