AtCoder

ABC339 E問題(Smooth Subsequence)を解く

AtCoder_ABC339_E

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+1, 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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA