Fが通せず終了。惜しいところまでいっていた気がしたけど、実際は全く惜しくなかった。
F. Equidistant Vertices
木のいくつかの頂点が同じ距離にある、ということは、別のある頂点（今回は中心と呼ぶ）があって、そこから等距離にあるとき、ということはコンテスト中に気付いていた。
なので、中心を全探索すれば良いのだが、それだと重複するものや、特定の頂点たちがもっと短い距離で結ばれている場合も数えてしまう。
それらをどのように除くか、というのが問題。
結論からいうと、「最初の1歩が全部違う場所に行く」（LayCurseさんのツイートより）場合を数えれば良い。これは全く思いつけていなかった。
確かに、これで、上に書いたようなダメな場合は除けている。
あとは、x歩進むとき、最初の1歩の候補がk個以上ある場合について、DPで数え上げれば良い。
（このDPの処理も、DP使う、と分かっていたから簡単に書けたけど、自力で思いつくのは楽じゃなかったかも）
0 件のコメント:
コメントを投稿