ABC314 C問題（Rotate Colored Subsequence）を解く

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

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

C問題 Rotate Colored Subsequence（Difficulty : 342）

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

ABC314 C問題 Rotate Colored Subsequence

色ごとに出現する場所を記憶して処理します。AtCoder Problems による Difficulty は 342 でした。

解答案

前準備として、各色が出現する場所を記憶しておきます。それぞれの色が何文字出現したかも記憶していき、該当する文字を出力していきます。

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

以下、配列の添え字は0からカウントします。

• 文字列の i 文字目の色を c[i] として格納します（16行目）。
• 色 i が出現する場所を配列 color[i] として格納しておきます（17行目）。
• 出力する文字を以下の条件で求めます。
  • 各色が何回でたか配列 p で管理する（初期値 0）。
  • i 文字目の色は c[i]
  • color[c[i]] の中から一文字シフトした文字を出力します。シフトする文字は color[c[i]] の長さの剰余として求めています（23行目）。
  • 配列 p[c[i]] を更新する（24行目）。

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

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

int main()
{
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	vector<vector<int>> color(m);
	vector<int> c(n);
	for (int i = 0; i < n; ++i) {
		int t;
		cin >> t;
		--t;
		c[i] = t;
		color[t].push_back(i);
	}

	vector<int> p(m, 0);
	for (int i = 0; i < n; ++i) {
		int mod = color[c[i]].size();
		cout << s[color[c[i]][(p[c[i]] - 1 + mod)% mod]];
		++p[c[i]];
	}
	cout << endl;

	return 0;
}

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

Python プログラム例（ABC314C）

考え方はC++と同じです。ただし、文字列の値を書き換えることができないため、空文字列 result を用意して文字を追加していきました（11、14行目）。

"""AtCoder Beginner Contest 314 C"""
n, m = map(int, input().split())
s = input()
c = list(map(int, input().split()))
color = [[] for i in range(m)]
for i in range(n):
    c[i] -= 1
    color[c[i]].append(i)

p = [0] * m
result = ""
for i in range(n):
    mod = len(color[c[i]])
    result += s[color[c[i]][(p[c[i]] - 1 + mod) % mod]]
    p[c[i]] += 1

print(result)

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

最後に

各色の文字をシフトする演算は少し複雑ですが、うまくプログラムで表現することができました。

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