[AtCoder] ABC139 E – League (500点)
問題概要
N人の選手がいる。各選手は１日１試合のみできる。総当たり戦を行う時、最短で何日かかるか？
ただし、i 番目の選手は \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}\) の順番で試合をする。
制約
\begin{align}
&3 \leq N \leq 1000 \\
&1 \leq A_{i, j} \leq N
\end{align}
考え方
単純に考えると以下のようなアルゴリズムを考えることができます。
- 選手N人それぞれに対応した待ち行列を作り、 \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}\) を格納しておく
- O(N)でその日に行う試合を決定でき、待ち行列からその試合を取り除く
- 2 を待ち行列の中が全て無くなるまで繰り返す。繰り返し回数が最小日数となる
しかし、このアルゴリズムでは、最悪の場合１日１回しか試合をすることができないので、O(N)の計算を N(N-1)/2 回繰り返すことになります。これでは間に合いません。
そこで、発想の転換が必要になります。
試合には行う順序が定められています。全ての試合を行うことができる場合、試合は半順序集合となっています。このような場合は、閉路のない有向グラフで表現することができます。
半順序集合 \(\Leftrightarrow\) 閉路のない有向グラフ(DAG)で表現可能
解き方
以下のようなアルゴリズムで解くことができます。
- 試合を頂点として、有向グラフを構成する
- 有向グラフに閉路が存在すれば全ての試合を行うことができない。閉路がなければ、始点からの最長のパスの長さが答え
i<j の時、選手 i と選手 j の試合を、\(\frac{i(i-1)}{2} + j + 1\) 番とすれば、試合に1から\(\frac{N(N-1)}{2}\) までの番号を一意に定めることができます。
後は\(A_{i, 1} \rightarrow A_{i, 2} \rightarrow \ldots \rightarrow A_{i, N-1}\) という順序関係を辺として与えれば良いです。最初の試合は 0 番から辺を張ります。
閉路の検出や、始点からの最長のパスの長さは、深さ優先探索で書くことが可能です。
解答例
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
struct Edge {
long long to;
};
using Graph = vector<vector<Edge>>;
int encode(int i, int j) {
if (i < j) swap(i, j);
return i * (i - 1) / 2 + j + 1;
}
int seen[2000000]; // 1:現在探索中のパスで行きがけ 2:探索後の頂点
int d[2000000]; // d[i]:= 始点から i への距離
int dfs(const Graph &G, int now) {
if (seen[now] == 2) return d[now];
seen[now] = 1;
for (auto e : G[now]) {
if (seen[e.to] == 1) { // 閉路を検出
cout << -1 << endl;
exit(0);
}
chmax(d[now], dfs(G, e.to) + 1);
}
seen[now] = 2;
return d[now];
}
int main() {
long long N;
cin >> N;
Graph G(N * (N - 1) / 2 + 1);
FOR(i, 0, N) {
int now = 0;
LOOP(N - 1) {
int j;
cin >> j;
j--;
int next = encode(i, j);
G[now].push_back({next});
now = next;
}
}
cout << dfs(G, 0) << endl;
return 0;
}