この記事の概要
@hirokihelloの解説ACした問題の思考の反省log
問題概要
nこの数列がある。
その連続する部分数列の和がK以上となるように、部分数列を作るときの部分数列の数を求める。
自分の思考
最初と最後を素直に決めて、足りてるかどうかを考えるのかと考えた。
その計算自体はDPかメモ化で、どこかに保存しておけば高速化できると考えた。
しかしそもそもの計算量がO(n^2)なので詰んだ。
この時点で解説を見た。
ACのための思考
解説とは若干異なるが、
まずスタートの点を1~nまで全探索することにする。
そのあと、Kを最初に超える点を見ていく。
ここで重要なのは、スタートのidxが a < bで、対応するゴールのidxが、ag, bgとする。
このとき必ずag <= bgとなる。なぜかというと、aからスタートした点の場合初めてagでKを超える。
なのでaからagまでのidxの和からaを引いたものがbからbgまでの和となり、これは直感的にわかる。
しゃくとり法という方法だが、スタートの点とゴールの点が1~nまでしか動かないので O(n)で余裕であにあった。
まとめ
区間+部分和の問題であったが最も大切であったのは、スタートの点を1~nまで見ていけば全ての部分和が作れるという考え方であった。
最初、bit全探索のように1桁の場合、2桁の場合、などのように考えなければ全ての部分和を求められないと考えていた。
部分和をどのように設定できるのかという考え方が今回は足りなかったと思う。