7K12 blog

猫でも分かるアルゴリズム解説

ABC139 E - League

f:id:tkr987:20200517033132p:plain

https://atcoder.jp/contests/abc139/submissions/11590159

これでdif12Kとかマ?あまりに天才的な実装、文章から構造を整理できる気がしない。

f:id:tkr987:20200517033318p:plain

試合テーブルの各行について試合の順番が前後してはいけない。そういうわけで、各試合に名前と矢印を付けるとグラフが見えてくる(ぇ 1vs2と2vs1を同一頂点インデックスにする必要があることに注意して隣接リストを作る。入次数0の頂点集合をスタートとしてBFSで最短経路を求めたとき、最大値になった頂点が最後の試合になる。この最大値が答えになる。

なお、試合テーブルを有向グラフにしたときにループが存在すると答えが存在しない。IQ3の自分には非自明すぎるので、サンプルから予想するしかなさそうという気持ちになる。