648.1

実装大変でしたね。

250

AとBからなる文字列のうち、文字数がNで、Aの後にBがくるというインデックスの組がK個の文字列を答えよ、という問題。

愚直に探索するのがいいと思うけれど、まずはAとBが半分ずつある文字列を作って、適当に隣接するA,Bをスワップしていくと良いらしい。余り確信が持てない...。

550

i番目のものの値段が買うたびに変動していって、i*2^jみたいになる商品があるので、安い順にK個買うときのK番目の値段を答えよ、という問題。ただし、iにも上限は一応ある。

取り敢えず、K以上になるのはどの商品か知らないけれど、1番目の商品を何個以上買う必要があるかを決める。そうすると、2番目の商品はそれよりも一個少なくしか買えない。3番目の商品はその時点では2個少ないけれど、それを1個少なく頑張るとしたらどうなるかを考える。もしそれでも足りないなら7番目の商品を増やす方向で頑張るし、そうでなければ5番目の商品を増やす方向で頑張る。みたいな感じで、何番目の商品が次に安いのかがなんとなく分かるので、頑張って探索しましょう、実装しましょう、という問題。問題自体は簡単だけれど、他人に説明するのが面倒。

要は、取り敢えず二進数で100...0の値段の商品を買うと個数が明らかにオーバーするけれど、一桁少ないと足りない、みたいなので桁数を固定して、後は上位ビットから順に0か1かを決めていくような感じでやれば良い。実装が大変、面倒です。

850

見てない。