judge.u-aizu.ac.jp 問題 長さ N の数列と整数 X（※Long型）が与えられる。 数列の部分列のうち、和が X 以下であるようなものの個数を求めよ。 考察 しゃくとり法の問題です。例によって詳細は省略します。 今回は自分で一から実装するのではなく、以下のペ…

atcoder.jp 問題 長さ N の数列と整数 K が与えられる。 積が K 以下であるような数列の部分列のうち、最も長いものの長さを出力せよ。 考察 しゃくとり法の典型問題……ということで何とか自力で考察・実装しました。 ・積が K より大きい → 左端を伸ばす ・…

atcoder.jp 問題 長さ N の数列がある。 数列の長さ 3 の部分列のうち、初めて和が K 未満になるような部分列の位置を求めよ。 考察 勉強のため、二種類の解法で解きたいと思います。 累積和から部分和を求める 数列に対してあらかじめ累積和をとっておくこ…