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

hamayanhamayan's blog

競技プログラミング

Digits Paradise in Hexadecimal [AtCoder Beginner Contest 194 F]

https://atcoder.jp/contests/abc194/tasks/abc194_f 前提知識 桁DP 解説 https://atcoder.jp/contests/abc194/submissions/20736872 この問題は桁DPで解く。 なお、桁DPが初見という人は他のオーソドックスな問題を先に解くことをお勧めする。 桁DP 以下の…

Mex Min [AtCoder Beginner Contest 194 E]

https://atcoder.jp/contests/abc194/tasks/abc194_e 前提知識 二分探索 (しゃくとり法みたいな考え方) 解説 https://atcoder.jp/contests/abc194/submissions/20735986 二分探索としゃくとり法っぽい考え方を使用して問題を解く。 ちなみにmexという関数…

Journey [AtCoder Beginner Contest 194 D]

https://atcoder.jp/contests/abc194/tasks/abc194_d 前提知識 競技プログラミングにおける確率・期待値問題 - はまやんはまやんはまやん 「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」 解説 https://atcoder.jp/conte…

Squared Error [AtCoder Beginner Contest 194 C]

https://atcoder.jp/contests/abc194/tasks/abc194_c 前提知識 主客転倒テク 解説 https://atcoder.jp/contests/abc194/submissions/20735087 言ってるの自分と物理好きさんだけかもしれないんだけれど、主客転倒テクを使う。 今回の問題はAの全組合せに対し…

Job Assignment [AtCoder Beginner Contest 194 B]

https://atcoder.jp/contests/abc194/tasks/abc194_b 解説 https://atcoder.jp/contests/abc194/submissions/20734525 競技プログラミングの基本である、考えうる組合せの全探索を行おう。 今回は、仕事Aと仕事Bをどの従業員に割り当てるかという部分を全探…

I Scream [AtCoder Beginner Contest 194 A]

https://atcoder.jp/contests/abc194/tasks/abc194_a 解説 https://atcoder.jp/contests/abc194/submissions/20734346 実装問題。 与えられた問題を理解して、コードに落とし込もう。 時に競技プログラミングの問題は1文字変数を使って説明されることがある…

Potion [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) F]

https://atcoder.jp/contests/abc192/tasks/abc192_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc192/submissions/20347402 DPで解くが、考察の流れは分かりにくいかもしれない。 どこから考え始めるか 色々な可能性から攻めていくが、問題の…

Train [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) E]

https://atcoder.jp/contests/abc192/tasks/abc192_e 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/abc192/submissions/20346183 ダイクストラ法で解く。 ダイクストラから少ししか変更がないので、ダイクストラを一通り勉強した後の1up問題とし…

Base n [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) D]

https://atcoder.jp/contests/abc192/tasks/abc192_d 前提知識 二分探索 解説 https://atcoder.jp/contests/abc192/submissions/20345441 誤読してしまったが、それもまた競プロなので問題を責めるべきではない。 場合分け 例えば、X=1, M=10の場合はどのよ…

Kaprekar Number [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) C]

https://atcoder.jp/contests/abc192/tasks/abc192_c 解説 https://atcoder.jp/contests/abc192/submissions/20344221 なかなか複雑な問題に見えるが、問題文に書かれていることをシミュレートすれば通る。 この辺のどこから深く考えるかというのはスピード…

uNrEaDaBlE sTrInG [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) B]

https://atcoder.jp/contests/abc192/tasks/abc192_b 解説 https://atcoder.jp/contests/abc192/submissions/20343662 各文字毎に奇数番目、偶数番目で判定していく。 C++であれば、判定はasciiコードを使用した判定方法を使うのがフルスクラッチでやるには…

Star [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) A]

https://atcoder.jp/contests/abc192/tasks/abc192_a 解説 https://atcoder.jp/contests/abc192/submissions/20343316 100で割った余りを使用するのが簡単な解法。 100で割った余りを計算すると、小さい方で一番近い100の倍数との差が得られる。 求めたいの…

競技プログラマーのブログをまとめてみた

この記事は、Competitive Programming (1) Advent Calendar 2020 - Adventarの22日目の記事です。 前日はskyaozoraさんの10年間の競プロAdventCalenderの記事を振り返るです。 過去記事はこちらです。 2019年1 今年中に理解する!多項式、母関数、形式的べき…

Lamps [HHKB プログラミングコンテスト 2020 E]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_e 前提知識 主客転倒 二次元累積和 二分探索 解説 https://atcoder.jp/contests/hhkb2020/submissions/17319314 初めて見る人には何から手を付けるべきか分からない問題であるように思う。 2K通りをす…

Squares [HHKB プログラミングコンテスト 2020 D]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d 解説 https://atcoder.jp/contests/hhkb2020/submissions/17318367 色々な考察が必要で、方針もたくさん見えるような問題。 引くべき方針1「余事象」 今回は余事象を考えるとすっきりする。 つまり、…

Neq Min [HHKB プログラミングコンテスト 2020 C]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c 解説 https://atcoder.jp/contests/hhkb2020/submissions/17316773 こういったクエリ問題では、1クエリだけの場合ではどのように答えるかを考える。 i=Nの場合は? いずれとも等しくない値で、かつ、…

Futon [HHKB プログラミングコンテスト 2020 B]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_b 解説 https://atcoder.jp/contests/hhkb2020/submissions/17315225 布団を敷く可能性がある場所をすべて全探索することで答える。 横置きの場合 横置きする場合の布団を置く可能性がある場所は、横置…

Keyboard [HHKB プログラミングコンテスト 2020 A]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_a 解説 https://atcoder.jp/contests/hhkb2020/submissions/17314776 SがYであれば、Tに対して、大文字にする操作をするように実装する。 大文字にする操作は標準関数を使うか、場合分けして答えるのが…

Multiset Mean [AtCoder Regular Contest 104 D]

https://atcoder.jp/contests/arc104/tasks/arc104_d 解説 https://atcoder.jp/contests/arc104/submissions/17180396 何から始める? 簡潔な問題文だが、何から始めるべきだろうか。 平均の問題への取り組み方はいくつかあるが、平均を求めるには「個数」と…

Fair Elevator [AtCoder Regular Contest 104 C]

https://atcoder.jp/contests/arc104/tasks/arc104_c 解説 https://atcoder.jp/contests/arc104/submissions/17177990 条件の簡単化 まず、条件を少し簡単化していく。 エレベーターの階層を数直線上に考えて、ある人が乗り降りすることを区間として考えてみ…

DNA Sequence [AtCoder Regular Contest 104 B]

https://atcoder.jp/contests/arc104/tasks/arc104_b 解説 https://atcoder.jp/contests/arc104/submissions/17177217 まず、条件を簡単化できないかを考えてみる。 結論だけ書くと、T1とT2が相補的である条件の言い換えは「AとTが同数、かつ、CとGが同数」…

Plus Minus [AtCoder Regular Contest 104 A]

https://atcoder.jp/contests/arc104/tasks/arc104_a 解説 https://atcoder.jp/contests/arc104/submissions/17177438 A=X+Y B=X-Y なので、A+Bをすると2Xとなる。 よって、(A+B)/2をすると、Xが得られる。 YはA-Xを使って計算して、答える。 int A, B; //--…

Heights and Pairs [ACL Beginner Contest F]

https://atcoder.jp/contests/abl/tasks/abl_f 前提知識 包除原理 NTT 解説 https://atcoder.jp/contests/abl/submissions/17051729 この問題は複合的な知識が要求される。 順番に理解をしていこう。 包除原理? パッと見て包除原理感がある。 なんでやとい…

Replace Digits [ACL Beginner Contest E]

https://atcoder.jp/contests/abl/tasks/abl_e 前提知識 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/abl/submissions/17051206 ACLコンテストというのもあり、遅延評価セグメントツリーが真っ先に思いついた。 遅延評価セグメントツリーで…

Flat Subsequence [ACL Beginner Contest D]

https://atcoder.jp/contests/abl/tasks/abl_d 前提知識 区間maxセグメントツリー 解説 https://atcoder.jp/contests/abl/submissions/17050957 たぶん似たような解法をやったことが無いと、思いつくのは難しいかもしれない。 以下のような問題設定は見たこ…

Connect Cities [ACL Beginner Contest C]

https://atcoder.jp/contests/abl/tasks/abl_c 前提知識 UnionFind, DSU 解説 https://atcoder.jp/contests/abl/submissions/17050582 この問題設定をパッと見てUnionFindが真っ先に思い浮かんだので、途中考察がしにくいのだが、 都市と道路を頂点と無向辺…

Integer Preference [ACL Beginner Contest B]

https://atcoder.jp/contests/abl/tasks/abl_b 解説 https://atcoder.jp/contests/abl/submissions/17050220 [A,B]と[C,D]の区間のANDを取ったときに、残る区間があるかという問題。 区間のANDを取りたい場面は結構あって、以下の手法が役に立つ。 [A,B]と[C…

Repeat ACL [ACL Beginner Contest A]

https://atcoder.jp/contests/abl/tasks/abl_a 解説 https://atcoder.jp/contests/abl/submissions/17050136 K回"ACL"を繰り返す。 ループで回してACLをくっつけてから答えとして返せばいい。 おすすめしないが、ループを使わなくてもif文でごり押してもいい…

Keep Distances [ACL Contest 1 D]

https://atcoder.jp/contests/acl1/tasks/acl1_d 解説 https://atcoder.jp/contests/acl1/submissions/16924046 強実装問題。 クエリ問題は1クエリではどう解くかを考えよう まずは1つのクエリに対してどうやって解くかを考えていこう。 「よい集合の和集合…

Moving Pieces [ACL Contest 1 C]

https://atcoder.jp/contests/acl1/tasks/acl1_c 解説 https://atcoder.jp/contests/acl1/submissions/16923883 ACLコンテストということで、最小費用流が何とか出てきた。 ACLじゃなきゃ思いついていないかも。 最小費用流が分からない場合は、先にどこかで…