考え方だけメモ． 考え方 回答例 考え方色の区別がない場合に必要な入れ替え操作の回数は，「自分より小さいのに自分よりあとに現れる数」の（すべての「自分」に関する）総和となる（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で見ていけば良さそう． 最…