pekempeyのブログ

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

2016 TCO Algorithm Hard. EllysTree

問題概要

木が与えられ、初期状態では Elly は頂点 0 にいる。Elly は先祖、子孫にジャンプすることができるが、過去に一度行ったことがある頂点にはジャンプできない。

Elly はすべての頂点を辿ることができるだろうか。辿ることができるなら、辿る順序のうち辞書順最小のものを求めよ。

解法

なるべく葉の方から埋めた方が有利なので、次のような貪欲で辿れるか判定できる。

  • 今いる頂点より下に葉があれば、どれでもいいのでその葉にジャンプする
  • 葉がなければ、最も近い先祖にジャンプする

これは結局のところ

  • 今いる頂点からジャンプできる最も高さの低い頂点にジャンプする

ということになる。

サンプル 1 の場合の動作例をスライドにした。

ただし、この貪欲で得られる解は辞書順最小とは限らない。

辞書順最小の解を得るには、今いる頂点から 0,...,n の順にジャンプしてみて実際に構成できるか試してみればいい。

サンプル 1 の場合、

  • 0 から 1 に飛んでみる。そこから貪欲に辿れるので 0 の次は 1 である。
  • 1 から 5 に飛んでみる。そこから貪欲に辿れるので 1 の次は 5 である。
  • 5 から 2 に飛んでみる。そこから貪欲に辿れるので 5 の次は 2 である。
  • 2 から 8 に飛んでみる。そこから貪欲に辿れないので 2 の次は 8 ではない。
  • 2 から 11 に飛んでみる。そこから貪欲に辿れるので 2 の次は 11 である。
  • 11 から 8 に飛んでみる。そこから貪欲に辿れないので 11 の次は 8 ではない。
  • 以後この繰り返し。

という処理で辞書順最小の解が得られる。


計算量が怪しいが危なげもなく通った。最悪ケースがあったら落としてください。

2016 TCO Algorithm Hard. EllysTree

判定部分の計算量にこだわらなければ結構速く通せたはずなので惜しいことをした。