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

hamayanhamayan's blog

2022-04-01から1ヶ月間の記事一覧

Index Trio [モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249) D]

https://atcoder.jp/contests/abc249/tasks/abc249_d 前提知識 約数列挙 解説 https://atcoder.jp/contests/abc249/submissions/31211388 とある数xの約数列挙をO(sqrt(x))で行う方法がある。 もし分からない場合は「約数列挙」あたりで検索して、勉強してく…

Just K [モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249) C]

https://atcoder.jp/contests/abc249/tasks/abc249_c 前提知識 bit全列挙 解説 https://atcoder.jp/contests/abc249/submissions/31208645 この問題ではbit全列挙が分かっているとスムーズに解くことができる。 bit全列挙については、他に詳しい解説があるの…

Keep Connect [ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) F]

https://atcoder.jp/contests/abc248/tasks/abc248_f 前提知識 (連結DP) 解説 https://atcoder.jp/contests/abc248/submissions/31047647 全くメジャーな言い回しではないが、連結DPをする。 ただ単に連結性を状態として持つDP。 一般にこの手のDPでは行列…

K-colinear Line [ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) E]

https://atcoder.jp/contests/abc248/tasks/abc248_e 解説 https://atcoder.jp/contests/abc248/submissions/31046558 幾何問題。 以下解法、非常に面倒なので、別の解法があるかも… (解法に移る前に) 以下のケースでちょっとはまったので、WAではまってる…

Range Count Query [ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) D]

https://atcoder.jp/contests/abc248/tasks/abc248_d 前提知識 二分探索 解説 https://atcoder.jp/contests/abc248/submissions/31044881 色々な解法が見える問題。 実際WaveletMatrixというデータ構造を使えば、一瞬で答えが出るのだが、二分探索解法で説明…

Dice Sum [ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) C]

https://atcoder.jp/contests/abc248/tasks/abc248_c 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc248/submissions/31043632 この問題では動的計画法を用いて、答えを作成していく。 動的計画法の入門の次の一手くらいの問題なので、全く分か…

Bishop 2 [AtCoder Beginner Contest 246 E]

https://atcoder.jp/contests/abc246/tasks/abc246_e 前提知識 拡張ダイクストラ 解説 https://atcoder.jp/contests/abc246/submissions/30681205 問題文とはxとyの解釈を逆にして説明している。 好みの問題ではあるのだが、つまり、チェス盤の上からy行目、…

2-variable Function [AtCoder Beginner Contest 246 D]

https://atcoder.jp/contests/abc246/tasks/abc246_d 前提知識 二分探索 解説 https://atcoder.jp/contests/abc246/submissions/30680524 なかなか難しいというか、競プロ的なアプローチを含んだ問題。 二分探索が分かっていない場合はそちらを先に学習して…