AtCoder

ABC274 C問題(Ameba)を解く

AtCoder_ABC274_C

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 でした。ABC C問題としては、標準的な難易度の問題です。

解答案

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

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

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++ と同じです。違いは、入力 Ai を一気に読んでいることと、出力が簡単に書けているところです。

"""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 は、順序を保ちます。

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

COMMENT

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

CAPTCHA