AtCoder

ABC294 C問題(Merge Sequences)を解く

AtCoder_ABC294_C

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

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

C問題 Merge Sequences(Difficulty : 127)

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

ABC294 C問題 Merge Sequences

2つの数列をマージして、ソートした結果の添え字を元の数列の数字に適用する問題です。AtCoder Problems による Difficulty は 127 でした。

解答案

問題を以下の方針で解きます。

  • N、M と数列 A と数列 B を読み込む。
  • 数列 A と数列 B のすべての要素を含む数列 C を生成する。
  • 数列 C をソートする。
  • 数列 C の値と添え字(要素の順番)を紐づける。
  • 数列 C の紐づけを数列 A と数列 B の各要素に適用する。

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

数列 A と数列 B の要素を C に登録します。ソートした後に、map を使って、数字と要素の順番を紐づけます。その紐づけ情報を元の数列 A と数列 B の要素に適用します。

以下が、C++プログラムとなります。

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

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

	sort(c.begin(), c.end());

	map<int, int> temp;
	for (int i = 0; i < n + m; ++i) {
		temp[c[i]] = i + 1;
	}

	for (int i = 0; i < n; ++i) {
		cout << temp[a[i]] << " \n"[i == n - 1];
	}
	for (int i = 0; i < m; ++i) {
		cout << temp[b[i]] << " \n"[i == m - 1];
	}

	return 0;
}

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

Python プログラム例(ABC294C)

Python では、C++ の map の代わりに辞書を使います。辞書の内容を元の数列 A と数列 B に適用して、それぞれの数列を表示しています(11-12行目および14-15行目)。

"""AtCoder Beginner Contest 294 C"""
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = a + b
c = sorted(c)
temp = {}
for i in range(n + m):
    temp[c[i]] = i + 1

a = [temp[i] for i in a]
b = [temp[i] for i in b]

print(*a)
print(*b)

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

最後に

紐づけを map や辞書を使ってプログラムしました。よく使う手法なので、慣れておきたいです。

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

COMMENT

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

CAPTCHA