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

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

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

問題リンク 解説 まず、順位を決める対象となる国の成績が確定していなかった場合、その成績をどう決めるか考える。 これは、その国の成績とできる点数の最大値でない場合を考えると、これを最大値と交換しても決して損しないので、なるべく最大値を取れば良…

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

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

問題リンク 解説 初歩的な動的計画法の問題です。 を、 行目かつ 列目のマスにいる状態とし、残り2つの添字で「どちらの方向から来たか、次に曲がれるか」を保持します。 この動的計画法を と の昇順で回すことで解けます。 このように、典型的な動的計画法…

問題リンク 典型寄せ集めみたいな問題 解説 まず、道の本数が高々 本なので、作れる道を列挙できれば、クラスカル法で空港の数と道のコストの組を計算できる。 空港の建設コストは会社ごとに異なるので、これを変数だと考えると、上に挙げた組は一次関数にな…

問題リンク 解説 要素が複数あるクエリ問はとりあえず1要素ソートするのが基本。 たぶんどっちをソートしても解けるが、今回は直径を降順ソートした。 クエリとマトリョーシカの追加を合わせてソートすれば、直径についての条件を考える必要はなくなる。 次…

だるかったので高速化したら通った 問題リンク 解法 とりあえず交点を求めてダイクストラしたいおきもちになるが、めんどくさいので愚直なダイクストラを書いてみる。 路線と場所ごとに距離を持たなければいけないが、これは unordered_map を使うのが最適（…

問題リンク 解説 問題の要旨を見ればわかると思いますが、すべての注文について、「どの店が一番注文先に近いか」を求めることができればよいです。 円環なので少し実装が煩雑になりますが、これは店の位置をソートして二分探索してやればよいです。 ここか…

問題リンク 解説 動的計画法の問題です。 たとえば、 を 日目に、前日店 で買い物をし、そこでは 日連続で買い物をしている、という場合の最小の合計金額とすると、 で解くことができます。 このように、最終的な最適解が、条件を絞れば途中まででも必ず最適…

問題リンク 解説 蟻本にもほぼ同じ問題が載っていることで有名です。 解法の説明はおそらくそちらの方が詳しいので、そちらを参照していただければ良いと思います。 2本の矢を投げて作れる点数を で列挙しソートしたあとに、それらを探索しながら「和が を超…

問題リンク 解説 問題文中にもあるように、 が小さいことを利用します。 まず、行の裏返し方を全探索した上で、列の裏返し方を考えます。 行の裏返し方が決まっていれば、各列について、裏返すべきかそうでないかは一意に定まります。表になるおせんべいが多…

問題リンク 解説 難易度5の中では考察寄りな問題です。 結論から言うと、「座標と熟すまでの時間の和の最大値」と、「座標の最大値の2倍」のうち大きいほうが答えになります。 以下に証明を示します。このような問題の証明を考えるのは、より難しい問題を解…

問題リンク 解説 累積和の典型的な問題です。 まず、宝石の位置を固定すると解きやすくなる、というのは感覚的に明らかでしょう。オーブと金塊のあるべき位置の条件が定まるからです。 結局、宝石を決めたとき、その右側にオーブが何個あるか、下に金塊が何…

問題リンク 解説 まず、B が残すカードは、山の中の連続する部分列だということがわかる。このようなものは 個ある。 これらすべてについて、A からカードを取ることで作れるか判定すればよいが、これは となってしまい、間に合わない。 B の残すカードの列…

問題リンク 解説 まず、トッピングの個数を固定することを考えます。トッピングの個数が一定なら、カロリーを高いものから貪欲に選んでいくのが当然最適です。 そこで、トッピングの個数を決め打ちして最大の1ドルあたりのカロリー数を計算し、最大のものを…

問題リンク 解説 調べなければいけない長方形が多いので、それぞれの長方形について高速にクエリを処理する必要があります。 これは、二次元累積和を使って、それぞれの種類のブロックが、1頂点を左上の端などに固定した長方形 通りの中にいくつかあるかを高…

問題リンク 解説 愚直にシミュレーションすることを考えると、時間計算量は になって、間に合いません。 毎日の移動で、区間の和をひとつずつ足して計算するのは無駄なので、累積和を使って高速化すると、計算量を にすることができます。 また、毎日の移動…

問題リンク 解説 まずは、どのような場合にICカードを買えばいいか考えましょう。 当たり前ですが、「買った方が安くなる場合」に買う方がよいです。 よって、それぞれの鉄道について、「買った方が安いか」を判定できればよい、ということになります。 この…

問題リンク 解説 基本的な動的計画法の問題です。 を、 日目に 番目の都市にいるときの、そこまでの疲労度の最小値とします。 疲労度は場所と日付がわかれば計算でき、次の都市にしか遷移しないので、このDPは で遷移し、時間計算量は となります。 出題当時…

問題リンク 解説 基本的な動的計画法の問題です。 を、 日目までで、 日目に 番目の服を着た時の、派手さの絶対値の合計の最大値、とします。 遷移は、前の日の服と今日着る服がわかっていればできるので、今日着る服を決めることで合計 になります。 この問…

問題リンク 解説 基本的な動的計画法の問題です。 を、 日目までで、2日前に食べたパスタの種類が , 最後に食べたパスタの種類が のときの、 日目までのパスタの選び方の総数として遷移します。 遷移は自分で考えてみましょう。 本選を目指すなら15分以内に…

問題リンク 解説 基本的な動的計画法（DP）の問題です。 式の 項目までで、値が になるような式の個数を として遷移していきます。 遷移式は簡単なので自分で考えてみましょう。 このような数え上げDPでは、「同一視できる状態をすべてうまく同一視する」と…

問題リンク 解説 この問題は、DFSで経路を列挙することで解くことができます。 DFSについては、けんちょんさんの記事を参照してください。 経路の総数が20万通りを超えないことが問題文で保証されているので、適当にDFSをして経路を列挙し、その中で最も長い…

問題リンク 解説 ねずみは、硬さの小さい順にチーズを食べていくので、あるチーズを食べたあと、次のチーズがある場所への最短経路がわかれば、これらの経路をつなげたものが答えとなります。 このような二次元のグリッド上で最短経路問題を解くには、BFS（…

問題リンク 解説 この問題は、LCS（Longest Common Substring）という有名問題です。 具体的には、次のような動的計画法（DP）をします。 を、「一つ目の文字列で 文字目、二つ目で 文字目まででのLCSの最大の長さ」とします。 このとき、遷移式は次のように…

問題リンク 解説 典型的な最短経路問題です。 最短経路問題については、この記事で包括的に扱っています。 この問題は、ダイクストラ法を用いて で解くことができます。 ただし、ほとんどのテストケースでは最悪計算量がかかることがないため、余裕をもって…

問題リンク 解説 DFSやBFSというテクニックを使います。 次の記事が参考になると思います。 けんちょんさんの記事 けんちょんさんの記事2 kaageの記事 この問題では、DFSやBFSを用いて、ある都市から通信できる都市に印をつけることで、光ファイバー網で結ば…