[Atcoder] Tournament

https://agc009.contest.atcoder.jp/tasks/agc009_b

概要

  • トーナメント戦を行ったところ、1番の選手が優勝した。
  • 他の選手について、誰に負けたのかが与えられるので、条件をみたすようなトーナメント表の深さの最低値を求めよ。

考察

  • ある選手がどの選手を倒したかのグラフを作成し、1番の選手から再帰。
  • 倒した選手(N人)のそれぞれについてトーナメント表の深さを求めようとする(倒した選手がいなければ0)。
  • 深さを降順にソートし、これらに1からNまでの数値を割り当てて、足す。
  • 足した後の配列の最大値が答えである。

再帰の深さ

  • 単純に実装すると、最悪10万回の再帰が必要になり、スタックオーバーフローになるおそれがある。
  • 今回、C++は 偶然 大丈夫であったが、RubyやPythonだと不可であった。
    • スタック拡張テクを使っても依然として通らない。
  • 今回は場当たり的(テストケース依存)な対応になるが、N/2番の選手から一旦再帰しておくことで再帰の深さをある程度減らすことができる。
    • この状態でもスタック拡張テクは依然として必要である。

解答例

余談