はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミング

Sum of Maximum Weights [AtCoder Beginner Contest 214 D]

https://atcoder.jp/contests/abc214/tasks/abc214_d 前提知識 (主客転倒) UnionFind 解説 https://atcoder.jp/contests/abc214/submissions/25065159 見た目はかなり難しい。 方針が分かれば実装はかなり簡単で済むのだが、考え方は難しい。 何がモチベー…

Distribution [AtCoder Beginner Contest 214 C]

https://atcoder.jp/contests/abc214/tasks/abc214_c 解説 https://atcoder.jp/contests/abc214/submissions/25034924 今回の問題は少し制約を緩めたものから考えるのがよい。 円周上というのをやめて一直線上で動けるということを考えることにすると、 解法…

How many? [AtCoder Beginner Contest 214 B]

https://atcoder.jp/contests/abc214/tasks/abc214_b 解説 https://atcoder.jp/contests/abc214/submissions/25065793 今回の問題は枝刈り全探索という方針を用いる。 全探索をしていくのだが、自明な「枝刈り」、つまり、探索を途中でストップすることで、 …

Common Prefixes [AtCoder Beginner Contest 213 F]

https://atcoder.jp/contests/abc213/tasks/abc213_f 前提知識 Suffix Array, LCP 解説 https://atcoder.jp/contests/abc213/submissions/24898387 Suffix ArrayとLCPの知識が無ければ、まず解くことはできない。 以下で軽く説明するが、他方で勉強する方が…

Stronger Takahashi [AtCoder Beginner Contest 213 E]

https://atcoder.jp/contests/abc213/tasks/abc213_e 前提知識 ダイクストラ 01-BFSの方が計算量がいいです(想定解) 解説 https://atcoder.jp/contests/abc213/submissions/24896937 確かに01BFSで解けるというか、まんまですね… 最終的な最短距離を求める…

Takahashi Tour [AtCoder Beginner Contest 213 D]

https://atcoder.jp/contests/abc213/tasks/abc213_d 前提知識 dfs 解説 https://atcoder.jp/contests/abc213/submissions/24895917 今回の問題はDFSというか、オイラーツアーというかという問題。 とにかく木上での深さ優先探索ができるなら解ける問題。 何…

Reorder Cards [AtCoder Beginner Contest 213 C]

https://atcoder.jp/contests/abc213/tasks/abc213_c 前提知識(というかそのもの) 座標圧縮 解説 https://atcoder.jp/contests/abc213/submissions/24895309 今回の問題は座標圧縮という典型アルゴリズムの実装を要求されている。 座標圧縮を理解すれば、…

Greedy Takahashi [AtCoder Beginner Contest 212 F]

https://atcoder.jp/contests/abc212/tasks/abc212_f 前提知識 ダブリング 解説 https://atcoder.jp/contests/abc212/submissions/24698572 最終的にはダブリングを使用して解く。 ダブリングについては説明しないので、どこかで学習してきてほしい。 重要性…

Safety Journey [AtCoder Beginner Contest 212 E]

https://atcoder.jp/contests/abc212/tasks/abc212_e 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc212/submissions/24697855 難しくなってくる。今回の問題はまずDPが分かっていることは前提で、その上で高速化をしていく必要がある。 なぜDP…

Querying Multiset [AtCoder Beginner Contest 212 D]

https://atcoder.jp/contests/abc212/tasks/abc212_d 前提知識 priority_queueなど 解説 https://atcoder.jp/contests/abc212/submissions/24696926 今回の問題は、以下のような条件を持つデータ構造を使える、持っていることが解くために必要なこととなる。…

Min Difference [AtCoder Beginner Contest 212 C]

https://atcoder.jp/contests/abc212/tasks/abc212_c 前提知識 二分探索, lower_bound 解説 https://atcoder.jp/contests/abc212/submissions/24696602 想定解法とは異なる解法ですが、達成したい目標は同じで、より高速化した解法が想定解法となります。 二…

Weak Password [AtCoder Beginner Contest 212 B]

https://atcoder.jp/contests/abc212/tasks/abc212_b 解説 https://atcoder.jp/contests/abc212/submissions/24695908 問題で言われている条件をそれぞれ判定して実装しよう。 入力が数として与えられるので整数型で保持したくなるが、 今回の問題では桁に分…

Red Polyomino [AtCoder Beginner Contest 211 E]

https://atcoder.jp/contests/abc211/tasks/abc211_e 前提知識 BFS 解説 https://atcoder.jp/contests/abc211/submissions/24516205 入力例3を見ると答えの最大数はあまり大きくないので、正しい候補を列挙すればよさそうに見える。 全探索だろうという方針…

Nevus [第七回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202107-open/tasks/past202107_i 前提知識 幾何問題 解説 https://atcoder.jp/contests/past202107-open/submissions/24478121 幾何問題である。複素数を使って座標を保持しながら、幾何的な操作を行っていくのがいい。 幾…

Computer [第七回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202107-open/tasks/past202107_o 前提知識 動的計画法 累積和 priority_queue, multiset 解説 https://atcoder.jp/contests/past202107-open/submissions/24477460 最初の考察方針というのはだいぶパフォーマンスに影響する…

Monochrome Design [第七回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202107-open/tasks/past202107_n 前提知識 平面走査 座標圧縮 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/past202107-open/submissions/24475768 今回の問題は最低限遅延評価セグメントツリーを理解してい…

Divide [第七回 アルゴリズム実技検定 M]

https://atcoder.jp/contests/past202107-open/tasks/past202107_m 前提知識 最小費用流 解説 https://atcoder.jp/contests/past202107-open/submissions/24472779 今回の問題は最小費用流が分かっていないと解けないので、どこかで学習してきてほしい。 最…

Multiple Min Query [第七回 アルゴリズム実技検定 L]

https://atcoder.jp/contests/past202107-open/tasks/past202107_l 前提知識 セグメントツリー 解説 https://atcoder.jp/contests/past202107-open/submissions/24471772 解法を思いつくのも難しいが、ならし計算量(償却計算量)も意識する必要があり、そこ…

Flying Trip [第七回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202107-open/tasks/past202107_k 前提知識 ダイクストラ 解説 今回の問題は無向グラフが与えられて頂点1から頂点Nへの最短距離で、かつ、満足度が最高のものを選択することが目的。 特に前半の「無向グラフが与えられて頂点…

Never Ending Journey [第七回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202107-open/tasks/past202107_j 前提知識 DAG判定、トポロジカルソート 解説 https://atcoder.jp/contests/past202107-open/submissions/24466589 問題を簡単化しよう 都市を頂点、道路を有向辺と捉えると、全体が有向グラ…

Line Chart [第七回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202107-open/tasks/past202107_h 前提知識 動的計画法 解説 https://atcoder.jp/contests/past202107-open/submissions/24466156 多次元のDPをくみ上げていく。 問題設定的にはいかにもDPっぽいという感じではあるが、慣れ…

Power Expression [第七回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202107-open/tasks/past202107_g 解説 https://atcoder.jp/contests/past202107-open/submissions/24465845 何から始めるか このような構築問題は、慣れないうちは何から始めていいか分からないと思う。 とりあえずいくつか…

Double Booking [第七回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202107-open/tasks/past202107_f 解説 https://atcoder.jp/contests/past202107-open/submissions/24465658 判定を効率化する問題。 大変そうに見えるが、特に大きなひねりはなく、愚直に実装すれば間に合う。 慣れている人…

Aoki's Trick [第七回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202107-open/tasks/past202107_e 解説 https://atcoder.jp/contests/past202107-open/submissions/24461067 この問題は勘がいい人だと3進数を利用したような問題だなと感じるかもしれない。 それが見えてれば比較的見通しの…

Replace [第七回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202107-open/tasks/past202107_d 解説 https://atcoder.jp/contests/past202107-open/submissions/24466988 ちょっと考察、ちょっと実装の問題。 操作回数が最大となる操作 ここがまず1つ考察が必要な部分である。 今回は実…

Validation [第七回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202107-open/tasks/past202107_c 解説 https://atcoder.jp/contests/past202107-open/submissions/24460011 要求されている判定を行う実装問題。 自分の実装では色々な工夫をすることで、なるべく実装を減らしている。 まず…

Vapor Pressure [第七回 アルゴリズム実技検定 B]

https://atcoder.jp/contests/past202107-open/tasks/past202107_b 解説 https://atcoder.jp/contests/past202107-open/submissions/24459788 シミュレーション問題。 計算一本でも求めることができるが、言われているシミュレーションを動かすことでも求め…

check digit [第七回 アルゴリズム実技検定 A]

https://atcoder.jp/contests/past202107-open/tasks/past202107_a 解説 https://atcoder.jp/contests/past202107-open/submissions/24459496 シミュレーション問題。 問題で要求されていることを実装しよう。 まず、自分の実装ではコードを文字列で取り込ん…

Ring MST [AtCoder Beginner Contest 210 E]

https://atcoder.jp/contests/abc210/tasks/abc210_e 前提知識 クラスカル法(MST, 最小全域木) 解説 https://atcoder.jp/contests/abc210/submissions/24333006 題名にもあるように今回はMST,最小全域木を作ることが目的となっている。 上手く隠されているよ…

National Railway [AtCoder Beginner Contest 210 D]

https://atcoder.jp/contests/abc210/tasks/abc210_d 解説 https://atcoder.jp/contests/abc210/submissions/24331674 難しい問題。 なお、i,jをx,yと言い換えて説明している。 何から始めるか 問題の中で一番厄介な部分が絶対値であり、これをどうしようか…