#matheditorial https://codeforces.com/blog/entry/61311 を考える = を考える 思いっきし相加相乗平均 x = y のとき最小そうでないとき, x と y ができるだけ近い方が良さそう (1) 式における x, y の対称性より, x ≤ y としても一般性を失わない とおく(1…

#dp 問題 https://yukicoder.me/problems/no/971 コンテストを振り返って 最初, bfs で書いて tle した 1 マス移動するごとに一定の時間が加算されるとは限らないから, 同じマスを何度も踏むことがありうる 最初, i 回いたずらっ子のマスを踏んでからあるマ…

#二分探索 #累積和 #中央値 解法 選んだ数列が要素数偶数なら, 真ん中の大きい方の数を抜いたほうが答えが良くなる(問題文に答えが整数になると書いてあるので, 分数が出てくる, 要素数偶数のときは答えにならないのではないか, と考える) ∵ 要素数が偶数の…

#math #言い換え #場合の数 問題 https://codeforces.com/contest/1288/problem/C 解法 対応するように, より, が決まれば も 1 対 1 で決まる 答えは, コード https://codeforces.com/contest/1288/submission/68889748

#math #ceil #不等式 #三分探索 解法 ∵ (左辺) = d (右辺) = ここで, x ≤ (右辺) ≥ = dより, -(n - x)(x + 1) + d ≤ 0 f(x) = とする この関数の最小値が 0 以下になればいいf ' (x) = 2x - (n - 1) = 0 x = f() ≤ 0 になるか コード https://codeforces.com…

#期待値 1. スライム i, i + 1 の間の距離が何回足されるか 方法 3 通り 1.1. 漸化式 1.2. 各々のスライムに対して何回通るかの確率を考える 1.3. 再帰的に解く2. スライム i, j の間の距離が何回足されるか editorial https://img.atcoder.jp/dwacon6th-pre…

#math #lcm #偶奇 解法 とりあえず, 小数点が嫌 2X = * (2p + 1) 左辺偶数, 2p + 1 = (奇数) より, 偶数 に奇数があったら 0 を出力して終わり : 偶数より, * (p + 0.5) = 例 1 とりあえず sample1 で実験 2 50 6 106 10 を 3 5 にする p + 0.5 を 2p + 1 に…

解法 1 (set) ある工事に対して, そこでストップになる人を求める ] の間 X が工事中ということは, ] に X にくる人がストップ すなわち, ] にスタートする人がストップ すべての工事に対して, ] にスタートする人をストップさせていく すべての工事に対して…

#2次元累積和 #圧縮 解法 列車 i は ] を走っている 2次元座標にプロットすると, 1 点で表せる L = , R = のところ 各 query を考える 区間 ] に収まっている列車の本数 L = に対し, R = L = に対し, R = ... L = に対し, R = ここで, L = に対し, R = L = …

#グラフ #相補的 #greedy 解法 できる限り大きな matching を満たす辺の集合をとる matching : どの 2 要素も端点を共有しない 集合のサイズを x とするmatching の端点でない頂点で, できる限り大きな independent を満たす頂点の集合をとる independent : …

#文字列 #bit #桁 解法 計算にあたり, 下の位から値が決まるのが困る 初めて 1 になる上の桁だけ計算できたら速いまず, x, y を反転する そうすれば, 左から計算できるsample の, x = 1010, y = 11, k = 1 の場合 x = 1010 → 0101 (反転), y = 0011 → 0110 (…

#文字列 #math 考えたこと 11...133...377...7 を考える 3 の数を x とすると, 3 は 2 つ選ぶので 答えは, 1 の数を i, 7 の数を j とすると, i * * jが n 以下になる最大の x は, くらい 全探索このようなやり方では, n が大きな素数のとき詰む s ≤ より よ…

#greedy #min #max #種類数 #数列 問題 https://codeforces.com/contest/1283/problem/E 解法 min について 1 回の merge で 1 つ数が減るよって min(残りの種類数) = min(元の種類数 - 減らせる種類数) = min(元の種類数 - max(merge の回数) ) 1 2 4 5 で,…

#math #条件厳密 解法 editorial の解法 ans は, -1 でなければ, 数列の 2 数から作れる sample 8 8 2 12 6 4 24 16 3 を sort する 2 3 4 6 8 12 16 24 ans = 48 = 2 * 24 = 3 * 16 = 4 * 12 = 6 * 8 別解 各素因数ごとに最小何か求める 最小なのは, 他の素…

#xor editorial の補足 解法1 数列に同じ 2 数を足しても xor は変わらない sum は 2 * その数増える2 * xor = sum にしたい 数列に足す 2 数は, (2 * xor - sum) / 2 ただし, 2 * xor - sum が偶数かつ 2 * xor ≥ sum 2 * xor は偶数より, sum が偶数残り 1…

問題 https://codeforces.com/contest/1270/problem/B 解法 単純なケースを考えるまず, 隣り合う 2 要素で YES になるのはどんな時か 差が 2 以上すべて, 差が 1 以下なら, どの区間を取っても最大で差がその区間の長さ - 1 答えは NO にならない

#木 #dfs #dp 解法 dfs で, それぞれの子を根とする部分木の頂点数が返ってくる その合計を n - 1 から引いたら残り 1 つの部分木の頂点数 コード https://atcoder.jp/contests/arc028/submissions/8522733

#two pointers コード https://codeforces.com/contest/1217/submission/67684154 解法 good か判定する文字列 (の左端と右端) を全探索する 右端を固定して左端をその右端の位置から左に延ばせば値が求まる値が求まったとき, その文字列の長さがその数より…

#math 問題 https://atcoder.jp/contests/abc148/tasks/abc148_e 類題 https://atcoder.jp/contests/abc052/tasks/arc067_a https://codeforces.com/contest/2/problem/B 解法 偶数の方が多いので, 素因数 5 の数を数えるここで, 例えば N = 100 なら, N!! =…

#two pointers #文字列 **解法 削除する区間の左 i を全探索する i より左に t の文字 (前から) があればあるほど削除する区間を延ばせる 具体例で解法を示すs = dcabdac t = abct は, s の 2 番目 (0 indexed) 以降の文字列で作れる 3 番目以降では無理t の…

#括弧列 #かっこ #カッコ editorial の補足 swapするところを全探索する以下の文字列を考える ( ) ( ) ( ) ) ( ( ) 前から prefix balances を計算する 1 0 1 0 1 0 -1 0 1 0一番小さい数は-1 この文字で終わるように始まるようにシフトする すなわち, その…

#greedy #segment union #event processing algorithms #binary search editorialの補足 何人連れて行くかは二分探索で固定されてるとする往復距離をできるだけ小さくしたい 何回か往復したとして, 被ってる場所があれば無駄segment を merge する 例えば, […

#文字列 解法 例 s = 231231 23131 23131131131 ... となるが, まず prefix がどの文字列でも同じことに注目 よって, 付け加えるだけまた, cut で s の末尾の数が必要だが, せいぜい以下 x 文字以上を構成する必要はないことを, 以下, editorial の補足で示…

解法 例 6 6 5 5 5 2 1w bwbw wbwb bwbw wbwbw bwbwbw上のように塗り分ける 各列ごとに, 偶奇によって一番下が b か w か変わる 反転しながら上に積んでいくここで, 上から 2, 3 行目を引き抜くことを考えるw bwbw wbwbw bwbwbwここで, 引き抜いたマスと隣接…

#greedy 解法 i番目とi + k番目は同じ数 同じグループにする グループ内では数字を合わせる手前の数が入ってるグループほど値を大きくしたくない例 6 2 123456 グループに分けると, グループ1 1, 3, 5 グループ2 2, 4, 6ここで, 先頭に近いほど値を変えたく…

#greedy #尺取り editorial https://codeforces.com/blog/entry/72461 ポイント が同じものは同時に見る 制限時間で全探索するが, 途中でbreakしない 例で示す ケース3で, であり, この前, すなわち, t = 1で打ち切る を採用しなければならない sum = 2 > 1…

#greedy 問題 https://codeforces.com/contest/1282/problem/B2 editorial https://codeforces.com/blog/entry/72461 editorialの補足 選択肢 1. 1個で買う 2. k個で買う k個以上を選択肢1. で買うのは不適 k個未満を1. で買うとして, 小さい方からfor文を回…

#math 解法 数列 h の i, i + 1 番目が 1. x x と同じとき, a の i 番目が何でも, シフトしても x との一致不一致は変わらない a の i 番目は k 通り2. x y と異なるとき a の i 番目が 2-1. x のとき h の i 番目と一致してたのに i + 1 番目と一致しなくな…

#文字列 #転倒数 解法 すべての文字に関して, 個数がs, tで同じでないといけない 反転する長さを2とする 1文字でも2つ以上出てたら必ずs, tを同じにできる s, tをsortするが, 隣の文字のswap回数を同じにしないといけない 同じ文字があれば, そこでswapしてs…

#set #sweep line #dsu(disjoint set union) #区間 #segment 解法 intersectの条件 2つの線分の一部が被ってる (一方が他方を完全に覆っていてはいけない)一部が被ってる2線分を考える 始点が先の線分を x , 始点が後ろの線分を y とする x の始点より後に y…