問題リンク 解説 求めるべき長方形がどのような形をしているか考えてみます。 題意より、求める長方形は3頂点が異なる色で、残りの1頂点は残りのどれかと同じ色です。 このような長方形には、3頂点が異なる色になるL字型の部分が必ず2つ含まれています。 よ…

問題リンク 解説 それぞれのジャンルごとに売る冊数を決めたとき、ジャンルごとの価格の最大値は明らかです。価格の高いものから貪欲に売るのが明らかに最適であるからです。 これを先に求めれば、ジャンルごとに売る冊数を適切に決めるだけで価格の最大値が…

問題リンク 解説 動的計画法を適切に高速化する問題です。 を、 番目の階段に来る方法の総数とします。 を求めるとき、どこの階段からここまで上ってこられるかを考える。これは、尺取り法や二分探索を使えば高速に求められます。 そのような段のうち最も低…