AtCoder ABC #139 : E - League

Eのタイムロス+1TLEがもったいない。
https://atcoder.jp/contests/abc139/tasks/abc139_e

問題

Nチームで総当たり戦を行う。
各チーム戦う相手の順番が決まっているものとする。

各チーム、1日で1試合しか行えない。異なるチームは同日に並行して試合を行えるとする。
総当たり戦を完了するまでに必要な最少日数は何日か。

解法

試合ができるところからどんどん行えばよい。
あとは日数の効率的な数え方を考えよう。

愚直に、「全チーム見て試合できそうなところを貪欲に行う」とすると、総当たり戦の順番によってO(N^2)日必要となり、判定にO(N^3)かかってしまう。
そこで、2日目以降は前日に試合の実施状況に変化があった人のみ次の試合が可能か判定するようにしよう。
そうすると各チームO(N)回しか判定しないので、O(N^2)で済む。

int N;
deque<int> A[1010];
int step[1010];
int M;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		FOR(j,N-1) {
			cin>>x;
			A[i].push_back(x-1);
		}
	}
	M=N*(N-1)/2;
	
	queue<int> Q;
	FOR(i,N) Q.push(i);
	
	int num=0;
	while(Q.size()) {
		int ok=0;
		
		queue<int> Q2;
		
		while(Q.size()) {
			i=Q.front();
			Q.pop();
			if(step[i]<=num && A[i].size() && A[A[i].front()].front()==i && step[A[i].front()]<=num) {
				step[i]=step[A[i].front()]=num+1;
				Q2.push(i);
				Q2.push(A[i].front());
				A[A[i].front()].pop_front();
				A[i].pop_front();
				M--;
			}
		}
		num++;
		if(M==0) break;
		swap(Q,Q2);
	}
	
	if(M) cout<<-1<<endl;
	else cout<<num<<endl;
}

まとめ

大雑把にO(N^3)解法で通るかなと思ったけどダメだった。
横着はいかんね…。