解けなかったので、こういう流れで解きたかったという妄想を書きます C - K Derangement 分かりやすさのために、以降i=0~N-1で0~N-1の順列を並び替える問題として考えます 解説 問題文で問われているのは辞書順最小なので、先頭からなるべく小さい数を入れて…

概要 包除原理と期待値の線形性（誤用かも）で解きました 既存の解説はメビウス変換が多かったので自分の解法を書いておきます。 問題 N個の整数S1...Snが与えられ、それらの整数をランダムにいくつか選ぶ。ここで(1<=i<=n)なるiで各Siが選ばれる確率はPi/10…

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

フローの張り方が分からなかった。 ------------------------------------------------------ F - Grid and Tokens 問題 H*Wのグリッドがある N個のコマで、i番目のコマについて ・指定された長方形領域のどこかに一つ置く ・置かない のいずれかを選択でき…

セグ木で差分を更新する方法が勉強になった。 F - Insertion Sort ---------------------------------------------------- 問題 長さNの順列Pが与えられる。 左からi番目の値はPiである。 以下の操作を使ってPiを昇順に並べたい。 ・i(1<=1<=N)を選ぶ。コス…

解けなかった...フローというかグラフ系が見えない事が多い。 ------------------------------------------------------------ 問題 M個の偶数長の整数配列が与えられる それぞれの整数にL, Rを割り振り方で、以下を満たすものを一つ構築せよ。ない場合は-1…

解説を理解するのに時間かかった... D - Range XOR 以下はkmjpさんのブログ記事 AtCoder ARC #133 : D - Range XOR - kmjp's blog を読んで理解したものなのですが、備忘録として残します。 問題 整数L, R, Vが与えられる。 L<=l<=r<=Rで、lからrまでのxorが…

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…

atcoder.jp 問題 H行W列のマス目について 各マスに0~K-1の整数を書き込もうとしている。 ここで以下の条件を満たす必要がある。 1<=i<=Hで、i行目のマスの整数の合計をKで割った余りはA[i]であり 1<=i<=Wで、i列目のマスの整数の合計をKで割った余りはB[i]で…

atcoder.jp 問題 順列P, Qが与えられるときに、連続するとは限らない部分列P', Q'を長さKで取る 任意のiについて、Q'i がP'iの倍数になっているとするとあり得る最大のKは何か 解答 全てのiについて、Piに対して同時に選べるQjの組の合計の合計は調和級数よ…

https://codeforces.com/contest/1633/problem/E 問題 N頂点M辺の連結無向グラフが与えられ、各辺にはwiの重みがある。 f(x) := sigma(wi - x)が最小になるように取った全域木のコスト とした時に、10^7個のxが与えられる。 全てのxについてf(x)を計算し、そ…

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