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 でした。
解答案
問題を解く方針を書きだします。
- 順列を読み込む。
- 読み込んだひとつ前の順列を求める。
- 求めた順列を表示する。
順列について、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 版はもっと良い書き方があるかもしれません。
引き続き ABC の問題を紹介していきます。
