競技プログラミング

問題概要

• 2 つの木が与えられる
• 各木から頂点を 1 つずつ選んで辺を追加すると新しい木が得られる
• 全ペアについて新しい木の直径の総和を求めよ

ABC389-Fで(遅延)セグメント木上の二分探索が使える問題が出た。

問題

結果的にACできたもののアホみたいな先入観込みで手こずってしまったのでメモに残しておく。

入青しました

1/6 のコンテストにて、2019 年から実に 4 年半以上の月日をかけて入青しました。

うぇーい

せっかくブログを立てたので競プロの記事を書きます。

dp などの問題で確率 mod P (P は大きい素数)を求めることがしばしばあります。
初見だと「は？確率の mod？何いってんだこいつ」となりがちなので、この記事では

単純なナップサック dp のような D 問題相当の dp なら解けるけど、確率 mod P とか言われると「は？何いってんだこいつ」となる人向けに

0. Python ユーザーが ACL の modint に相当するライブラリ等を使わずに
1. 答えが小数になることを許容してそのまま実装し
2. 実装した確率 dp を機械的に mod P に対応させる

というステップで解く方法について整理しました。