B - Who is Saikyo? Editorial by Nyaan
この問題のポイントは「最強のプログラマーの候補がちょうど 1 人である条件を整理する」という点です。この部分で方針を誤ると実装が少し大変になってしまいます。
条件を整理すると、実は以下のアルゴリズムで解くことができます。
- \(s[i]\) を「自分より強い人の人数」を管理する配列とする。はじめ
s
は \(0\) で初期化されている。 - \(i=1,2,\dots,M\) の順に、 \(s[A[i]]\) に \(1\) を加算するという操作を行う。
- 操作後に \(s[x] = 0\) である人がちょうど \(1\) 人であれば \(s[x] = 0\) である \(x\) が答えとなる。\(2\) 人以上いれば答えは
-1
となる。
アルゴリズムの正当性に関して、全てを説明しようとすると煩雑になるので要点をかいつまんで説明します。
下の図で表される例を考えます。(\(1 \gets 2\) は「人 \(1\) は人 \(2\) より強い」という意味。他も同様)
このとき、問題文の条件にもある 推移律 を満たすような強さの割り当て方は次の 2 通りです。
左側の割り当て方に注目すると、「\(1\) が最強で、\(2\) がその次に強く、\(3\) がその次に強く、\(4\) が最下位」という順序関係が成り立つことがわかります。つまり、\(1, 2, 3, 4\) という数列を考えると「左に番号が出て来る人は右に番号が出て来る人よりも強い」という関係が成り立ちます。
右側の割り当て方についても同様に \(1, 2, 4, 3\) という数列が「左に番号が出て来る人は右に番号が出て来る人よりも強い」という条件を満たします。
このように、問題文の条件を満たすように強さを割り当てると、ある \(1, 2, \dots, N\) を並べ替えて出来る数列 \(p\) が存在して、強さが \(p\) で番号が登場する順番として表すことができます。(これを 全順序 と呼びます)
この事実を利用すると、命題 \(P, Q\) を
- \(P\) : \(s[x] = 0\) である人がちょうど \(1\) 人
- \(Q\) : 最強のプログラマーが人 \(x\) に特定できる
としたときに 「\(P\) ならば \(Q\) である」「\(P\) でなければ \(Q\) でない」という 2 点が証明できて、ここからアルゴリズムが正しい答えを返すことが確認できます。
計算量は \(\mathrm{O}(N + M)\) で十分高速です。
- 実装例(C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<int> deg(N);
for (int _ = 0; _ < M; _++) {
int a, b;
cin >> a >> b;
--a, --b;
deg[b]++;
}
int ans = -1;
for (int i = 0; i < N; i++) {
if (deg[i] == 0) {
if (ans != -1) {
cout << -1 << endl;
exit(0);
} else {
ans = i + 1;
}
}
}
cout << ans << endl;
}
posted:
last update: