二分探索:工夫して求めた配列上のlower_bound
NoviSteps2Q
しゃくとり法
二分探索
二分探索:lower_bound
二分探索:工夫して求めた配列上のlower_bound
ある値を固定して考える
解空間:O(N^2)個の区間
解空間:O(N^2)通りの選択肢
数列
累積和
単調性に着目する
AtCoder
鉄則本
鉄則本B問題
鉄則本★4
そのまま覚えたい典型問題
しゃくとり法の練習問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 この数列の連続する区間であって、総和が 以下であるものの個数を求めよ。 制約 解法 (1)：しゃくとり法 editorial に詳しく書かれている。 github.com コー…
NoviSteps3Q
二分探索
二分探索:lower_bound
データ構造テク：前処理
累積和
二分探索:工夫して求めた配列上のlower_bound
ソート
AtCoder
AtCoder400点
茶色diff
ABC-D
Greedy
クエリ処理問題
制約条件:ある値<=K
最大回数・最大個数を求める
最適化問題
この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ！ 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…
NoviSteps2Q
AtCoder
AtCoder400点
茶色diff
ABC-D
二分探索
データ構造テク：前処理
二分探索:lower_bound
数列
クエリ処理問題
K番目を求める
二分探索:K番目を求める
二分探索:工夫して求めた配列上のlower_bound
色んな方法があるが、できるだけ楽にやりたい！ 問題へのリンク 問題概要 単調増加な 要素からなる数列 がある。この数列について、次の 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、 のどれとも異なる数値 (よい数と呼ぶこととする) のうち、…
