AtCoder

ABC276 C問題(Previous Permutation)を解く

AtCoder_ABC276_C

AtCoder が提供しているABC(AtCoder Beginner Contest)276 のC問題をC++とPythonで解いてみました。ABC276は、2022年11月5日21:00に実施されました。

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

C問題 Previous Permutation(Difficulty : 389)

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

ABC276 C問題 Previous Permutation

与えられた順列のひとつ前の順列を求める問題です。AtCoder Problems による Difficulty は、389 でした。ABC C問題として、標準的な問題です。

解答案

問題を解く方針を書きだします。

  • 順列を読み込む。
  • 読み込んだひとつ前の順列を求める。
  • 求めた順列を表示する。

順列について、Project Euler 問題24(辞書式順列)で紹介してます。

C++ プログラム例(ABC276C)

C++ には、次の順列を求める next_permutation があります。ただし、問題では、ひとつ前の順列を求める必要があります。このため、順列の要素の順番を逆転して、ひとつ先の順列を求めます。この順列の要素の順番を再び逆転することにより、ひとつ前の順列が得られます。

以下がプログラムとなります。順列の要素を逆転させているコードの背景色を変更しています。

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

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

	for (int i = 0; i < n; ++i) {
		p[i] = n + 1 - p[i];
	}
	next_permutation(p.begin(), p.end());
	for (int i = 0; i < n; ++i) {
		p[i] = n + 1 - p[i];
	}

	for (int i = 0; i < n; ++i) {
		if (i > 0) {
			cout << " ";
		}
		cout << p[i];
	}
	cout << endl;

	return 0;
}

そもそも、無理に next_permutation を使う必要はありません。ひとつ前の順列を求める prev_permutation があるからです。これを使えば、すっきりと書くことができます。

以下は、prev_permutation を使ったプログラムとなります。

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

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

	prev_permutation(p.begin(), p.end());

	for (int i = 0; i < n; ++i) {
		if (i > 0) {
			cout << " ";
		}
		cout << p[i];
	}
	cout << endl;

	return 0;
}

どちらも AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC276C)

Python では、itertools.permutations がありますが、$2 \leqq N \leqq 1000$ の範囲では、計算量もメモリ使用量も非常に多くなります。

C の道具箱で紹介した次の順列を求める関数 next_perm を Python に移植して使うことにします。ただし移植する場合、次の順列があることを前提にしました。以下は、ベースとなる C 版の関数 next_perm のプログラムです。

int next_perm(int p[], int n)
{
    int i, j, t;

    i = n - 2;
	while ((i >= 0)&&(p[i] >= p[i + 1])) {
		--i;
	}
	if (i == -1) {
		return 0;
	}

	j = n - 1;
	while (p[i] >= p[j]) {
		--j;
	}
	t = p[i];
	p[i] = p[j];
	p[j] = t;
	++i;
	j = n - 1;
	while (i < j) {
		t = p[i];
		p[i] = p[j];
		p[j] = t;
		++i;
		--j;
	}

	return 1;
}

C++ の next_permutation を使った場合と同じように順列の要素を逆転して、次の順列を求めた後、再び順列の要素を逆転します。

移植した Python 関数も含めたプログラムは、以下となります。

"""AtCoder Beginner Contest 276 C"""


def next_perm(p, n):
    i = n - 2
    while i >= 0 and p[i] >= p[i + 1]:
        i -= 1
    j = n - 1
    while p[i] >= p[j]:
        j -= 1
    p[i], p[j] = p[j], p[i]
    i += 1
    j = n - 1
    while i < j:
        p[i], p[j] = p[j], p[i]
        i += 1
        j -= 1
    return p


n = int(input())
p = list(map(int, input().split()))
for i in range(n):
    p[i] = n + 1 - p[i]
p = next_perm(p, n)
for i in range(n):
    p[i] = n + 1 - p[i]
print(*p)

こちらも「AC」と判定されました。

最後に

順列についての問題でした。言語によって、ライブラリが用意している機能に差があるため、C++ 版と Python 版でだいぶ異なるプログラムになりました。まだ Python に慣れていません。Python 版はもっと良い書き方があるかもしれません。

ABC276 について、引き続き、D問題まで紹介します。

COMMENT

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

CAPTCHA