千反田えるのAC録[ARC070 D - No Need]

夏休みに入ったので、こちらもだいぶ暇です。夏休み中は1日1AC以上を目標にコツコツ頑張っていきたいですね。

普通に難しかったです。これ初見でわかる人天才では？

自分は自力実装こそしたものの、答えを見てどうにかの実装となりました。

恐らくですけど、部分点の考察までは割とスムーズにいくんですよ。

この時点でDPを行う必要があるわけですが、高々5000までの和が作れるかどうかの判定ができればいいことに気付けるかどうかでまず一苦労だと思います。

細かいところは公式解説に譲りますが、とにかくk-a[i]<=a[i]以外で作った和<kを達成するものが一つでもある時点でそれは必要な数、ということになります。

これをすべてのa[i]に適用することで部分点を獲得することができますね。

で、満点解法なんですが。さすがに累積和を使って解く方法は思いつかなすぎると思ったので、素直に二分探索をしました。そもそもこの二分探索を使う方法すらほとんど思いつかないと思うのですが。

数字が大きくなるほど必要になっていって、小さくなるほど不必要になっていく、というところは感覚でわかると思います(だって0はどう考えても不必要ですし5000はどう考えても必要でしょう?)が、必要と不必要の間に境界が存在し、二分探索ができるというところに関しては直感的に分かりづらいと思います。

二分探索は個人的にはバグの温床だと思っています、あまり書きたくはない。今回も二分探索の実装で盛大にバグり散らかしました。

難しいです。が、テクニックは平凡なものの集まりなのでしっかり実装できるようにしていきたいです。