H - Candles Editorial by mechanicalpenciI


明らかにそれぞれのろうそくの火はすでに燃え尽きていない限り訪れた瞬間に消すのが最善です。また、\(10^{100}\) 分は十分に長いため、すべてのろうそくのある座標を訪れるとして良いです。(燃え尽きた後に訪れるものも含みます。)そして、訪れるろうそくの順番を \(1\) つ定めると、最短距離、最速で次のろうそくへ向かうのが最適です。これより、常に速度は \(1\) 、また方向転換はろうそくのある地点でしか行わないとして良いです。

また、以降の説明を簡単にするため、座標 \(0\) に時刻 \(0\) で長さ \(0\) のろうそくが立っているとします。これによって答えが変わる事はありません。以降出てくる \(N\) は 元の値に \(1\) を加えたものであることに注意してください。そしてろうそくの位置を\(X_1<X_2<\cdots <X_N\)とし、高橋君が \(X_i\) を初めて訪れたとき、高橋君が訪れたことがある範囲は \([X_i,X_j]\) または \([X_j,X_i]\) で表され、次訪れるろうそくは前者なら(それぞれ存在するなら) \(X_{i-1}\) または \(X_{j+1}\), 後者ならば\(X_{j-1}\) または \(X_{i+1}\)となります。この事から最後に訪れるろうそくは\(X_1\)または\(X_L\)にあるものという事も分かります。

次に問題設定を少し変更することを考えます。 具体的には、

  • ろうそくの火は燃え尽きず、負の長さを取り得る。
  • 行動を始める前に高橋君はいくつかのろうそくを取り除くことができる。(取り除かれたろうそくは最終的な長さの和に一切関係しない)

という変更を加えます。この時の答えは元の問題と同じになります。明らかにこの変更によって元の問題より答えが大きくなることはないですが、新しい設定の下でも、「元の問題で答えを最大化する行動をしたときすでに燃え尽きてしまっているろうそくを事前に取り除いておく」という行動によって元の問題で達成できた値を得ることができるからです。 [](以下、高橋君が火を消さない限りろうそくが(負の長さになって)燃え続けていると考えることにします。)

これによってろうそくが時間経過で燃え尽きることが無くなり、\(1\) 分あたりのろうそくの長さの総和の減少分は \(N-(最初に取り除いた本数)-(すでに高橋君が火を消した本数)\) で表すことができます。この「残り本数」に注目する事で、問題は結局次のようなものと考えられます。

  • 高橋君は最初カウンターを持って座標 \(0\) に立っており、スコアは \(0\) である。
  • カウンターの値 \(C\) は最初に \(0\) 以上 \(N\) 以下の整数値を自由に設定できる。
  • 座標 \(X_i\) に値 \(H_i\) が定まっている。
  • 高橋君は自分の座標を \(+1\) または \(-1\) するように移動できる。 \(\pm 1\) 移動するたびにスコアは \(C\) 減少する。(負の値も取り得る。)
  • 高橋君は初めて座標 \(X_i\) に訪れて、カウンターの値が \(C>0\) であるとき、カウンターの値を \(1\) 減少させてスコアに \(H_i\) を加えるか選ぶことができる。
  • このときの最終的なスコアを最大化させたい。

これは、次のような動的計画法を用いて解くことができます。
\(dp[i][j][flag][k]\) を今までに訪れた区間は \([X_i,X_j]\) であり、今、(\(flag=0\) ならば左端 \(X_i\) , \(flag=1\)ならば右端 \(X_j\) )にいる状態で、その座標での選択を終えた後のカウンターの値が \(k\) であるときの、これ以降のスコアの増減の最大値(現在のスコアを \(s\) とすると、これ以降最善な行動を行ったときの最終的なスコアは \(s\) によらない定数 \(k\) を用いて \(s+k\) と書け、その \(k\) の値)で定めます。
ここで、添字の範囲は \(1\leqq i\leqq j\leqq N\) , \(flag=0\) or \(1\) , \(0\leqq k \leqq N-(j-i+1)\) です。

初期値は \(dp[1][N][flag][0]=0\) であり、求めたいものは\(X_{i_0}=0\)となる\(i_0\)を用いて\(\displaystyle\max_{0\leq k\leq N-1} dp[i_0][i_0][flag][k]\) で与えられます。(\(k=N\) を考える必要が無いのは高さ \(0\) のろうそくが含まれているからです。) 遷移については、\(dp[i][j][flag][k]\)\(dp[i-1][j][flag][k-1]\) , \(dp[i-1][j][flag][k]\) , \(dp[i][j+1][flag][k-1]\) , \(dp[i][j+1][flag][k]\) の値から \(O(1)\) で求められるため、 遷移は全体で \(O(N^3)\) であり、十分高速です。

よって、この問題を解く事が出来ました。

c++による実装例:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N (ll)302
#define INF (ll)4000000000000000001
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rep3(i, a, b) for(ll i = a; i >= b; --i)
#define all(c) (c).begin(), (c).end()


int main(void) {
	ll n, x, y, d;
	vector<pair<ll, ll> >c;
	ll dp[N][2][N];
	ll dp2[N][2][N];
	ll i0;
	ll ans = 0;
	cin >> n;
	d = 0;
	rep(i, n) {
		cin >> x >> y;
		if (x == 0) {
			d++;
			ans += y;
		}
		else c.pb({ x,y });
	}
	n = n + 1 - d;
	c.pb({ 0,0 });
	sort(all(c));
	rep(i, n) {
		if (c[i].second == 0)i0 = i;
	}
	rep(i, N) {
		rep(ii, 2) {
			rep(j, N) {
				dp[i][ii][j] = -INF;
				dp2[i][ii][j] = -INF;
			}
			dp[i][ii][0] = 0;
		}
	}
	rep3(j, n - 2, 0) {
		rep(i, n - j) {
			rep2(k, 1, n - j - 1) {
				if (i > 0) {
					dp2[i][0][k] = max(dp2[i][0][k], dp[i - 1][0][k] - (k*(c[i].first - c[i - 1].first)));
					dp2[i][0][k] = max(dp2[i][0][k], dp[i - 1][0][k - 1] + c[i - 1].second - (k*(c[i].first - c[i - 1].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i - 1][0][k] - (k*(c[i + j].first - c[i - 1].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i - 1][0][k - 1] + c[i - 1].second - (k*(c[i + j].first - c[i - 1].first)));
				}
				if ((i + j) < (n - 1)) {
					dp2[i][0][k] = max(dp2[i][0][k], dp[i][1][k] - (k*(c[i + j + 1].first - c[i].first)));
					dp2[i][0][k] = max(dp2[i][0][k], dp[i][1][k - 1] + c[i + j + 1].second - (k*(c[i + j + 1].first - c[i].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i][1][k] - (k*(c[i + j + 1].first - c[i + j].first)));
					dp2[i][1][k] = max(dp2[i][1][k], dp[i][1][k - 1] + c[i + j + 1].second - (k*(c[i + j + 1].first - c[i + j].first)));
				}
			}
		}
		rep(i, n - j) {
			rep2(k, 1, n - j - 1) {
				rep(ii, 2) {
					dp[i][ii][k] = dp2[i][ii][k];
					dp2[i][ii][k] = -INF;
				}
			}
		}
	}

	x = 0;
	rep(k, n) {
		x = max(x, dp[i0][0][k]);
		x = max(x, dp[i0][1][k]);
	}
	ans += x;
	cout << ans << endl;

	return 0;
}

posted:
last update: