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

hamayanhamayan's blog

競技プログラミング

Max Sum Counting [AtCoder Beginner Contest 216 F]

https://atcoder.jp/contests/abc216/tasks/abc216_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc216/submissions/25449760 DPが分かっていることは前提なので勉強してきてほしい。 何から始めるのか 手がつかない場合は問題の弱点を探るのが…

Amusement Park [AtCoder Beginner Contest 216 E]

https://atcoder.jp/contests/abc216/tasks/abc216_e 解説 https://atcoder.jp/contests/abc216/submissions/25449841 この問題は貪欲法で解ける。 勉強熱心な方はDPを思いついたかもしれないが、たぶん正常な反応だと思う。 貪欲法で解けそうな問題が実際は…

Pair of Balls [AtCoder Beginner Contest 216 D]

https://atcoder.jp/contests/abc216/tasks/abc216_d 解説 https://atcoder.jp/contests/abc216/submissions/25449941 貪欲法というかシミュレーションで解く問題。 今回は目標を達成するには、ボールが取り出せるならどんな順番でもいいので取り出していっ…

Many Balls [AtCoder Beginner Contest 216 C]

https://atcoder.jp/contests/abc216/tasks/abc216_c 関連知識 構築問題 解説 https://atcoder.jp/contests/abc216/submissions/25449969 この問題は2進法についての理解があると解法が思いつきやすい。 このような構築問題は方針がいくつかあるが、Nを見る…

倉庫番ロボット [パソコン甲子園2020 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0436 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0436/review/5811448/hamayanhamayan/C++14 解くのにかなり手こずった。難しかった。 ちょっとだけ遠回りも記しておこう。 …

高速道路網 [パソコン甲子園2020 予選 H]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0435 前提知識 トポロジカルソート 動的計画法 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0435/review/5811215/hamayanhamayan/C++14 まずは問題の整理をしていく。 与えら…

加工機 [パソコン甲子園2020 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0434 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0434/review/5811086/hamayanhamayan/C++14 シミュレーション高速化していく問題となる。 加工後の高さをもっていきながら…

One More aab aba baa [AtCoder Beginner Contest 215 C]

https://atcoder.jp/contests/abc215/tasks/abc215_c 解説 https://atcoder.jp/contests/abc215/submissions/25247677 今回要求されている問題を実装できるかという問題となる。 前半と後半でやればいい。 文字列Sの各文字を並べ替えて作ることが可能な文字…

Coprime 2 [AtCoder Beginner Contest 215 D]

https://atcoder.jp/contests/abc215/tasks/abc215_d 解説 https://atcoder.jp/contests/abc215/submissions/25246926 始めてこういう系統の問題を見る人は何から手を付けていいか分からないだろう。 gcdをして1になる数は基本的には互いに素である数となる…

Chain Contestant [AtCoder Beginner Contest 215 E]

https://atcoder.jp/contests/abc215/tasks/abc215_e 前提知識 bitDP 解説 https://atcoder.jp/contests/abc215/submissions/25245742 この問題はbitDPの応用問題となる。 とりあえずmod数え上げなので、DPがまず第一候補として挙がってくる。 コンテストの…

Dist Max 2 [AtCoder Beginner Contest 215 F]

https://atcoder.jp/contests/abc215/tasks/abc215_f 前提知識 二分探索 尺取り法 (セグメントツリー、SparseTable) 解説 https://atcoder.jp/contests/abc215/submissions/25244049 二分探索と尺取り法の知識はこれ以降の解説を理解するのに必須であるので…

テトラへドロン [パソコン甲子園2020 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0433 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0433/review/5788439/hamayanhamayan/C++14 かなり複雑な問題で何から手を付けたものかという感じだと思うが、規則性を見つ…

写真の回転 [パソコン甲子園2019 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0432 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0432/review/5788072/hamayanhamayan/C++14 若干の高速化は含まれるが、大体は実装問題である。 盤面の回転処理を実装する…

カラフル円盤通し [パソコン甲子園2020 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0431 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0431/review/5787948/hamayanhamayan/C++14 問題で要求されている問題をさばいていこう。 要求されている事項をプログラム…

あいさつまわり [パソコン甲子園2020 予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0430 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0430/review/5787700/hamayanhamayan/C++14 今回の問題はどういう順番で家を訪ねていくかというのを考えていくものであるが…

商店街へのお出かけ [パソコン甲子園2020 予選 B]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0429 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0429/review/5787654/hamayanhamayan/C++14 与えられた判定問題を実装していく、実装問題となる。 条件をプログラムに落と…

緯度経度 [パソコン甲子園2020 予選 A]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0428 解説 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0428/review/5787569/hamayanhamayan/C++14 基本的な入出力を問うような問題。 競技プログラミングを始めるには、言語を決…

Substrings [AtCoder Beginner Contest 214 F]

https://atcoder.jp/contests/abc214/tasks/abc214_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc214/submissions/25062984 今回の問題は部分列DPを見たことが無いと難しいかもしれない。 こちらを理解しておくことで、今回の問題をスムーズ…

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 問題で言われている条件をそれぞれ判定して実装しよう。 入力が数として与えられるので整数型で保持したくなるが、 今回の問題では桁に分…