考え方 回答例（配るDP & いもす法） 考え方配るDPなら区間への遷移．貰うDPなら区間への遷移．よって，よくある累積和を取りながらのDP． 【類題】 EDPC - M - Candies - 競プロはじめました ABC249E - RLE - 競プロはじめました 回答例（配るDP & いもす法…

Pythonの機能→c++でどう書く？を整理したい． 基本的なもの：C++で競プロ（メモ） - 競プロはじめました defaultdict defaultdict(int) defaultdict(list) 関連記事 defaultdictdefaultdict(int)std::mapを使えばよい． map - cpprefjp C++日本語リファレン…

Pythonが苦手なやつ（順序付集合 - 競プロはじめました）． 解法1：順序付き集合（c++） 考え方 回答例（setとmap） 回答例（multiset） 解法2：heapq（Python） 考え方 回答例 解法1：順序付き集合（c++）考え方辞書で個数を管理して，順序付集合でmax, min…

考え方 回答例 考え方ある頂点から他の頂点への最短経路を求めると，最短経路からなる集合は木になる（最短経路木）． よって，最短経路で通る辺を列挙すれば良い．回答例 import heapq N, M = map(int, input().split()) G = [[] for _ in range(N)] E = {}…

色々な解き方があるなぁ．．． 解法1：片方の集合を前から見ていく（もう一方は包含される範囲を見る） 考え方 回答例 解法2：種類数が同じ場合だけ考える 考え方 回答例 解法3：種類数が同じ場合だけ考える & 数値の置き換え 考え方 回答例 解法1：片方の集…

考え方 回答例 考え方$N \leq 10^{18}$なので$q \leq 10^{6}$．よって，$10^{6}$以下の素数を列挙して，$\min(N /\!/ q^{3}, q - 1)$以下の素数の数を数え上げれば良い． エラトステネスの篩（Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめまし…

解法1 考え方（貰うDP） 回答例（貰うDP） 考え方（配るDP） 回答例（配るDP） 解法2 考え方（貰うDP） 回答例（貰うDP） 解法1考え方（貰うDP）「dp[i] = $i$までの全てに餌をあげる方法を決めたときの最小の合計コスト」とすると，「$i$と$i + 1$に餌をあ…

解法1：鳩の巣原理＋bit全探索 考え方 回答例 解法2：DP＋経路復元 考え方 回答例 解法1：鳩の巣原理＋bit全探索考え方200で割った余りは200通りだけであるから，201個調べれば必ず同じものがある．$2^{N} > 200$となる最小の$N$は$8$なので，先頭の$8$個を…

考え方 回答例 考え方以下2点がポイント． 制約がユルイので，マッチングを全探索できる（bisectは必要ない．3重ループで間に合う．） 貪欲法で解ける 貪欲法の考え方は，2パターンある． 「箱」を順番に見る：「後ステップに大きい箱を残す」ことは，「それ…

考え方 回答例 参考 考え方数列$C$の等しい部分に分割して考えて，それぞれの区間での$A_{1},...,A_{M}$の最大値が$O(1)$で求められれば，全体では$O(N)$計算できる．数列$C$の要素が全て$a$である区間を考える．$B,A$の前の区間からの持ち越し分を$b_{0}, a…

考え方 回答例 参考 考え方 「dp[i][j] = $i$番目まで選んだときに和が$j$となる場合の数」としたくなる 不等式の両辺が動くと困るので，片方を固定したい．和については↑のようにdpで考えたいので，maxを固定したい． $\{(A_{i}, B_{i})\}_{i}$を$A_{i}$に…

考え方 回答例（再帰関数） 回答例（スタック） 考え方AtCoder Beginner Contest 220 - YouTube 頂点1からの答えがわかっていれば，頂点1に隣接する頂点$v$の答えは「(頂点1の答え) - ($v$の部分木の頂点数) + (N - $v$の部分木の頂点数)」で求められる．こ…

EDPC - M - Candies - 競プロはじめましたの類題だが，今回の方がはるかに難しい．．． 配るDP & いもす法 貰うDP & 累積和 配るDP & いもす法文字数が少ない問題に帰着させられそうなので，dpを考える．「dp[i][j]=圧縮前の長さが$i$・圧縮後の長さが$j$の…