https://atcoder.jp/contests/abc212/tasks/abc212_c 前提知識 二分探索, lower_bound 解説 https://atcoder.jp/contests/abc212/submissions/24696602 想定解法とは異なる解法ですが、達成したい目標は同じで、より高速化した解法が想定解法となります。 二…
![はてなブックマーク - Min Difference [AtCoder Beginner Contest 212 C]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/08/01/011957)
https://atcoder.jp/contests/abc212/tasks/abc212_b 解説 https://atcoder.jp/contests/abc212/submissions/24695908 問題で言われている条件をそれぞれ判定して実装しよう。 入力が数として与えられるので整数型で保持したくなるが、 今回の問題では桁に分…
![はてなブックマーク - Weak Password [AtCoder Beginner Contest 212 B]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/08/01/011855)
https://atcoder.jp/contests/abc211/tasks/abc211_e 前提知識 BFS 解説 https://atcoder.jp/contests/abc211/submissions/24516205 入力例3を見ると答えの最大数はあまり大きくないので、正しい候補を列挙すればよさそうに見える。 全探索だろうという方針…
![はてなブックマーク - Red Polyomino [AtCoder Beginner Contest 211 E]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/230238)
https://atcoder.jp/contests/past202107-open/tasks/past202107_i 前提知識 幾何問題 解説 https://atcoder.jp/contests/past202107-open/submissions/24478121 幾何問題である。複素数を使って座標を保持しながら、幾何的な操作を行っていくのがいい。 幾…
![はてなブックマーク - Nevus [第七回 アルゴリズム実技検定 I]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/205054)
https://atcoder.jp/contests/past202107-open/tasks/past202107_o 前提知識 動的計画法 累積和 priority_queue, multiset 解説 https://atcoder.jp/contests/past202107-open/submissions/24477460 最初の考察方針というのはだいぶパフォーマンスに影響する…
![はてなブックマーク - Computer [第七回 アルゴリズム実技検定 O]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/203806)
https://atcoder.jp/contests/past202107-open/tasks/past202107_n 前提知識 平面走査 座標圧縮 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/past202107-open/submissions/24475768 今回の問題は最低限遅延評価セグメントツリーを理解してい…
![はてなブックマーク - Monochrome Design [第七回 アルゴリズム実技検定 N]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/203706)
https://atcoder.jp/contests/past202107-open/tasks/past202107_m 前提知識 最小費用流 解説 https://atcoder.jp/contests/past202107-open/submissions/24472779 今回の問題は最小費用流が分かっていないと解けないので、どこかで学習してきてほしい。 最…
![はてなブックマーク - Divide [第七回 アルゴリズム実技検定 M]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/203547)
https://atcoder.jp/contests/past202107-open/tasks/past202107_l 前提知識 セグメントツリー 解説 https://atcoder.jp/contests/past202107-open/submissions/24471772 解法を思いつくのも難しいが、ならし計算量（償却計算量）も意識する必要があり、そこ…
![はてなブックマーク - Multiple Min Query [第七回 アルゴリズム実技検定 L]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/203450)
https://atcoder.jp/contests/past202107-open/tasks/past202107_k 前提知識 ダイクストラ 解説 今回の問題は無向グラフが与えられて頂点1から頂点Nへの最短距離で、かつ、満足度が最高のものを選択することが目的。 特に前半の「無向グラフが与えられて頂点…
![はてなブックマーク - Flying Trip [第七回 アルゴリズム実技検定 K]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/203348)
https://atcoder.jp/contests/past202107-open/tasks/past202107_j 前提知識 DAG判定、トポロジカルソート 解説 https://atcoder.jp/contests/past202107-open/submissions/24466589 問題を簡単化しよう 都市を頂点、道路を有向辺と捉えると、全体が有向グラ…
![はてなブックマーク - Never Ending Journey [第七回 アルゴリズム実技検定 J]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/203245)
https://atcoder.jp/contests/past202107-open/tasks/past202107_h 前提知識 動的計画法 解説 https://atcoder.jp/contests/past202107-open/submissions/24466156 多次元のDPをくみ上げていく。 問題設定的にはいかにもDPっぽいという感じではあるが、慣れ…
![はてなブックマーク - Line Chart [第七回 アルゴリズム実技検定 H]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/203047)
https://atcoder.jp/contests/past202107-open/tasks/past202107_g 解説 https://atcoder.jp/contests/past202107-open/submissions/24465845 何から始めるか このような構築問題は、慣れないうちは何から始めていいか分からないと思う。 とりあえずいくつか…
![はてなブックマーク - Power Expression [第七回 アルゴリズム実技検定 G]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/202945)
https://atcoder.jp/contests/past202107-open/tasks/past202107_f 解説 https://atcoder.jp/contests/past202107-open/submissions/24465658 判定を効率化する問題。 大変そうに見えるが、特に大きなひねりはなく、愚直に実装すれば間に合う。 慣れている人…
![はてなブックマーク - Double Booking [第七回 アルゴリズム実技検定 F]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/202824)
https://atcoder.jp/contests/past202107-open/tasks/past202107_e 解説 https://atcoder.jp/contests/past202107-open/submissions/24461067 この問題は勘がいい人だと3進数を利用したような問題だなと感じるかもしれない。 それが見えてれば比較的見通しの…
![はてなブックマーク - Aoki's Trick [第七回 アルゴリズム実技検定 E]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/202726)
https://atcoder.jp/contests/past202107-open/tasks/past202107_d 解説 https://atcoder.jp/contests/past202107-open/submissions/24466988 ちょっと考察、ちょっと実装の問題。 操作回数が最大となる操作 ここがまず1つ考察が必要な部分である。 今回は実…
![はてなブックマーク - Replace [第七回 アルゴリズム実技検定 D]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/202625)
https://atcoder.jp/contests/past202107-open/tasks/past202107_c 解説 https://atcoder.jp/contests/past202107-open/submissions/24460011 要求されている判定を行う実装問題。 自分の実装では色々な工夫をすることで、なるべく実装を減らしている。 まず…
![はてなブックマーク - Validation [第七回 アルゴリズム実技検定 C]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/202524)
https://atcoder.jp/contests/past202107-open/tasks/past202107_b 解説 https://atcoder.jp/contests/past202107-open/submissions/24459788 シミュレーション問題。 計算一本でも求めることができるが、言われているシミュレーションを動かすことでも求め…
![はてなブックマーク - Vapor Pressure [第七回 アルゴリズム実技検定 B]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/202423)
https://atcoder.jp/contests/past202107-open/tasks/past202107_a 解説 https://atcoder.jp/contests/past202107-open/submissions/24459496 シミュレーション問題。 問題で要求されていることを実装しよう。 まず、自分の実装ではコードを文字列で取り込ん…
![はてなブックマーク - check digit [第七回 アルゴリズム実技検定 A]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/24/202322)
https://atcoder.jp/contests/abc210/tasks/abc210_e 前提知識 クラスカル法(MST, 最小全域木) 解説 https://atcoder.jp/contests/abc210/submissions/24333006 題名にもあるように今回はMST,最小全域木を作ることが目的となっている。 上手く隠されているよ…
![はてなブックマーク - Ring MST [AtCoder Beginner Contest 210 E]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/17/233253)
https://atcoder.jp/contests/abc210/tasks/abc210_d 解説 https://atcoder.jp/contests/abc210/submissions/24331674 難しい問題。 なお、i,jをx,yと言い換えて説明している。 何から始めるか 問題の中で一番厄介な部分が絶対値であり、これをどうしようか…
![はてなブックマーク - National Railway [AtCoder Beginner Contest 210 D]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/17/233152)
https://atcoder.jp/contests/abc210/tasks/abc210_c 前提知識 尺取り法 解説 https://atcoder.jp/contests/abc210/submissions/24333038 色々解法があるが、特別なデータ構造が必要ないのは尺取り法（正確にはっぽいアルゴリズム）だろう。 この問題は尺取…
![はてなブックマーク - Colorful Candies [AtCoder Beginner Contest 210 C]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/17/233052)
https://atcoder.jp/contests/abc210/tasks/abc210_b 解説 https://atcoder.jp/contests/abc210/submissions/24333088 シミュレーションして勝敗を決していこう。 先頭から順番に、高橋君、青木君の順番でカードを見ていき悪いカードを受け取った人が負けな…
![はてなブックマーク - Bouzu Mekuri [AtCoder Beginner Contest 210 B]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/17/232949)
https://atcoder.jp/contests/abc210/tasks/abc210_a 解説 https://atcoder.jp/contests/abc210/submissions/24333120 場合分けして問題を解こう。 状況が変わる条件はキャベツをA個以下買うか、A個よりも多く買うかである。 キャベツをA個以下買う場合はす…
![はてなブックマーク - Cabbages [AtCoder Beginner Contest 210 A]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/17/232848)
https://atcoder.jp/contests/abc209/tasks/abc209_f 前提知識 挿入DP 累積和によるDP高速化 解説 https://atcoder.jp/contests/abc209/submissions/24159889 mod109+7で制約をみてみると、dp[N][N]的な感じかなとまずよぎる。 色々整理していこう。 最適動…
![はてなブックマーク - Deforestation [AtCoder Beginner Contest 209 F]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/11/154241)
https://atcoder.jp/contests/abc209/tasks/abc209_e 前提知識 後退解析（ゲーム問題） 解説 https://atcoder.jp/contests/abc209/submissions/24158002 ゲーム問題は手法が限られているので、なにも思いつかない場合はとりあえず全部の手法を1つずつ試して…
![はてなブックマーク - Shiritori [AtCoder Beginner Contest 209 E]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/11/154140)
https://atcoder.jp/contests/abc209/tasks/abc209_d 前提知識 LCA 解説 https://atcoder.jp/contests/abc209/submissions/24156786 この問題はアルゴリズム力が要求される問題。 何が分かれば問題が解けるかという所から考えていく。 なお、想定解法は全然…
![はてなブックマーク - Collision [AtCoder Beginner Contest 209 D]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/11/154020)
https://atcoder.jp/contests/abc209/tasks/abc209_c 前提知識 modつき計算 解説 https://atcoder.jp/contests/abc209/submissions/24156090 問題をそのまま受け取ると難しい問題。 mod 109 + 7での計算ができることが前提条件。 とりあえず解きたい場合はAC…
![はてなブックマーク - Not Equal [AtCoder Beginner Contest 209 C]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/11/153920)
https://atcoder.jp/contests/abc209/tasks/abc209_b 解説 https://atcoder.jp/contests/abc209/submissions/24155585 問題で指定されているように偶数番目の商品は定価の1円引きで購入して、奇数番目の商品は定価通りで購入したとして 合計金額を計算してい…
![はてなブックマーク - Can you buy them all? [AtCoder Beginner Contest 209 B]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/11/153823)
https://atcoder.jp/contests/abc209/tasks/abc209_a 解説 https://atcoder.jp/contests/abc209/submissions/24155463 制約を見るとA≦Bが保証されていないので、それに気を付ける必要がある。 普通にA～Bでループを回せば、A≦Bでない場合はループが回らない…
![はてなブックマーク - Counting [AtCoder Beginner Contest 209 A]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/11/153720)
https://atcoder.jp/contests/abc208/tasks/abc208_e 前提知識 桁DP 解説 https://atcoder.jp/contests/abc208/submissions/23995133 桁DPの知識が必要になる。 桁DPに慣れていれば真っ先に桁DPが思い浮かびそうな問題設定であるので、 もし知らない場合は桁…
![はてなブックマーク - Digit Products [AtCoder Beginner Contest 208 E]](https://b.hatena.ne.jp/entry/image/https://blog.hamayanhamayan.com/entry/2021/07/05/013342)