AtCoder

ABC279 E問題(Cheating Amidakuji)を解く

AtCoder_ABC279_E

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

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

E問題 Cheating Amidakuji(Difficulty : 1390)

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

ABC279 E問題 Cheating Amidakuji

前からの結果を先に求めてから、その後で後ろからのあみだくじを組み合わせます。AtCoder Problems による Difficulty は、1390 でした。

解答案

1 から $N$ までの選択肢があり、$M$ 本の横棒があるあみだくじを考えます。$i$ 本目の横棒を抜いたときに、1 が行く先を出力する問題です。

  • 前から 1 がどこに移るのか、求めておきます。
  • 後ろからのあみだくじを求めておいた、前からの結果と組み合わせます。

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

以下は、プログラムの補足です。

  • 配列 pre に、1 の行き先を格納します(13ー23行目)。
  • 配列 post には、後ろから考えたあみだくじを格納します。初期値は、post[i] = i となります(25ー28行目)。
  • 後ろから考えたあみだくじに、前から求めた結果をあわせます(31行目)。
    • あみだくじを更新します(32ー34行目)。
  • 配列 result は、逆に格納されているため、反転して出力します(37ー40行目)。

プログラムは、以下となります。

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

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

	vector<int> pre(m);
	pre[0] = 1;
	for (int i = 0; i < m - 1; ++i) {
		if (pre[i] == a[i]) {
			pre[i + 1] = pre[i] + 1;
		} else if (pre[i] == a[i] + 1) {
			pre[i + 1] = pre[i] - 1;
		} else {
			pre[i + 1] = pre[i];
		}
	}

	vector<int> post(n + 1);
	for (int i = 1; i <= n; ++i) {
		post[i] = i;
	}
	vector<int> result;
	for (int i = m - 1; i >= 0; --i) {
		result.push_back(post[pre[i]]);
		int t = post[a[i]];
		post[a[i]] = post[a[i] + 1];
		post[a[i] + 1] = t;
	}

	reverse(result.begin(), result.end());
	for (int i = 0; i < result.size(); ++i) {
		cout << result[i] << endl;
	}	

	return 0;
}

このプログラムは、AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC279E)

Python版も基本的な考え方は同じです。以下がプログラムです。

"""AtCoder Beginner Contest 279 E"""
n, m = map(int, input().split())
a = list(map(int, input().split()))

pre = [0] * m
pre[0] = 1
for i in range(m - 1):
    if pre[i] == a[i]:
        pre[i + 1] = pre[i] + 1
    elif pre[i] == a[i] + 1:
        pre[i + 1] = pre[i] - 1
    else:
        pre[i + 1] = pre[i]

post = [0] * (n + 1)
for i in range(1, n + 1):
    post[i] = i

result = []
for i in range(m - 1, -1, -1):
    result.append(post[pre[i]])
    post[a[i]], post[a[i] + 1] = post[a[i] + 1], post[a[i]]

result.reverse()
print(*result, sep='\n')

このプログラムも「AC」と判定されました。

最後に

当時、ABC279 はD問題まで解けました。E問題は問題を読んであきらめました。前に解けなかった問題を、実力向上のため解いています。

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

COMMENT

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

CAPTCHA