解説を理解するのに時間かかった... 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…

E - 和風いろはちゃん / Iroha and Haiku余事象を考えるとわかりやすい 桁毎に全探索するメモ化で解く ある桁iで使える数vは、iを右端としたときに575とならないようなvだが これは右端から数の累積和を取ってbitに持たせれば575になるか判定できる 18以上の…

C - Kill/Death 問題概略 1000個の物を100個の箱に入れたい、また、いくつかの区間で昇順になっている必要がある。N,M sum 解法 昇順について考えなければ、桁DPとして解ける。 dp[i][rem] := iまで見ていて、残り使える合計がrem 昇順になっていないといけ…

問題概略 A~Bの中で4か9が含まれる物の個数を答えよ。制約 A,B 解法 4か9が一つでも含まれてればいいなら包除原理使うか！と思ったけど、大変そうなので桁DPで解いた。 まとめ上げるのに必要な条件は 何桁目を見ているか 数が上限ギリギリかどうか すでに4,9…

問題概略 ２つの整数u,v 制約 N 解法 aとbを適当に選んで、出てきたu,vを数えていきたくなる。しかし、これでは重複してしまうし、メモできるような数ではない。 ある桁のビットが1,0の時に0,1にしてもu,vが等しいと気づく。 よって1,0 は許すが0,1は許さな…