495.1

見た部分はストレートフォワードなセット。

275

1からNまでの数の(連続である必要はない)部分列について、小さい順に素数かどうかが与えられる。このとき、元の部分列をできる限り復元せよ、という問題。

探索するだけ。部分列のどれかがある値だと仮定すると、その前後は一番近い素数ないし素数でない数を割り当てていくことで、その仮定が正しいかどうかが分かる。

500

見てない。

975

長さNのビット列があるとして、Kビットのパターンをシフトして得られるものをN/K個使って全体をカバーすることを考える。このとき、可能なパターンは何通りか答えよ、という問題。

ただの分割統治。分割の方法が二通りあるので、それらを交互に組み合わせていくことでパターン数が結構増える。分割は除算をベースに進むので、出てくるのはNの約数だけなので、メモしてやればTLEの心配はない。分割の方法は、Aビット刻みに並べて、0,1,2,...,A-1シフトしたものでカバーする方法と、Bビット連続で並べて、0,B,2B,...とシフトしたものでカバーする方法。AはKの1より大きい約数すべてが該当して、BはNのNでない約数のうちKの倍数であるものすべてが該当する。