詰め切るのが難しかった D - Pure Straight ------------------------------------------------------------ 問題 N項の整数列Aが与えれる、Aiは1...Kのいずれかである。 隣接する二項をswapする操作を何回でも行える時、ある区間が1...Kになるような最小の…

F - Unfair Nim 解答 (A[0]-x)^(A[1]+x) == A[2]^...^A[N-1]になるようなxがあるかという問題である a2 =A[0]-x, b2 =A[1]+xとして、a2とb2を求める事にする 問題文より、a2は以下を満たす最大の値になる 0 <= a2 <= A[0] a2 + b2 = A[0] + A[1] a2 ^ b2 = A…

https://codeforces.com/contest/1593/problem/D2 問題 N要素の整数列Aと以下の操作が与えられる ・あるiについてA[i]-=Kする あるKについて上の操作を任意の回数行った後に 同じ数字が過半数を占めました 考える最大のKを求めよ Kには単調性が無いので二分…

D - 一次元オセロ (1D Othello)kmjpさんの実装を参考にしました Submission #3867975 - パ研合宿コンペティション 2日目解法 白黒を区間として持てばひっくり返すのが楽です。 操作中の区間は高々N+1個であり、消える区間は端であるため、dequeを使えば実装…

D - IntegerotS問題概略 N個の非負整数がああり、それぞれに価値がある。 いくつかをKを超えないようにorを取った時に価値を最大化したい。制約 1≤N≤105 0≤K 0≤Ai 1≤Bi≤109(1≤i≤N) 入力は全て整数である解法 最初桁DPのようなことをやろうとした。oo桁目以降…

問題概略 N個の正の整数が与えられる。 xorがKになるような選び方は何通りか制約 N K sum(ai) 解法 O(NK)が間に合うなら、[i][k] := i番目までの中からkを作る通り として [i+1][k] += [i][k] [i+1][k^A[i]] += [i][k] と現状から遷移できるものを足していけ…

D - Two Sequences 長さNの数列 a,bが与えられる。 ai bjのN^2の全ての選び方について、ai + bjを計算しする。 それらのxorを求めよ 制約 入力は全て整数 1≤N≤200,0001≤N≤200,000 0≤ai,bi<228 解法 愚直に計算すると間に合わない。 xorは繰り上がりしないの…

C - すぬけそだて――ごはん―― 問題概略 A以上B以下の数から0個以上選ぶ時、それらが互いに素になる組み合わせはいくつか 制約 1≤A≤B≤10181≤A≤B≤1018 B−A≤35 解法 高々35個しかないので、偶数の中から0個か1つ選び、奇数の中から選ぶ数を全探索できる(18 * 2^1…