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

https://atcoder.jp/contests/abc210/tasks/abc210_c 前提知識 尺取り法 解説 https://atcoder.jp/contests/abc210/submissions/24333038 色々解法があるが、特別なデータ構造が必要ないのは尺取り法（正確にはっぽいアルゴリズム）だろう。 この問題は尺取…

https://atcoder.jp/contests/abc210/tasks/abc210_b 解説 https://atcoder.jp/contests/abc210/submissions/24333088 シミュレーションして勝敗を決していこう。 先頭から順番に、高橋君、青木君の順番でカードを見ていき悪いカードを受け取った人が負けな…

https://atcoder.jp/contests/abc210/tasks/abc210_a 解説 https://atcoder.jp/contests/abc210/submissions/24333120 場合分けして問題を解こう。 状況が変わる条件はキャベツをA個以下買うか、A個よりも多く買うかである。 キャベツをA個以下買う場合はす…

https://atcoder.jp/contests/abc209/tasks/abc209_f 前提知識 挿入DP 累積和によるDP高速化 解説 https://atcoder.jp/contests/abc209/submissions/24159889 mod109+7で制約をみてみると、dp[N][N]的な感じかなとまずよぎる。 色々整理していこう。 最適動…

https://atcoder.jp/contests/abc209/tasks/abc209_e 前提知識 後退解析（ゲーム問題） 解説 https://atcoder.jp/contests/abc209/submissions/24158002 ゲーム問題は手法が限られているので、なにも思いつかない場合はとりあえず全部の手法を1つずつ試して…

https://atcoder.jp/contests/abc209/tasks/abc209_d 前提知識 LCA 解説 https://atcoder.jp/contests/abc209/submissions/24156786 この問題はアルゴリズム力が要求される問題。 何が分かれば問題が解けるかという所から考えていく。 なお、想定解法は全然…

https://atcoder.jp/contests/abc209/tasks/abc209_c 前提知識 modつき計算 解説 https://atcoder.jp/contests/abc209/submissions/24156090 問題をそのまま受け取ると難しい問題。 mod 109 + 7での計算ができることが前提条件。 とりあえず解きたい場合はAC…

https://atcoder.jp/contests/abc209/tasks/abc209_b 解説 https://atcoder.jp/contests/abc209/submissions/24155585 問題で指定されているように偶数番目の商品は定価の1円引きで購入して、奇数番目の商品は定価通りで購入したとして 合計金額を計算してい…

https://atcoder.jp/contests/abc209/tasks/abc209_a 解説 https://atcoder.jp/contests/abc209/submissions/24155463 制約を見るとA≦Bが保証されていないので、それに気を付ける必要がある。 普通にA～Bでループを回せば、A≦Bでない場合はループが回らない…

https://atcoder.jp/contests/abc208/tasks/abc208_e 前提知識 桁DP 解説 https://atcoder.jp/contests/abc208/submissions/23995133 桁DPの知識が必要になる。 桁DPに慣れていれば真っ先に桁DPが思い浮かびそうな問題設定であるので、 もし知らない場合は桁…

https://atcoder.jp/contests/abc208/tasks/abc208_d 前提知識 （ワーシャルフロイド） 解説 https://atcoder.jp/contests/abc208/submissions/23994717 ワーシャルフロイドを正確に理解していれば解ける問題。 いや、この問題を理解することがワーシャルフ…

https://atcoder.jp/contests/abc208/tasks/abc208_c 解説 https://atcoder.jp/contests/abc208/submissions/23993957 シミュレーションを高速化することを考える。 今回は2段階で分配が行われる。 持っているお菓子がN個以上なら1個ずつおかしを配る N個未…

https://atcoder.jp/contests/abc208/tasks/abc208_b 解説 https://atcoder.jp/contests/abc208/submissions/23993696 今回は貪欲解で解くことができる。 だが、制約を見ると動的計画法を使っても解くことができるようになっている。 ここは恐らく優しさであ…

https://atcoder.jp/contests/abc208/tasks/abc208_a 解説 https://atcoder.jp/contests/abc208/submissions/23993338 A問題にしては少し難しかったかもしれない。 だが、テクニックとしてはそれほど難しくないので、もし分からなかった場合は覚えておこう。…

https://atcoder.jp/contests/abc207/tasks/abc207_f 前提知識 二乗の木DP 解説 https://atcoder.jp/contests/abc207/submissions/23806639 二乗の木DPという手法を用いる。 知らないと解けない気もするが、計算量的なセンスがあれば自ら生み出せるかもしれ…

https://atcoder.jp/contests/abc207/tasks/abc207_e 前提知識 https://blog.hamayanhamayan.com/entry/2017/02/27/021246 解説 https://atcoder.jp/contests/abc207/submissions/23805901 高度なDP。慣れていないと簡単ではないと思うのだが、500人も解くん…

https://atcoder.jp/contests/abc207/tasks/abc207_d 前提知識 幾何知識 解説 https://atcoder.jp/contests/abc207/submissions/23804855 微妙に幾何知識が必要。 自分の解法は想定解法ではなく、かつ、コンパイル時最適化でTLEをごり消した解法です。 慣れ…

https://atcoder.jp/contests/abc207/tasks/abc207_c 解説 https://atcoder.jp/contests/abc207/submissions/23803776 区間をすべて[l,r)の半開区間に変換して比較をしよう。 [l,r] -> [l,r + 0.5) [l,r) -> [l,r) (l,r] -> [l + 0.5, r + 0.5) (l,r) -> [l …

https://atcoder.jp/contests/abc207/tasks/abc207_b 解説 https://atcoder.jp/contests/abc207/submissions/23803329 愚直にシミュレーションをしていって、目標が達成されれば即座に回数を答えれば答えになる。 ただ、目標が達成可能でない場合は無限に操…

https://atcoder.jp/contests/abc207/tasks/abc207_a 解説 https://atcoder.jp/contests/abc207/submissions/23802672 選んで手に取る組合せは3通りなのでそれをすべて列挙して最大値を求めてもいい。 自分の実装では、求めたい最大値は3つの数から大きい2つ…

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

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

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

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

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

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

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

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

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