ABC339 E問題（Smooth Subsequence）を解く

AtCoder が提供している（AtCoder Beginner Contest）339 のE問題をC++とPythonで解いてみました。ABC339は、2024年2月3日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

E問題 Smooth Subsequence（Difficulty : 1109）

問題はリンク先をご覧ください。

ABC339 E問題 Smooth Subsequence

数列の範囲内の最大値を使って更新していきます。AtCoder Problems による Difficulty は 1109 でした。

解答案

セグメント木を使います。

C++ プログラム例（ABC339E）

プログラムのポイントです。

• 最大値を求めるセグメント木を用意します（25行目）。
• 数列の要素 a[i] の値に対して、前後 D の範囲の最大値を探して（29行目）、それに1を加えた値で更新します（30行目）。
• セグメント木の要素で最大値を出力します（33行目）。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;

int op(int a, int b)
{
	return max(a, b);
}

int e()
{
	return 0;
}

int main()
{
	int n, d;
	cin >> n >> d;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	segtree<int, op, e> seg(500000+2);
	for (int i = 0; i < n; ++i) {
		int L = max(1, a[i] - d);
		int R = min(500000, a[i] + d);
		int t = seg.prod(L, R + 1);
		seg.set(a[i], t + 1);
	}

	cout << seg.all_prod() << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python のセグメント木について

Python は、セグメント木を標準ライブラリとしては用意していません。このブログの Python プログラムは、なるべく言語標準のライブラリで実装したいと考えています。このような事情で、この記事では、Python に移植したプログラムの紹介を省略します。

最後に

値をセグメント木に格納して処理する問題でした。仕組みが分かれば、それほど難しくない問題だと考えています。

引き続き ABC の問題を紹介していきます。