過去問埋め2
B - Between a and b ...(ABC048)
0≦a≦b≦10^18,1≦x≦10^18となるとき
a≦k≦bとなるkのうちxで割り切れるものの個数を求める問題
制約が0以上であることに注意しなければならなかった
b/x-(a-1)/xとかすると多分a=0でアなのでb/x-a/x+!(a%x)とかにするべき
長さのnの数列a,b,cについてai<bj<ckとなるパターンを数える
制約的に愚直にはできないので二分探索する。
初の二分探索だったがバグらせたので要精進。
めぐる式考えた人天才か?(これchokudaiさんなんですね)
これ天才限定パズルでは?
dpな気がしてならなかったけどx<=1000000000なので無理
簡単に言ってしまうと1+2+3+....+t>=xとなる最小のtが答えとなる
(このようなtのときある部分集合{1,2,...t}の和がxとなる)
n個のビスケットが入った袋から自由に選び(合計%2==p)となる組み合わせの数を求める
全ての袋に偶数枚のビスケットが入っていればans=0 or 2^n
それ以外のときans=2^(n-1) (i個目以外のn-1個の選び方を決めたときiを選ぶか選ばないかのどちらかが条件を満たすため)
C - Takahashi's Information(ABC088)
あまり難しくはないが一つ決め打ちして矛盾を調べるのは汎用性が高そう