ABC378 C問題（Repeating）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）378 C問題をC++とPythonで解いてみました。ABC378は、2024年11月2日21:00に実施されました。

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

C問題 Repeating（Difficulty : 191）

問題の詳細は、リンク先をご覧ください。

ABC378 C問題 Repeating

連想配列を使って直前に出現した位置を記録します。AtCoder Problems による Difficulty は 191 でした。

解答案

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

その値が最後に出現した場所を記録するだけです。$1 \leqq A_i \leqq 10^9$ という制約が大きいため、配列での格納が難しいです。

このため、連想配列（map）を使います。連想配列であれば、出現した整数だけ記憶するだけです。最大 $2 \times 10^5$ 箇所の整数の場所であれば格納できます。

以下が、C++プログラムです。

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

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

	map<int, int> last;
	vector<int> b(n, -1);
	for (int i = 0; i < n; ++i) {
		if (last.find(a[i]) != last.end()) {
			b[i] = last[a[i]];
		}
		last[a[i]] = i + 1;
	}

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

	return 0;
}

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

Python プログラム例（ABC378C）

Python版も基本的な考え方は同じです。初期値がない場合に参照しないため、組込み型の辞書が使えます。以下がプログラムです。

"""AtCoder Beginner Contest 378 C"""
n = int(input())
a = list(map(int, input().split()))

last = {}
b = [-1] * n
for i in range(n):
    if a[i] in last:
        b[i] = last[a[i]]
    last[a[i]] = i + 1

print(*b)

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

最後に

連想配列が必要でない場合も配列ではなく連想配列を使うことがあります（例えば、ABC378A問題の解説をご覧ください）。この問題では、連想配列が必要となるため、制約と実装が合って気分的にはすっきりしました。

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