読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CROC 2016 - Elimination Round D. Robot Rapping Results Report

codeforces.com

問題概要

ロボット i とロボット j の対戦結果が与えられる。

ロボット同士を戦わせたときに勝つのはスキルレベルの大きい方である。

ロボットの強弱関係が完全に分かるのは何試合目か。なおスキルレベルは distinct であることが保証されている。

解法

すべての対戦結果を見ても強弱関係の分からないロボットの組がいるなら -1 を出力する。

強弱関係を完全に知るのに必要な情報は、順序が隣接しているロボット同士の対戦結果である。

A が B に勝つという関係を有向グラフで表せば、次の図の実線の辺が必要である。

f:id:pekempey:20160319142202p:plain

よって次のような処理すればいい。

  1. 任意のロボットの組の強弱関係が分かるかを判定する
  2. 強弱関係でソートする
  3. 必要な情報が現れる最後のインデックスを探す

強弱関係が完全に分かるかどうかを調べるには、DAG の根からの最長距離が n-1 であるような頂点があるかを見ればいい。

強弱関係が完全にわかっているなら最長距離がそのまま強弱関係のソート結果になる。

後は 3 をやって終わり。

CROC 2016 - Elimination Round D. Robot Rapping Res ...

最近トポロジカルソートのライブラリを作ったので使ってみた。