596.1

なんか算数っぽいセットだった。

250

ある要素を+1する操作または、全部の要素を二倍にする操作を行って、目的の配列を作るときの操作回数の最小値を答えよ、という問題。

取り敢えず、目的の配列の奇数要素は+1でしか作れないので、それ戻して、全部偶数になったら半分にして、とかそんな感じ。

500

どの二個のANDをとっても0にならず、どの三顧のANDをとっても0になるような集合を作りたい。一部分与えられているので、要素数がNのそのような集合のうち、辞書順で最小のものを答えよ、という問題。

取り敢えず使わないといけない要素でチェックしてやる。で、どれとANDとっても0になるビットをそれぞれ覚えておく。後は、新規に追加する要素について、今までにある要素から、余ってるやつを小さい順に加えていくだけ。後ろに追加しないといけない個数分だけ使えるビットを確保しておくことも忘れない。めんどくさいゲー。

1000

f(N)=N*(N-1)*(N-4)*(N-9)*...という関数がある。lo以上hi以下の整数について、この関数を適用した結果をDで割ったときの余りが0になるものの個数を答えよ、という問題。

f(N)がDで割り切れるとき、f(N+D)は(N+D)*(N+D-1)*...=f(N)+D*f(N)/(N,N-1,N-4,N-9,...)+D*D*f(N)/(N,N-1,N-4,...の二個の積)になるので、f(N+D)もDで割り切れる。(なんか後ろに更にかかるかも知れないけれど、それは見なくてもいいよね？)ということなので、f(N)をDで割ったときの余りが0になる最小のNをバイナリサーチで求めることができる。後はD回繰り返せば良さそうな雰囲気。

ちなみにバイナリサーチしないでTLEして落とされたっぽいと思っているだけで、何の確証もない。