1-indexedで説明します。
題意(意訳)
- n 人の人がいる。これらの人は過去に5回の試合に出ており、その順位が与えられる。順位はdistinct(同順はない)である。
- チャンピオンとは、3つ以上の試合において、他のどんな人よりも順位が強い(数値としては低い)人のことである。各試合の間に優劣はない(ポイントの高い試合、などはない)
- チャンピオンがいるならその人を述べよ(複数いるならどれでもいい)。いないならそれを述べよ
- ※後述の通り、複数の候補が存在することはありません
こう考えた 前提
まず、(aがbに)勝つをaはbより順位が強い試合が3つ以上あると定義します。
さて、問題のポイントは、チャンピオンがいるなら、１人に定まるです。なぜなら、チャンピオン$a$がいるとするなら、その人は3つ以上の試合の順位がほかのすべての人より強いです。もしも、他のチャンピオン$b$がいるとすると、その人は$a$に勝てる試合が3つ以上あることになりますが、これは前提に反します。
ただし、サンプルにある通り、チャンピオンがいない場合もあるです。
こう考えた STEP1 チャンピオン候補を決める
STEP1では、チャンピオンがいると仮定します。(この仮定で処理を進めるのがとても重要！)
まず、人$1$をチャンピオンと仮定して、人$2,3,..,n$と比較します。もし、すべてに勝ったなら、人$1$がチャンピオンです。もし、人$k$に負けたとすると、人$k$がチャンピオンかもしれないので、人$k$を基準にして$人k+1, k+2,..n$と比較します。これを繰り返します。$O(N)$です。
こうして最後に残った(最後まで処理した)チャンピオン候補kは真にチャンピオンとは限りません.
$k$よりも前の人に負けることがあるからです。ただし、チャンピオンがいるとするならば、最後に残ったチャンピオン$k$が答えです。なぜなら、前提の通り、チャンピオンはほかの人に負けるはずがないので、どういう順序(例えばソートされても)で上記の施行をしても絶対に最後まで残ります。
こう考えた STEP2 チャンピオンかを確かめる
そこで、チャンピオンかを判定します。候補$k$を$k$を除く$1,2,..,n$と愚直に比較します。すべてに勝てればチャンピオンです。$O(N)$です。
サンプル2の通り、途中で負けることがありますが、この場合は-1(チャンピオンはいない)です。他に本当のチャンピオンがいることはありません。STEP1後段の通り、それが存在するなら、$k$はそれに負けています。
実装
結果、$O(N)$で解けました。
私はSTEP1がうまく思い浮かばず、トーナメント形式でSTEP1を処理しました。(2人ずつ取っていき、買ったほうだけ次のリストに残す方法です)。
from copy import deepcopy
def do():
n = int(input())
dat = []
for i in range(n):
l = map(int, input().split())
l = list(l)
l.append(i)
dat.append(l)
odat = deepcopy(dat)
# STEP1:
while len(dat) > 1:
newdat = []
for i in range(0, len(dat), 2):
ls = dat[i:i+2]
if len(ls) == 1:
newdat.append(ls[0])
continue
a = ls[0]
b = ls[1]
cnt = 0
for i in range(5):
if a[i] < b[i]:
cnt += 1
if cnt >= 3:
newdat.append(ls[0])
else:
newdat.append(ls[1])
dat = newdat
# STEP2
candidate = dat[0]
for x in odat:
cnt = 0
for i in range(5):
if candidate[i] <= x[i]:
cnt += 1
if cnt >= 3:
continue
print("-1")
return
print(candidate[5] + 1)
q = int(input())
for _ in range(q): do()