#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…

#math editorialの補足 a ≥ bとする xの条件 1. 2. と(a - b)の2で割った余りが等しい 上2つを満たす最小の自然数をxとする a, bが等しくなる足し方 をa, bに分配する とりあえず, a, bにずつ分配する a, bが等しくなるのだから, 結局 aにはを足し, bにはを…

#map #x 解法 mapを2つ用意する 左から半分見るのと, 右から半分見るの 1が2より何個多いかを引数に, valueをindexとする 1が2より何個多いかで, 同じ数なら, より中心に近いindex が保存されることになる できるだけ食べないようにしたいからmap1でkeyがeな…

#ふつうの文字列 解法 1. 0...1, 1...0の文字列の数の差が1以下 多い方から始めて交代交代にすればいい0...1, 1...1, 1...0 のように間に1...1や0...0を挟むことも考えられるが これは後で挿入するとしたらよい後で挿入できないのは 0...1, 1...0が1つもなく…

#ふつうの文字列 解法 twooneでtwoとoneを認識 twoのo, oneのeを消すと twonとなり, twoが残る端を消すのはよくなさそう 真ん中さえ壊せばいい 他の文字と連結してもone, twoが作れないoooooneでも, 真ん中のnさえ壊せばいい onnnneはそもそもoneでないtwone…

#dp コード https://codeforces.com/contest/1262/submission/67185823 解法 自分が作る数列を考える 1番目の数は何通りありうるかsample1で考える 1 3 1 1番目の数を決めるのに, 関係するのは1 3 1にしたらポイントは-1 なぜなら, 1番目の数どうし1で一致し…

#文字列 注意 for文でやると事故りやすそう for文でやるというのは, sを前から見て, s[i] == c[i]の間はcontinueして, とか s[i] > c[i]なら, sのi + 1番目以降でc[i]より小さいの探す ただ, i + 1番目がなかったら? すなわち, i番目が最後のときまた, sがc…

解法 (xorの和) = (桁上がりを無視した足し算の和) = (足し算の和) - (桁上がりの和) 10^9+7で割るとこで事故った waのコード Submission #8867231 - AtCoder Beginner Contest 147 まず, 41行目あたりでAがlong longでもギリギリなことに注意(1)59行目 (ans…

#codeforcesまず, 偶数に着目する 0 0 0 ... 0 2 2 2 ... 2 (1) というようにする1は(1)のどこにも入れられる 3は2 2の間か2の横の端にしか入れられない 1と3は並ばないので, 独立に考える以上より, 制約のある3の入れられる場所をなるべく多くするため, 偶…

#codeforces 誤った考察 数列に出る数で2回以上出るのは, 最初の数以外消していい反例 3 1 2 3 4 あとの3消したらダメ辺の数多くなる? 1 1 ... 1 2 2 ... 2 のケース 圧縮したらいい1 2 1 2 ... 1 2 は? 1-2 1-2 1-2 ... だけでいい反例 1 2 3 2 3 で 1-2-3 …