ABC077 C - Snuke Festival
問題
提出コード
中段について、番目のパーツを使うとしたときに、使うことができる下段のパーツはとなるパーツ番号の場合です。このようなのうち最小のものをもとめれば、それより大きい個のパーツはすべて使用できます。
ということで、まずはそれぞれのパーツについて、昇順でソートをしておきます。すると、先ほどのの最小値は二分探索で求めることができます。
そして、に対して使えるのパーツの個数を記録していきます。
さて、を使うと決めたときは、となるようなの個数です。ということで、先ほどソートをしていたため、こうなるようなの最小値を求めていれば、使えるの区間が決まります。
を使用したときに使えるの個数は先ほど求めていたため、その記録を後ろ側から累積和を求めることで、
でを決めたときに使えるとのパーツの組み合わせを求めることができます。