Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

EDPC W : Intervals

新年度になったので、リハビリがてら毎日なにかしら競技プログラミングの問題を解いていこうと思います。(余裕があればブログも更新していきたい……)

問題文 : https://atcoder.jp/contests/dp/tasks/dp_w

概要

日本語なので略。

解法

「1つ以上1を含んでいたら得点が入る」という設定だと解きづらいので、以下のように問題を言い換えて考えてみる。

長さ N の 0 と 1 からなる文字列を考えます。 この文字列のスコアを次のように計算します。

  •  i (1 \leqq i \leqq M) について、 l_i 文字目から  r_i 文字目までがすべて  0 なら、スコアに  -a_i を加算する。

初期状態のスコアが  \sum_{i=1}^{M} a_i のとき、文字列のスコアの最大値を求めてください。

すると、dp[i][j] :=  i 文字目を  j としたときのスコアの最大値、というDPを考えられる。 (1 \leqq i \leqq N, j \in \{ 0, 1\})
DPの漸化式の更新は、Starry Sky 木などのデータ構造を使うことで1状態ごとに \mathrm{O}(\log N)時間でできる。
したがって全体の時間計算量は  \mathrm{O}(N \log N) 時間となる。

コード

#include <bits/stdc++.h>

using namespace std;

static const int MAX_SIZE = 1 << 18;

typedef long long Int;

Int segMax[2 * MAX_SIZE - 1], segAdd[2 * MAX_SIZE - 1];

void add(int a, int b, Int x, int k = 0, int l = 0, int r = MAX_SIZE)
{
	if (r <= a || b <= l) return;
	
	if (a <= l && r <= b) {
		segAdd[k] += x;
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);

	segMax[k] = max(segMax[k * 2 + 1] + segAdd[k * 2 + 1], segMax[k * 2 + 2] + segAdd[k * 2 + 2]);
}

Int getMax(int a, int b, int k = 0, int l = 0, int r = MAX_SIZE)
{
	if (r <= a || b <= l) return (LLONG_MIN);
	
	if (a <= l && r <= b) return (segMax[k] + segAdd[k]);
	
	Int left = getMax(a, b, k * 2 + 1, l, (l + r) / 2);
	Int right = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
	
	return (max(left, right) + segAdd[k]);
}

Int black[200001], white[200001];
int main()
{
  int n, m;
  
  scanf("%d %d", &n, &m);
  
  vector< pair<pair<int, int>, int> > v;
  
  long long tot = 0;
  for (int i = 0; i < m; i++) {
    int l, r, a;
    scanf("%d %d %d", &l, &r, &a);
    tot += a;
    v.push_back(make_pair(make_pair(r, l), a));
  }
  sort(v.begin(), v.end());
  int p = 0;
  long long black_max, white_max;
  black_max = white_max = 0;
  for (int i = 1; i <= n; i++) {
    black[i] = max(black_max, white_max);
    black_max = max(black_max, black[i]);
    while (p < m && v[p].first.first == i) {
      add(0, v[p].first.second, -v[p].second);
      p++;
    }
    white[i] = getMax(0, i);
    white_max = max(white_max, white[i]);
    add(i, i + 1, black[i]);
  }
  
  printf("%lld\n", tot + max(black_max, white_max));
  return 0;
}

コメント

  • やることは比較的すぐに思いついたが、コード中の`add`関数の引数の型を間違えていることにずっと気づかずWrong Answerを出しまくってしまいました。
  • Introduction to Segment Tree に載っているStarry Sky木のコードの変数の型がおかしいことに気づきました。直しておきます。