B問題なのに手間取ったのでメモ． 全探索せずに，切り上げ・切り下げで考えて沼ってしまった．．．考え方1：全探索B問題としては，全探索するのが素直．個数$N$のパターンは高々$10^{6}$通りなので，$A \leq 1000W/N \leq B$となるもののうち，最小・最大を…

考え方根を「深さ$0$」とすると，深さ$d$にある頂点の個数は$2^{d}$個．深さ$0$から深さ$d$までの頂点の総数は\begin{aligned} \sum_{i = 0}^{d} 2^{i} = 2^{d + 1} - 1 \end{aligned}であるから，問題文の設定では深さは$N - 1$である．「①一番浅い頂点$v$…

各$A_{i}$について，$i 考え方 $i \begin{aligned} \mathrm{ans} &= \sum_{\{(i,j) \mid i &=\sum_{j} 2^{j} \textcolor{red}{\sum_{ \substack{i \end{aligned}を計算すればよい．以下，$j$でループさせることにして，赤字の部分をどう実現するか考える． …

1. bit 全探索考え方分割後の数字は，大きい位ほど大きい数字のほうがよい．よって，どの数字を選ぶかが決まれば，並び方は決まる．数字の選び方を全探索することを考えると，9桁しかないのでbit 全探索できる．回答例 N = list(map(int, list(input()))) N.…

考え方差分だけを処理していく問題．ログインとログアウトを後で区別できるようにして「ごちゃまぜソート」をするとラク（これもよくあるパターン）．日付を1日単位で見るとTLE．「現れる日付の差」を使って処理する．現れる日付を前から見ていき，今ログイ…

考え方 $S,T$の原点を重心に取り直す（座標全体を$N$倍すれば，座標変換後も整数座標になる） $S$の中で原点から最も離れている点$(x_{0}, y_{0})$を1つとる． $T$の中で，原点からの距離が$\sqrt{x_{0}^{2} + y_{0}^{2}}$に一致するものの偏角（$x$軸となす…

よく出る思考パターン・覚えておきたいアイディアをメモしておきます． 問題の分類にもなっています．参考になるコードのリンクをメモしている問題もあります．【2022.01追記】最近は，このページではなく，タグで分類するようにしています． 入力 出力 改行…

【類題】EDPC - D - Knapsack 1 - 競プロはじめました 考え方 DP - 「ぴったり」で考える方法 貰うDP 考え方まず，制約から何を変数に使えるか考える．D - Knapsack 1とは，制約のみ異なる．これにより，変数に$W$を使うことはできなくなる．代わりに，$v_{i…

【類題】EDPC - E - Knapsack 2 - 競プロはじめました 考え方②：「ぴったり」で考える方法 貰うDP 考え方①：「以下」で考える方法 貰うDP 考え方②：「ぴったり」で考える方法「$W$以下」ではなく，「$W$ぴったり」となるように考えるのがよくあるパターン．…

配るDPでないと，うまく書けない例？ 【類題】 ABC099C - Strange Bank - 競プロはじめました ナップサック問題に雰囲気が似ている：D - Knapsack 1 - 競プロはじめましたDP考え方$N$コの弁当からたこ焼き$X$コ・たい焼き$Y$コ（ぴったり）になるよう選ぶ方…

きっかけ：ABC219Dと次の記事． 貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita DP 考え方 貰うDP 配るDP メモ化再帰 DP考え方答えを$f(N)$とすると，$x = 0,1,...,N-1$に対して$f(x)$がわかっていれば$f(N)$が計算できる．よって，D…

考え方 回答例 考え方 辺を除かない状態で，最短距離dを求める．また，最短経路につかう辺の集合routeを求める． 辺を順に除いていき，その辺がrouteに含まれないならdが答え．routeに含まれるなら，もう一度最短距離を求める（※）． （※）routeの数≦$N-1$で…

クラスカル法クラスカル法．コストの小さい順に辺を見ていき，閉路・二重辺でなければ追加する．UnionFindを使う．バラバラの状態からはじめ，辺の頂点が同じグループに属していないなら追加すれば良い．UnionFindコストが負の辺は取り除く意味がない（すべ…

対角線上の2点を決める 対辺の数を求める 対角線上の2点を決める長方形は，対角線上の2点により一意に決まる．よって， 左上と右下の座標を決めたとき， 左下と右上の座標が集合に含まれるか判定する setのinなら$O(1)$で計算できるのがポイント．【参考】Su…

不要部分を削った行列が一致するか判定する numpyによる解法 numpyなし #の座標の集合で見る 不要部分を削った行列が一致するか判定する行列の不要な部分を削除した上で，片方の行列を回転させてもう一方と一致するかを調べれば良い．numpyによる解法ちょっ…

C++ ではこんなに簡単にかけるのに．．． Editorial - AtCoder Beginner Contest 217【追記（C++ の回答）】(C++) ABC217D - Cutting Woods - 競プロはじめました一般的な話は次が役立ちそう： std::setを使わない代替テクニック [いかたこのたこつぼ] 【Pyt…

考え方 二分探索 貪欲法 考え方$1 \leq K, A_{i} \leq 2\times 10^{9}$と，大きな値を取り得る．二分探索公式解説の方法：Editorial - AtCoder Beginner Contest 216初期値が$A_{i}$のアトラクションは，最大$A_{i}$回利用できる．利用回数の視点で考えるの…

【関連問題】 ABC223D - Restricted Permutation - 競プロはじめました 考え方 回答例 回答例 - カウンタで管理 回答例 - 1個ある集合・2個ある集合を別に持つ 回答例 - トポロジカルソート 考え方言われたとおりにやって間に合うというのに気付けるか，言わ…

この記事は，以下から該当箇所を抜き出したものです：Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました （蟻本p. 114-）【注】Pythonでは繰り返し二乗法を実装しなくても，pow(base, exp[, mod])により，pow(base, exp) % modが効率よく計算…

解答の補足事項のみ書いておく．以下では，$l, m,n\in \mathbb{Z}$とする．はじめに$A_{i_{1}}$を選び，辺を張れるだけ張ったすると，$x$と同じ連結成分にできる頂点は\begin{aligned} & x + l A_{i_{1}} \pmod N \\ & \Leftrightarrow x + l A_{i_{1}} + m …

解法1. 式変形参考記事[1]の方法． すべての料理の集合を$\Omega$，先手が選ぶ料理の集合を$X$，後手が選ぶ集合を$Y$とする．先手が最大化したいのは\begin{aligned} & \sum_{i\in X} A_{i} - \sum_{i\in Y} B_{i} &= \sum_{i\in X} (A_{i} + B_{i}) - \sum_…

B - アリの高橋くん 考えたこともっと簡単な方法があるんだろうな，とは思いつつも，計算で解が出せるので解いてしまった．現在地$(x_{0}, y_{0})$を中心とする円で各辺に接するものの半径を求め，それらのうちの最小値が答えになる．隣り合う頂点の座標を$(…

E - Divide Bothもう少し簡単な類題で慣れないと解けないなぁ，という感想． とりあえず約数で考えて，余分なものを差し引いて最大公約数の寄与だけ取り出す方法は汎用性がありそう．考えたこと与えられている条件は $x,y$が互いに素ではなく 一方が他方の倍…

D - KAIBUNsyo考えたこと $A$を両端から，ペアとなる文字を中心に向かって順に見ていく． もし「異なる」場合は，その時点で置き換える． でできる．ここで問題になるのは，ある2つの数字を等しいとみなす処理を繰り返すため，「数字が異なる」という状態が…

C - Swappable考えたこと典型例としてまとめていた次がほとんどそのまま使える． AtCoder - 解法の整理 - 競プロはじめました上では$A_{i}=A_{j}$の個数を数えているのに対し，今回は$A_{i}\neq A_{j}$の個数を求める点が違う．よって，総数（$N (N - 1)/2$…

B - Savings考えたこと\begin{aligned} \sum_{i=1}^{k} = \frac{k(k+1)}{2} \end{aligned}だから，\begin{aligned} \frac{k(k+1)}{2} \geq N \end{aligned}を満たす最小の正整数$k$を求めれば良い．２次方程式\begin{aligned} & \frac{k(k+1)}{2} = N \\ &\L…

A - Maxi-Buying$\lfloor 1.08\times N\rfloor$は int(1.08 * N) 108 * N // 100 math.floor(1.08 * N) などで計算できる．

C - Many Formulas考え方文字列$S$の長さを$N$とすると，$N-1$箇所に$+$を入れる方法を全通り試せばよい．これはbit全探索で実現できる．最終的に求めたいのは総和なので， $+$の直後の文字列から次に$+$が出るまでの文字列を記憶し， $+$が出たら，それまで…

E - Dist Max考え方$i,j$を含んだ式で2重ループだとTLEする問題．典型的なパターンとして，①$|x_{i} - x_{j}| + |y_{i} - y_{j}| = X$となる$X$を振る，②$i,j$を式変形で分離してループを1つにする，が考えられる．①は$1\leq x_{i}, y_{i}\leq 10^{9}$だから…

D - Card Eater考えたこと同じカードが3枚以上あれば，そのカードを3枚選ぶことで，2枚ずつ減らせる．この操作を繰り返せば，同じカードは2枚以下にできる．よって，すべてのカードは1枚 or 2枚であるとして良い（※ 1枚になるのは同じカードが奇数枚あったと…