情報オリンピックの過去問には教育的な問題が多いです。 この記事で情報オリンピックの解説を集約し、予選/本選対策に役立つようにします。 パ研での新入生教育の一環も兼ねて、「JOIの問題で教育的なものについて解説を書いて集約する」という試みをします…

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

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

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

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

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

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

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

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

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

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

問題リンク 解説 二次元累積和というテクニックを使います。 二次元累積和については、けんちょんさんの記事を参照してください。 二次元累積和を使うと、「ある長方形領域に人が住んでいるか」と、「住んでいない場合、買収にかかるコストはいくらか」を で…