ちゃんと考察する練習をしたメモ

こちらの記事で「ちゃんと考察してから解きましょうね」（超意訳）と書いてあり、最近はその練習をしています。

初心者が陥りがちな嘘貪欲やコーナーケースやその他諸々に関して - えびちゃんの日記

記事で例題として載っている問題について、コードを書いたので、そのメモ。あとからランダムなテストケースで確認できるように、愚直解もいっしょに載せる。

負の値を含む区間和の数え上げ

~~（気が向いたら考察書く。とりあえずコメントには書いてある）~~ → 書いた

負の値を含む数列の区間和を求めたい

まずはサンプル見てみる[] は最大となる区間を表す

1 2 3 -1000 [4 5] -1000 6
→ 9 が最大

[1 2 3 -1 4 5 -1 6]
 → 19が最大

考察のポイント

全探索を考えてみる
探索対象がふたつあって, O(N²)の時は, 一方を固定してみる
二分探索は単調性がある時に有効(今回は使えない)
ソート済み状態を保ちながら集合を管理したい時は, そういうデータ構造使うと便利
- set → 重複なし集合. 今回は負の値があるので, 累積和が重複するので NG
- multiset → 重複あり集合. 今回は集合の値が重複するので, 有効. 集合の任意の値の削除も O(logN)でできる
- priority_queue → 重複あり集合. 今回は見終わった値の削除がしたいが, priority_queue は最大の要素しか削除できないので NG
区間和は累積和を使うと, うまく求まる

考察(思考垂れ流し ver.)

区間を全探索で 2 重ループにすると O(N²)になって間に合わない
尺取っぽいな. 尺取で単調費減少の区間でやってみる
- 合計が減少したあとに, 最大値をとることがあるのでダメそう
でも, 区間を[l,r)とすると, l は固定して全探索しておきたい
区間を[l,r)の各 l での l<=r<=n の中での最大値がほしい(図参照)
l が固定されると, 累積和を使うとなんかうれしそう
累積和 sum[l]<=sum[r]の範囲で最大のものを求めたい
なんか, r を二分探索したいなあ. でも, 負の値があるので累積和の単調性がない
なんとかして, 常に区間[l,r)の累積和の集合が, ソート状態を保てるようにしたい
set とか multiset とか priority_queue だな.
set は重複取り除くのでダメ. priority_queue は見終わった値を取り除けないのでダメ.
multiset でできそうかも？
- 累積和計算して, multiset に突っ込む
- 集合の最大値 → multiset の末尾要素みればよい
- 見終わった区間を無視 → multiset から,現在の累積和 sum[0,l)を取り除く
- multiset に入ってるのは l=0 の時の累積和なので, 区間和[l,r)じゃないよね？
- → 取り除いた累積和[0,l)を引けば, 区間和[l,r) になる

コーナーケース

区間[l, l) = 区間をひとつも選ばない時はあるのか？
- 0<=l<=r<=n なので, ありえる. a の要素がすべて負の時は, [l,l)=0 が最大となる
区間の数の最小は？
- n=1. 上記解法で n=1 の場合も正常に動くはず
区間やループ範囲に気をつける
- l を全探索 0<=l<=n
- mutiset から取り除くのは sum[l] は大丈夫？
  - l=0 の時, 0 が取り除かれる.
  - l=1 の時, a[0]が取り除かれる.
  - l=2 の時, a[0]+a[1]が取り除かれる.
  - 見終わった累積和[0,l)が取り除かれてるので大丈夫そう

コード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const long double EPS = 1e-14;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = a; i < b; ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto i : a)
#define all(obj) (obj).begin(), (obj).end()
template <typename T> inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T> inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }

/**
 * 考察メモ
 *
 * (案)
 * - 区間[l, r)とすると,
 * - lをi<nで全探索
 * - aをセグ木にのせて, 各lでのrを求めて, 値を求める
 * うーん、いまいちダメそう
 *
 * (案)
 * - 区間を正の区間と負の区間に区切って, 配列を再度つくる.
 * - {-, +, -, +,..}みたいな配列が出来上がる
 * - 符号ごとに累積和をとっておくとうれしい？
 * うーん、よくわからん
 *
 * (案)　※有力
 * 累積和を取って, multiset に突っ込む
 * lを走査しながら, multiset から一番大きい数字を出力.
 * l+1に行く時に, multiset から累積和のl要素を削除する
 *
 */
// NOTE: 型は？ → 10^9 * 10^5 = 10^14 で ll

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  // 累積和
  a.insert(a.begin(), 0);
  vector<ll> sum(n + 1);
  inclusive_scan(all(a), sum.begin());

  // multisetに突っ込む
  multiset<ll> s;
  rep(i, n + 1) s.insert(sum[i]);

  // NOTE: ループ範囲を詰めていない. 怪しいかも
  // lを走査しながら, multisetから一番大きい区間を探す
  ll ans = 0;
  rep(l, n + 1) {
    auto it = s.end();
    --it;
    chmax(ans, *it - sum[l]);
    s.erase(s.find(sum[l]));
  }
  cout << ans << endl;
}

愚直解

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const long double EPS = 1e-14;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = a; i < b; ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto i : a)
#define all(obj) (obj).begin(), (obj).end()
template <typename T> inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T> inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// 関数定義------------------

// メイン------------------
int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  a.insert(a.begin(), 0);
  vector<ll> sum(n + 1);
  inclusive_scan(all(a), sum.begin());

  ll ans = 0;
  rep(l, n + 1) rep(r, l, n + 1) chmax(ans, sum[r] - sum[l]);
  cout << ans << endl;
}

nakashiiiの自由帳

自由に書きます

ちゃんと考察する練習をしたメモ

負の値を含む区間和の数え上げ

考察のポイント

考察(思考垂れ流し ver.)

コーナーケース

コード

愚直解