ABC274 C問題（Ameba）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）274 のC問題をC++とPythonで解いてみました。ABC274は、2022年10月22日21:00に実施されました。

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

C問題 Ameba（Difficulty : 315）

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

ABC274 C問題 Ameba

連想配列を使う問題です。AtCoder Problems による Difficulty は、315 でした。

解答案

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

• N と 数列 A_n を読み込む。
• A_n から、アメーバの分裂をシミュレーションする。アメーバの番号と組みにして世代数も記憶する。
• 最後に、アメーバ番号順に世代数を出力する。

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

アメーバの番号と世代数を組にして記憶する必要があります。このため map を使います。map のキーはアメーバ番号、値は世代数とします。その時点でのアメーバの数を max_no として記憶しておきます。以下が、解答例です。分裂のシミュレーション部分は背景色を変更しました。

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

int main()
{
	int n;
	cin >> n;
	map<int, int> m;

	int max_no = 1;
	m[1] = 0;
	for (int i = 0; i < n; ++i) {
		int t;
		cin >> t;
		m[max_no + 1] = m[t] + 1;
		m[max_no + 2] = m[t] + 1;
		max_no += 2;
	}

	for (auto it = m.begin(); it != m.end(); ++it) {
		cout << (*it).second << endl;
	}

	return 0;
}

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

Python プログラム例（ABC274C）

Python では、dict（辞書）を使います。考え方は、C++ と同じです。違いは、入力 A_i を一気に読んでいることと、出力が簡単に書けているところです。

"""AtCoder Beginner Contest 274 C"""
n = int(input())
a = list(map(int, input().split()))
m = {}
max_no = 1
m[1] = 0
for i in range(n):
    m[max_no + 1] = m[a[i]] + 1
    m[max_no + 2] = m[a[i]] + 1
    max_no += 2

print(*m.values(), sep="\n")

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

最後に

C++の map と Python の dict は、連想配列と呼ばれる入れ物です。連想配列を使う問題は、C問題で一定の割合を占めています。なお、連想配列は、一般的に順序を保つ保証はありません。C++ の map と Python 3.7 以降の dict は、順序を保ちます。

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