問題リンク 細部が詰められなかったので解説の方法でACしてしまったが、あとで落ち着いて詰め直したらできた。 自分の解法は解説の方法より（実装は面倒だが）直感的だと思うので、紹介しておく。 問題概要 長さ の数列があって、異なる2要素を選んでそれぞ…

30秒眺めただけで解けた。全力でイキっていきたい。 問題リンク 問題概要 長さ の円環上に蟻が 匹いて、ある向きを向いている。蟻は向いている向きに一定の速度で進んでいき、他の蟻とぶつかるとそれぞれ向きを変えて進み始める。 秒後にそれぞれの蟻がいる…

書いた class BIT { unsigned int n; std::vector<lint> bit; public: BIT(unsigned int n) :n(n) { bit.resize(n + 1, 0); } void add(int a, lint x) { while (a <= n) { bit[a] += x; a += a & -a; } } lint query(int a) { lint cnt = 0; while (a > 0) { cnt </lint>…

問題リンク 問題概要 木があって、頂点には値が割り振られている。 葉を2つ選んでその間のパスの頂点の値をインクリメントする、という操作を、最初全部値が0の状態から始めてこの状態を構成できるか。 解説 頂点ベースではなく、辺ベースで考えると、ある葉…

マジで何やっても解けねえ 問題リンク 問題概要 略 考察 とりあえず式変形をして添字ごとでまとめると、結局 を計算して、かけて だったらダメ、という条件になる。 が のときには定義できないが、これは別にして計算できるのでまあどうにかなる。 さて、こ…

ネタを思いついたので、書きます。 「うちのオカンがね、好きなWriterがいるらしいんやけど、その名前をちょっと忘れたらしくてね」 「Writerの名前忘れてもうて、どうなってんねんそれ」 「でもね、オカンの好きなWriterなんて、touristか、双子ぐらいやろ…

問題リンク 結構面白かったので、解説を。 解説 まず、 のときは、経過時間が指数関数的に増加していくことに気がつく必要がある。 これで、であるような店は高々 個以内に収まることがわかる。 であるような店は、明らかに最後にまとめて訪れるのが良いので…

マラソン問題なので、したアプローチなどを記してみる。 問題概要 以上 以下の整数を100個、それらの約数の和集合の大きさが最大になるように出力せよ。 考察 約数の個数が多いといえば、高度合成数が思い浮かぶ。 ちょうどいい高度合成数に、大きめの素数を…

AtCoder社のアルゴリズム実技検定 第二回の問題を全部解いてみた。 感想をはさみながら解説をする。 今回はバチャ形式で一気に解いたので、時間も記しておく。 A問題 2:42 やるだけ、条件分岐して和か差。 B問題 4:54 std::countを使うと楽。やるだけ。 C問…

AtCoder社のアルゴリズム実技検定 第一回の問題を全部解いてみた。 感想をはさみながら解説をする。 A問題 PASTだけに普段よりは実務的な問題って感じがする。やるだけ。 入力例もどことなく実務を意識している感じがある。（アルファベットの入った文字列を…

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を用いて、ある都市から通信できる都市に印をつけることで、光ファイバー網で結ば…

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