解法1 考え方 回答例 解法2 考え方 回答例 解法1考え方例えば，入力例1を考えると，下図の筆算が計算できれば良い．繰り上がりを考えなければ，各桁の足し算は$X$の累積和になっている． 後は，繰り上がりを考慮すれば良い．筆算回答例 import itertools X =…

【関連】 ABC231F - Jealous Two - 競プロはじめました 考え方 回答例 考え方ABC231Fと類似の考え方．ただし，BITで区間和を取るのではなく，区間の最大値を求める．最大値を求めるように，BIT (Binary Indexed Tree (BIT) / Fenwick Tree - 競プロはじめま…

【関連】 D - プレゼント (ABC038D - プレゼント - 競プロはじめました) 考え方 回答例 参考 考え方$A$の昇順・$B$の降順で見ていく．絵を書くとわかりやすい．各$B_{i}$に対し， bit[i] += 1とし， ans +=$\sum_{j (\geq i)} \mathrm{bit\,} [j]$としていく…

フェニック木 (Fenwick tree) とも呼ばれます． 基本形（区間和） 機能 実装例 例題 応用（最大・最小・XORなど） 機能 実装例 例題 応用（二分探索→ある要素が何番目に大きいかがわかる） 参考 基本形（区間和）機能数列$a_{1},a_{2},...,a_{N}$があったと…

【関連】 F - Valid payments 考え方 回答例 考え方まず，$X$を「$\{A_{i}\}_{i}$を使った進数」で表す．つまり，「$X$を最小の硬貨でピッタリ払うときに必要な各硬貨の枚数」を決める．これは，大きい硬貨から使えるだけ使えば良い．これにより，$X$を\begi…

考え方 回答例 UnionFind DFS 考え方「$A$と$B$が隣あっている」を「$A$と$B$に辺がはられている」と読み替えればグラフの問題になる．横一列に並べられる条件は， すべての頂点から出ている辺の本数が2以下であること 閉路がないこと である．閉路検出は次…

無向グラフ UnionFind DFS 有向グラフ トポロジカルソート 無向グラフ【例】 ABC231D - Neighbors - 競プロはじめました UnionFindUnionFind（UnionFind木 - 競プロはじめました）を使えば，次で検出できる． 辺を張るたびに頂点をマージする 新たに$a,b$に…

【関連】 ABC230E - Fraction Floor Sum - 競プロはじめました 方法1：エラトステネスの篩（ふるい） 考え方 回答例 方法2：等差数列の和 考え方 回答例 方法3：和を√Nで分割 考え方 回答例 方法1：エラトステネスの篩（ふるい）考え方約数を考える問題では…

【関連】 ABC172D - Sum of Divisors - 競プロはじめました 考え方 回答例 参考 考え方$[x]$は他の問題では$\lfloor x \rfloor$で表すことが多いので，こちらを使う．もちろんそのまま計算しては間に合わないので，$\biggl\lfloor \dfrac{N}{i} \biggr\rfloo…

考え方 回答例. 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 - 貪欲法 - …

方法1 回答例 方法2 方法1コンテスト中に考えた方法です． $B_{00} = (i-1)\times 7 + j$を満たす$(i, j)$が存在し， $1 \leq i \leq i + N - 1 \leq 10^{100}$，$1 \leq j \leq j + M - 1 \leq 7$を満たし， $B_{kl} = B_{00} + 7k + l$を満たす ならYesで…

「値」が何種類かというのがポイント．ここを「$n$の種類」と読み違えると泥沼にはまる（「$X=1$の場合，無限に存在するじゃん？？？」，となる）．上のせいで，難易度が水色なのだと予想．．．考え方例を見ればわかるように，$n$に関して単調増加なので，二…

考え方 回答例1：「Pinv[頂点]=コマ」を使う 回答例2：「P[コマ]=頂点」を使う 考え方コマを頂点に置く方法は$9! = 362,880$と少ないので，dictで「並び順：かかった手数」を管理しながら全探索（BFS）できます．コマのない頂点には，仮想的なコマ9を置くこ…

全探索して，3点が一直線上になければ+1すれば良い．一直線上にあることは，$x$が小さい順に点を$P_{1}, P_{2}, P_{3}$として，条件【「点$P_{1}$と点$P_{2}$の傾き」＝「点$P_{1}$と点$P_{3}$の傾き」】を満たすかどうかで判定できる．分数だと分母がゼロの…

「長方形が3つ」という点と「辺の長さが整数」という点がポイントです． 考え方条件を満たす長方形が3つ存在したとする．長方形が3つなので，ある一つの長方形は，辺を$x$軸 or $y$軸方向に目一杯延長しても他の2つの長方形と干渉しない．そのような長方形を…

【関連問題】 ABC216D - Pair of Balls - 競プロはじめました 考え方「数字を頂点」，「順序関係を辺」と考えればグラフの問題になる．求められているものは，トポロジカルソートしたもので，辞書順で最小のものであるとわかる． （トポロジカルソートについ…

考え方：二分探索バグ取りに苦労した．もっと見通しの良い方法がありそう． 求める位置が左からx以上となるならok，そうでないならngとして二分探索を考える．あとはcheck(x)関数をつくればよい．左からx進むのにかかる時間tlと，トータルの時間を計算するこ…

むずい．考えの流れを整理しておく． 【類題】 C - ABC conjecture 考え方$N\leq 10^{10}$だから，$N$になる数を調べることはできない．よって，$a^{b}$で表せる数を重複なくカウントして，$N$から引く方針． 一番単純な方法として，「$a,b$の全探索＋setの…

考え方入力例1の3番目をもとに考察するとよい（具体例大事！）．$R \leq B$とする（例は既にそうなっている）．以下の手順で全てGに変えることができる． R G B 1 2 4 3 1 3 2 3 2 1 5 1 0 7 0つまり，すべてGにしたければ，RとBを同じ個数に調整できればよ…

考え方：公式解説の方法公式解説の方法（Editorial - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222））を考える． まず，各辺を何回通るか求める．頂点$A_{i}$と頂点$A_{i+1}$を結ぶ辺を通る回数を$C_{i}$とする．すると，\begin{ali…

考え方dp[i][j]=「$c_{i} = j$となる方法の数」がわかれば，\begin{aligned} &\mathrm{dp}[i+1][j] \\ & = \begin{cases} \, \displaystyle \sum_{k\leq j} \mathrm{dp}[i][k] & (A_{i + 1} \leq j \leq B_{i+1}) \\ \, 0 & (\text{otherwise}) \end{cases} …