2021-12-01から1ヶ月間の記事一覧
解法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…
