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

考え方 回答例 考え方答え（$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で管理できる．【更新ルール…