#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 ≤ より よ…