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

hamayanhamayan's blog

2021-04-25から1日間の記事一覧

Graph Smoothing [AtCoder Beginner Contest 199(Sponsored by Panasonic) F]

https://atcoder.jp/contests/abc199/tasks/abc199_f 前提知識 行列累乗 解説 https://atcoder.jp/contests/abc199/submissions/22041784 この問題は数学パートと行列累乗高速化パートに分かれる。 行列累乗を使ったDP高速化を知らない場合は解けないのでま…

Permutation [AtCoder Beginner Contest 199(Sponsored by Panasonic) E]

https://atcoder.jp/contests/abc199/tasks/abc199_e 前提知識 bitDP 解説 https://atcoder.jp/contests/abc199/submissions/22040868 今回の問題はbitDPで解ける。 dp[msk] := 1~Nの数についてmskのものを使用していて、条件が満たされる数列の組み合わせ …

RGB Coloring 2 [AtCoder Beginner Contest 199(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc199/tasks/abc199_d 2020/4/25修正。後半部分が嘘解法でした。 前提知識 UnionFind dfs 解説 https://atcoder.jp/contests/abc199/submissions/22051608 制約を見ると全部の状態を全列挙しても大丈夫そうな感じがある。 本当…

IPFL [AtCoder Beginner Contest 199(Sponsored by Panasonic) C]

https://atcoder.jp/contests/abc199/tasks/abc199_c 解説 https://atcoder.jp/contests/abc199/submissions/22039696 この問題のミソはT=2の処理である。 T=1の場合はswapがO(1)で行えるので問題ない。 T=2の場合は、普通にやるとO(N)かかるのでこれを何と…

Intersection [AtCoder Beginner Contest 199(Sponsored by Panasonic) B]

https://atcoder.jp/contests/abc199/tasks/abc199_b 解説 https://atcoder.jp/contests/abc199/submissions/22039415 この問題は色々な解法が考えられるが、計算量が最も良いものを選択した。 求めたい整数xはとある範囲に限定される。 その範囲は、N個の[A…

Square Inequality [AtCoder Beginner Contest 199(Sponsored by Panasonic) A]

https://atcoder.jp/contests/abc199/tasks/abc199_a 解説 https://atcoder.jp/contests/abc199/submissions/22038994 問題文を実装しよう。 言語によるが累乗をサポートしていない場合は、普通に掛け算に直して計算する。 特に気を付ける所はない。 自分が…