itertools.combinations()の使い方に注意が必要． 考え方 回答例 考え方$A$のどの行・列を残すかを全通り試せば良い．回答例itertools.combinations()を使えば簡単だが，2回使う場合には注意が必要．こうするとダメ． r = combinations(range(H1), H2) c = c…

方法1： 考え方 方法2：座標圧縮+いもす法 考え方 回答例 方法1：考え方$a, b$をイベント発生日としてまとめて扱い，イベント発生日を小さい順に考えると簡単に処理できる． Editorial - AtCoder Beginner Contest 188方法2：座標圧縮+いもす法考え方日をind…

考え方 回答例 考え方トーナメントは再帰で一つ下の階層の勝者を求められる．解法2がきれい． Editorial - AtCoder Beginner Contest 188 （Pythonの例：Submission #19320967 - AtCoder Beginner Contest 188）回答例 N = int(input()) A = list(map(int, i…

解法1：式変形 考え方 回答例 解法1：式変形考え方愚直に計算する方法を考えて，そのあと計算量を落とすことができるか検討する．$x, y$を全探索すると\begin{aligned} f(x, y) = Lx + \sum_{k = x + 1}^{N - y} A_{k} + yR \end{aligned}の最小値を計算でき…

考え方だけメモ． 考え方 回答例 考え方色の区別がない場合に必要な入れ替え操作の回数は，「自分より小さいのに自分よりあとに現れる数」の（すべての「自分」に関する）総和となる（AtCoder Beginner Contest 261 - YouTube）．後ろから見ていけばBITで反…

考え方 回答例 考え方2進数で30桁に制限されている．bitの桁ごとに演算すれば良い．また， 1〜iまでの操作の合成 (※1) 1〜iまでの操作の合成を値に作用させた結果 を保持できれば良い．※1：bitの桁ごとに計算して，桁の計算後が終われば捨てることにすれば，…

考え方 回答例 考え方$\mathrm{op}_{1}, (\mathrm{op}_{2} \circ \mathrm{op}_{1}),..., (\mathrm{op}_{M} \circ \cdots \circ \mathrm{op}_{1})$に対応する変換行列を予め計算しておけば良さそうであることはわかる．ベクトル$\begin{pmatrix} x \\ y \end{…

考え方 回答例 考え方区間$[l, r]$を考える（$1 \leq l \leq r \leq M$）．$l$を固定し，$r$を良い数列になるまで動かす．このとき，$r^{\prime} \geq r$に対し，区間$[l, r^{\prime}]$に対応する数列はすべて良い数列なので，個数をカウントする．上を$l=1,…

考え方 回答例 考え方Pythonの苦手な順序付き集合． 順序付集合 - 競プロはじめましたあとはlower_boundを使ってやるだけ．回答例 #include <bits/stdc++.h> using namespace std; int main() { int N, K; cin >> N >> K; vector<int> P(N); vector<int> ANS(N + 1, -1); vector<int> UNDER</int></int></int></bits/stdc++.h>…

考え方 回答例 考え方最小値の最大値なので，二分探索を考える．すべての要素を$x$以上にできるかは， $x + b$以上の要素から$b$減らせる操作回数 $x$未満の要素から$a$増やさなければならない操作回数 の2つを比較することで判定できる．回答例 N, a, b = m…

考え方 回答例 考え方文字列を[(文字種1, 個数1), (文字種2, 個数2), ...]の形（ランレングス圧縮 ，連長圧縮）で表した上で，条件を考える． Editorial - AtCoder Beginner Contest 259回答例 S = input() T = input() def f(X): res = [] cnt = 1 for x1, …

考え方 回答例 考え方入力例1を表でまとめるとわかる．各$p$を横に並べ，$p$の指数を標柱に記入している．丸をつけているのは，各$p$の指数の最大値である． $a_{i}$を1に変えた場合に最小公倍数が変化し得るのは「$a_{i}$の素因数$p$の指数$e$が，その他の$…

考え方 回答例 考え方$N$個の円を$1,...,N$の頂点に対応させ，円周が交わるなら辺を張った無向グラフを考える．こうすれば，$(s_{x}, s_{y})$に対応する頂点の集合から，$(t_{x}, t_{y})$に対応する頂点の集合へ到達できるかを判定する問題に帰着する．「中…

方法1 考え方 回答例 方法1考え方 各じゃがいもの種類$i$に対して，$i$スタートで重さの総和が$X$以上になるときの「個数」と「その次の箱に入るじゃがいもの種類$j$」を求めることができる． 上の結果から$i\to j$に辺を張った有向グラフを考えると，周期$N…

考え方 回答例 考え方ある文字列$S$に関する良いパス$A$がわかっていたとすると，そのパスの最後の頂点から隣の頂点に遷移してできたパス$A^{\prime}$は対応する文字列$S^{\prime}$に関する良いパス（の候補）である．よって，BFSで見ていけば良さそう． 最…

考え方 回答例 考え方優先順位は 桁数を増やすこと 大きい位に大きな数字を置くこと である．よって， コスト最小の操作を使って桁数をなるべく増やしたものを求め， 上の桁から（予算を超えない限り）なるべく大きな数字で置き換えていく ことで答えが求ま…

考え方 回答例 考え方答え（$S$）で二分探索（$O(\log \cdots)$）する．$S$を決めれば辺を$O(N^{2})$で張れる．スタート地点（$N$通り）を決めれば，BFS（$O(N^{2})$）で全ての頂点に行けるかどうかを計算できる．回答例すでに訪れた頂点はリストではなくset…

方法1：1コずつずらす 考え方 回答例 方法2：bisect 考え方 回答例 方法1：1コずつずらす考え方$X$としては現れる体重だけを調べれば良い．体重をソートして一番小さい場合から順に，正しく判定できている人数を調べれば答えがわかる．回答例 N = int(input(…

考え方 回答例 考え方入力例として， 3 3 1 2 2 3 3 1を考えると，DFSで辺を作れば$T_{1}$に，BFSで辺を作れば$T_{2}$になることがわかる．すでに頂点をつないだかどうかはsetで管理すれば良い．回答例スタックを使えばDFSになり，キューを使えばBFSになる．…

考え方 回答例 考え方全点対最短経路問題（すべての2頂点間の最短路を求める問題）が解けていれば， ある2頂点を結ぶ辺は， その2頂点を迂回する（複数の辺を使う）ことで，同じコスト「以下」で到達できるならなくてもよい（※1） ことからこの問題も解ける…

考え方 回答例 考え方アライグマ「E問題はサイクルを見つける問題なのだ！ 誰からも嫌われてない子にキャンディをあげていくと、嫌い関係がサイクルになってるところが残るのだ。サイクルのうち一番不満度が小さいところを諦めればいいのだ！」 pic.twitter.…

考え方（いもす法） 回答例 考え方（いもす法）Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)ログインしている人数をいもす法で求められる． ログイン人数が0→1以上となるところが区間の左端…

考え方 回答例 参考 考え方問題文から， $A_{i}$を一つ決めれば「良い数列」はきまる $O(MN)$くらいは許される がわかる．よって，$A_{i} = X_{j}$となる$(i, j)$の組み合わせを全探索できそう．$A_{i} = X_{j}$となるそれぞれの場合について，$A_{1}$が何に…

考え方 回答例 考え方クエリごとに$X$と$A_{i}$の差を求めるとTLEする．クエリの計算量$O(Q)$は絶対に必要なので，操作回数を高速に求める必要がある．ここで， $A_{i} $A_{i} \geq X$なら操作回数は$A_{i} - X$ だから，答えは\begin{aligned} \sum_{i (A_{…

考え方 回答例 参考 考え方分割の過程を二分木だと思って逆順に見ると，各葉に起因するコストは(葉の長さ)×(葉の深さ)となる．よって，もし二分木の形が決まっているのなら，長さが小さいものが最も深くなるように配置すれば良い． 以上をもとに，テキトーに…

考え方 回答例 考え方制約から 距離0：1コ 距離1：1×3コ 距離2：1×3×3コ 距離3：1×3×3×3コ で，各クエリに対して40コ調べれば良いから，言われたとおり計算するだけでよい．回答例訪れた頂点の管理をするために全頂点の配列を用意するとTLEする（各頂点への…

考え方 回答例 考え方$N$以下の整数を，平方数で割れるだけ割ったもので分類する．同じクラスに属する数どおしを掛け合わせたときにだけ，積が平方数になる．回答例 N = int(input()) cnt = [0] * (N + 1) for i in range(1, N + 1): j = 2 while j * j <= i…

気づくまでに時間がかかったのでメモ． 考え方 回答例 考え方$K=1$ならソートできる．したがって，$\mod K$ごとにソートできる．その結果を$A$のソート結果と一致するか見る．回答例 N, K = map(int, input().split()) A = list(map(int, input().split())) …

考え方 回答例 考え方DPで前から決めていけば良いことはわかる．DPを更新するためには， 前から何番目まで決めたか すでに使った文字の集合 最後に選んだ文字の種類 がわかれば良い（dp[i][j][k]で表す）．使った文字の集合はbitで管理できる．【更新ルール…

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