問題リンク 解説 制約を見ると，時系列順に DP をしてやれば解けそうだが，ある社員が鍵を持っているかどうかの影響は，出た直後と戻る直前両方の時間に対して発生するので，時系列順に見るのは得策ではない． ある社員が鍵を持っていないとき，出た直後の区…

問題リンク 解説 答えを二分探索する． 答えを決め打ちすればその答えよりある貴族の踊りが上手いか下手かだけが問題になる． トーナメントのような表を描いて，「この位置にくる貴族の踊りが答えより 上手い/下手な 条件」を考えてやる． その子部分木で最…

問題リンク 解説 どのような移動が可能か考えると，「上り路線から，ある駅で下り路線に変えていくらか戻ったりスタンプを押したりして，またどこかの駅で上り路線に乗り直す」という動きの連鎖になることがわかる． 次のような DP ができる． $dp[i][j]=i$ …

問題リンク 解説 まず、$P$ 頂点のグラフを構築できれば、その中での経路のうち辺のコストの最大値の最小化をすればいいことになる。 このグラフ上でクラスカル法みたいなことをやれば、木上の問題になるのもすぐわかる。 さて、この木の構築方法だが、各建…

問題リンク 解説 bit DP くらいしか解けそうな方法がなくて困るが、制約を眺めると $D_i\leq 7$ になっている。つまり、一定以上に離れた位置にある小籠包を食べる順番は美味しさの総和に関係ない。 次のような DP をする。 $dp[i][j]=i$ 番目の小籠包を食べ…

問題リンク 解説 小課題は自明なので略 $Y_i=0$ の場合を考えると、トポロジカル順で DP をしてやれば解ける。 データ構造などで処理するのは難しそうなので、$Y_i$ に付随する計算量は、 $Y_i$ の定数倍もしくは小さい別の関数がかかった形にする必要がある…