2020最新版競プロスラング用語集です。 「FFの競プロerが意味不明な単語を叫んでいてわからない！」 「界隈用語で溢れていて入っていけない！」という方、必見です。 ちょっと内輪ネタが入っているかもしれませんが、競プロ用語は全部内輪ネタみたいなものな…

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

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

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

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

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

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

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

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

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

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

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

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

解いた赤diffでは2問目。（1問目はReversing and Concatenating） 2種類のタイルの敷き詰めなので、片方の敷き詰め方だけ考えて、もう片方を敷ける場所がたくさん確保できるように最適化する、という方針で行った。 とりあえず横向きを敷き詰め終わった後の…

面白かったので解説を。 問題概要 グリッドがある。 グリッドの各マスにはいくつかのブロックが積んであり、これに対して次のような操作が行える。 隣り合っている マスを選び、ブロックを つずつ上に積む。 マスを選び、ブロックを つ積む。 この操作によっ…

3月に予定されていた、数理の翼伊計島セミナーが中止となり、数理の翼Nセミナーと名前を変えてオンライン開催となった。 参加した感想などをここに記す。 Day1 簡単な器材説明や、Zoomの使い方の確認があった。 そのあとはabc予想に関する話をちょっと聞いた…

第19回日本情報オリンピック春期トレーニング合宿に参加してきました。 Day1 集合は8:30で、少し渾身の懇親をした後、すぐに競技が始まりました。 どうでもいいですが、自分はこのような競技やテストの前には必ず特定のツイートをすることで知られています。…

第19回日本情報オリンピックの本選に参加してきました。(かなり経ちましたが、ここにもQiitaに書いたのをコピペして書き残しておきます。 日本情報オリンピックとは 日本中の中高生が国際情報オリンピックへの出場枠4つをかけて争う、国内最大の中高生のため…