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

hamayanhamayan's blog

競技プログラミング

Interval Game 2 [AtCoder Beginner Contest 206(Sponsored by Panasonic) F]

https://atcoder.jp/contests/abc206/tasks/abc206_f 前提知識 grundy数 解説 https://atcoder.jp/contests/abc206/submissions/23623437 今回の問題はgrundy数を知らないとまず解けない。 解説範囲がとても広くなってしまうので、grundy数についてはどこか…

Divide Both [AtCoder Beginner Contest 206(Sponsored by Panasonic) E]

https://atcoder.jp/contests/abc206/tasks/abc206_e 前提知識 約数系包除原理 解説 https://atcoder.jp/contests/abc206/submissions/23623547 しょっぱなから発想の転換が必要な問題。 類題を多く解いているので、すぐ思いついたが、そうでないと難しい。 …

KAIBUNsyo [AtCoder Beginner Contest 206(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc206/tasks/abc206_d 前提知識 UnionFind 解説 https://atcoder.jp/contests/abc206/submissions/23624301 以下の解説は、この問題はUnionFindを知らないと理解は難しいので、どこかで学習してきてほしい。 UnionFindを知らな…

Swappable [AtCoder Beginner Contest 206(Sponsored by Panasonic) C]

https://atcoder.jp/contests/abc206/tasks/abc206_c 解説 https://atcoder.jp/contests/abc206/submissions/23625007 まず、i,jの組を全探索する方針があるが、これは9*1010通りとなるので間に合わない。 全探索系は107くらいが上限。 だが、片方だけ全探索…

Savings [AtCoder Beginner Contest 206(Sponsored by Panasonic) B]

https://atcoder.jp/contests/abc206/tasks/abc206_b 解説 https://atcoder.jp/contests/abc206/submissions/23625300 この問題は実は1日目から順番にシミュレートすれば間に合う。 200点問題ではあるが、ちょっと計算量について考え始めると心配になったり…

Maxi-Buying [AtCoder Beginner Contest 206(Sponsored by Panasonic) A]

https://atcoder.jp/contests/abc206/tasks/abc206_a 解説 https://atcoder.jp/contests/abc206/submissions/23625515 今回の問題で精度が要求されるかは分からないが、テクとして、小数計算は精度が心配だから、できるなら整数で計算するというものがある。…

Grid and Tokens [AtCoder Beginner Contest 205 F]

https://atcoder.jp/contests/abc205/tasks/abc205_f 前提知識 最大流 解説 https://atcoder.jp/contests/abc205/submissions/23457322 今回の問題は最大流問題に帰着できる。 パッと見て類題を思い出して、選択肢を考えていくと最大流で解法が思いつける。 …

White and Black Balls [AtCoder Beginner Contest 205 E]

https://atcoder.jp/contests/abc205/tasks/abc205_e 前提知識 カタラン数 解説 https://atcoder.jp/contests/abc205/submissions/23454802 この問題は類題を知っていれば解法は一瞬で思いつくが、知らないと一生解けない(少なくとも自分は…) この問題はカ…

Kth Excluded [AtCoder Beginner Contest 205 D]

https://atcoder.jp/contests/abc205/tasks/abc205_d 解説 https://atcoder.jp/contests/abc205/submissions/23456683 自分はクエリ先読みと尺取り法っぽく解いた。 考え方が思いついても実装も大変な問題。 クエリ先読みについてはモチベは簡単なので、軽く…

POW [AtCoder Beginner Contest 205 C]

https://atcoder.jp/contests/abc205/tasks/abc205_c 解説 https://atcoder.jp/contests/abc205/submissions/23456949 発想力が必要となる問題。 真面目に計算するのは精度的に無理なので、logか…?とも思ったがこちらも精度が心配で、300点っぽくない。 大…

Permutation Check [AtCoder Beginner Contest 205 B]

https://atcoder.jp/contests/abc205/tasks/abc205_b 解説 https://atcoder.jp/contests/abc205/submissions/23457038 問題を少し変えて考えてみる。 今回の判定問題は、与えられたAを並び替えて、1,2,3,...,Nになるかというのを考えても問題ない。 と考える…

kcal [AtCoder Beginner Contest 205 A]

https://atcoder.jp/contests/abc205/tasks/abc205_a 解説 https://atcoder.jp/contests/abc205/submissions/23457255 単位数である1mLを経由することで計算をしていく。 100 mL -> A kcal 1 mL -> A / 100 kcal B mL -> A / 100 * B kcal ということでA/100…

Hanjo 2 [AtCoder Beginner Contest 204 F]

https://atcoder.jp/contests/abc204/tasks/abc204_f 前提知識 bitDP 行列累乗を使ったDP高速化 解説 https://atcoder.jp/contests/abc204/submissions/23263864 今回の問題はとても難しいのだが、典型度は高い。 まず、制約がかなりとがっているので、何を…

Rush Hour 2 [AtCoder Beginner Contest 204 E]

https://atcoder.jp/contests/abc204/tasks/abc204_e 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/abc204/submissions/23263588 問題設定が有向グラフの最短経路問題なので、ダイクストラ法が最初に思いつく。 ダイクストラ法をもじって解くこ…

Cooking [AtCoder Beginner Contest 204 D]

https://atcoder.jp/contests/abc204/tasks/abc204_d 解説 https://atcoder.jp/contests/abc204/submissions/23262989 この問題はDPで解ける。 いかにDPで解くという所に帰着させるかを説明していこう。 まず、制約がとても小さい。 パッと見て貪欲で行けそ…

Tour [AtCoder Beginner Contest 204 C]

https://atcoder.jp/contests/abc204/tasks/abc204_c 前提知識 BFS 解説 https://atcoder.jp/contests/abc204/submissions/23261589 この問題では実装方針から正しく計算量を見積もれるかがポイントとなる。 計算量見積もりをして、オーダーで上限を当てはめ…

Nuts [AtCoder Beginner Contest 204 B]

https://atcoder.jp/contests/abc204/tasks/abc204_b 解説 https://atcoder.jp/contests/abc204/submissions/23260128 シミュレーションする問題。要求されていることを実装しよう。 それぞれの木の実について、 10以下であれば何もしない 10より大きいならA…

Rock-paper-scissors [AtCoder Beginner Contest 204 A]

https://atcoder.jp/contests/abc204/tasks/abc204_a 解説 https://atcoder.jp/contests/abc204/submissions/23259935 あいこになるのは全部同じか全部違う場合なので、その2つの状況で場合分けして答えることにしよう。 x=yであれば全部同じの場合なので、x…

Weed [AtCoder Beginner Contest 203(Sponsored by Panasonic) F]

https://atcoder.jp/contests/abc203/tasks/abc203_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc203/submissions/23075597 まずAはソートしておこう。 これはよくあるテクであるが、ソート可能な配列はソートしておく。 何に気付くべきか こ…

White Pawn [AtCoder Beginner Contest 203(Sponsored by Panasonic) E]

https://atcoder.jp/contests/abc203/tasks/abc203_e 解説 https://atcoder.jp/contests/abc203/submissions/23075564 計算を差分だけになるように気を付けながらポーンの場所を残しつつ、シミュレーションしていく問題。 ans := とあるx座標において、白の…

Pond [AtCoder Beginner Contest 203(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc203/tasks/abc203_d 前提知識 二分探索 二次元累積和 解説 https://atcoder.jp/contests/abc203/submissions/23075536 二分探索しよう。 始めてみる・慣れていない場合はピンとこないと思うが、最大値の最小値というのが二分…

Friends and Travel costs [AtCoder Beginner Contest 203(Sponsored by Panasonic) C]

https://atcoder.jp/contests/abc203/tasks/abc203_c 解説 https://atcoder.jp/contests/abc203/submissions/23075028 int N, K; vector<pair<ll, ll>> AB; //--------------------------------------------------------------------------------------------------- ll s</pair<ll,>…

AtCoder Condominium [AtCoder Beginner Contest 203(Sponsored by Panasonic) B]

https://atcoder.jp/contests/abc203/tasks/abc203_b 解説 https://atcoder.jp/contests/abc203/submissions/23075335 全ての階層、すべての部屋について全探索して間に合うので全探索しよう。 2重ループで2変数を使うのでごちゃごちゃにならないように注意…

Chinchirorin [AtCoder Beginner Contest 203(Sponsored by Panasonic) A]

https://atcoder.jp/contests/abc203/tasks/abc203_a 解説 https://atcoder.jp/contests/abc203/submissions/23075477 問題に書いてあることをそのまま実装した。 全部違うかどうかはsetを使って実装して、被っているものがあれば、どこが被っているかを比較…

Count Descendants [エイシングプログラミングコンテスト2021(AtCoder Beginner Contest 202) E]

https://atcoder.jp/contests/abc202/tasks/abc202_e 前提知識 オイラーツアー BIT クエリ先読みと水平走査 解説 https://atcoder.jp/contests/abc202/submissions/22837009 最後までの理解は難しいかもしれないが、問題の言い換え部分までは参考になるかも…

aab aba baa [エイシングプログラミングコンテスト2021(AtCoder Beginner Contest 202) D]

https://atcoder.jp/contests/abc202/tasks/abc202_d 解説 https://atcoder.jp/contests/abc202/submissions/22836918 辞書順に並び替えると、 a???????? b???????? の並びになっており、K番目ということを考えると、このどちらのグループに入るかということ…

Made Up [エイシングプログラミングコンテスト2021(AtCoder Beginner Contest 202) C]

https://atcoder.jp/contests/abc202/tasks/abc202_c 解説 https://atcoder.jp/contests/abc202/submissions/22836846 ちょっとだけ整理 今回の問題は、解く前にまずは整理することが重要である。 B[C[j]]の部分であるが、別途配列Dを考えて、単純にD[j] = B…

180° [エイシングプログラミングコンテスト2021(AtCoder Beginner Contest 202) B]

https://atcoder.jp/contests/abc202/tasks/abc202_b 解説 https://atcoder.jp/contests/abc202/submissions/22836805 シミュレーション問題。 問題で要求されていることを実装しよう。 自分の実装例について説明する。 反転する C++であればreverse関数を使…

Three Dice [エイシングプログラミングコンテスト2021(AtCoder Beginner Contest 202) A]

https://atcoder.jp/contests/abc202/tasks/abc202_a 解説 https://atcoder.jp/contests/abc202/submissions/22836615 abcについて反対側の面を計算(7-aのように)して総和を求めて答えよう。 特に注意点はないですね。 もし、この問題に詰まった場合は AtC…

Shortest Distance Query [第六回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202104-open/tasks/past202104_o 前提知識 木上での最短経路(LCA, ダブリング, HL分解…) 最短経路問題 解説 https://atcoder.jp/contests/past202104-open/submissions/22667026 最終問題。今までなかなか見たことがない難…