考え方 回答例. 1 回答例. 2 - dequeを使う 考え方左端と右端を右方向に動かしていけば，$S$の長さの2倍の計算量で全て見ていける．したがって，しゃくとり法で実装すれば良い．あとは，いかにバグらせないかがポイントになる．回答例. 1$X$に変えられる区間…

【関連記事】 UnionFind木 - 競プロはじめました 考え方 回答例 考え方逆から考えてUnionFind木でつないでいくだけ．連結成分の数は， 頂点を加えたら+1 つながっていないグループを新たにつないだら-1 とすればよい．グラフの辺は小さい頂点から大きい頂点…

【関連】 UnionFind木 - 競プロはじめました 考え方 回答例 考え方$2^{10} = 1024$だから，$N= 2^{20}\simeq 10^{6}$．操作で時間がかかるのは$t_{i} = 1$の2. の部分．これを高速化するには，与えられた$x_{i}$に対しx[i] += 1$\pmod{N}$を繰り返し，はじめ…

実装 基本形 例題 AtCoder Typical Contest 001 参考 実装基本形 p = [-1] * (N + 1) # 親の配列 (いなければ-1), N要素 (1-indexed, P[0]はダミー) def root(x): # 親がいなければ自分(=根)を返す if p[x] < 0: return x # 自分の根 = 親の根 # & パス圧縮 …

考え方 回答例 考え方\begin{aligned} M^{K^{N}} \pmod{998244353} \end{aligned}を計算せよ，という問題．$x^{n}$の形なら繰り返し二乗法で計算できるので，この形に持っていくことを考える．logなんかをとっても上手くいくはずがない．$p = 998244353$は素…

ABC227Dと内容はほとんど同じですが，計算を効率的にしなければなりません． 【類題】 D - Project Planning (ABC227D - Project Planning - 競プロはじめました) 方法1 考え方 回答例 方法2 考え方 回答例 方法3 考え方 回答例 方法1考え方まず，整数$a$が…

【類題】 F - Distinct Numbers (ABC143F - Distinct Numbers - 競プロはじめました) 考え方 回答例 考え方部署$i=1$から順番に，下図のように割り当てることを考える．考え方すると，部署$i$のメンバーで使えるのは$\min(x, A_{i})$となる（チーム数を超え…

考え方 回答例 考え方\begin{aligned} \Biggl|\frac{B_{i}}{M} - \frac{A_{i}}{N} \Biggr| = \frac{1}{MN} | N B_{i} - M A_{i}| \end{aligned}であるから，$| N B_{i} - M A_{i}|$を最小化すれば良い．そこで，はじめに\begin{aligned} B_{i} = \biggl\lflo…

考え方 回答例 注 考え方任意の頂点を根として考えて良い．根から順番に深さ方向に辺の色を決めていけば，まだ見ていない辺の色を決めるときに常に始点の色が定まった状態になっている．そこで，根から順番に，子ノードに辺を伸ばしていくことを考える．始点…

考え方解説にあるように，偏角で考えれば「区間スケジューリング問題」に帰着する． Editorial - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)「区間スケジューリング問題」については，例えば蟻本を参照： Pythonで蟻本2-2 - 貪欲法 - …