ABC352 D問題（Permutation Subsequence）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）352 のD問題をC++で解いてみました。ABC352は、2024年5月4日21:00に実施されました。

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

D問題 Permutation Subsequence（Difficulty : 714）

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

ABC352 D問題 Permutation Subsequence

与えられた数列と添え字の関係を使います。AtCoder Problems による Difficulty は 714 でした。

解答案

一読しただけでは、問題の意味が分かりませんでした。このような場合は、入力例の確認です。入力例3を確認します。$N=10, K=5$ です。

この関係を逆にして、特定の Pi の位置を示したものが以下です。

上の表から、連続する5個の要素を取り出します。

i₅ – i₁ の最小値は、5となります。

以下の手順で解が求まることが分かりました。

• 数列 P_i の逆の関係の数列を考える。
• 添え字の数列から最初K個を格納して、最大値（i_K）と最小値（i₁）を求める。
• 次の数列の要素を加える。
• 先頭の要素を削除する。
• この時点での最大値と最小値を求める。

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

次のことができるコンテナが必要です。

• 要素の追加が速くできる。
• 要素の削除が速くできる。
• コンテナの要素の最大値が速く取り出せる。
• コンテナの要素の最小値が速く取り出せる。

C++のsetコンテナは以上を満たします。イテレータ begin() で最小値が、イテレータ rbegin() で最大値を示す場所が取れます。

なお、逆の関係の数列 r[i] は、0からカウントするようにしました。以下が、C++プログラムです。ポイントとなる行の背景色を変更しました。

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

#define INF (1 << 30)

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> p(n), r(n);
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
		r[p[i] - 1] = i;
	}

	set<int> s;
	for (int i = 0; i < k; ++i) {
		s.insert(r[i]);
	}
	int result = *s.rbegin() - *s.begin();
	for (int i = k; i < n; ++i) {
		s.insert(r[i]);
		s.erase(r[i - k]);
		result = min(result, *s.rbegin() - *s.begin());
	}

	cout << result << endl;

	return 0;
}

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

Python の標準ライブラリの set は、順序付きではないため、プログラムの紹介を省略します。

最後に

コンテストで、D問題の意味が一読して分からず、E問題を先に解いていました。E問題を解いた後に入力例を検討して問題の意味するところが分かりました。

今回のコンテストは、E問題までとF問題以降で難易度に差がありました。このような場合、E問題までを速くとことがわたしの実力ではレート向上に必要になってきます。問題の読解力も向上させる必要があるかもしれません。

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