ABC352 B問題（Typing）を解く

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

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

B問題 Typing（Difficulty : 55）

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

ABC352 B問題 Typing

長さが異なる2つの文字列を比較していきます。AtCoder Problems による Difficulty は 55 でした。

解答案

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

文字列 s のインデックス s_index と文字列 t のインデックス t_index を用意します。ふたつの文字列 s と t の文字が一致するまで、t_index を進めます（13ー15行目）。

一致した t_index を記憶しておく、後でまとめて出力します（22行目）。

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

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

int main()
{
	string s, t;
	cin >> s >> t;

	vector<int> result;
	int s_index = 0;
	int t_index = 0;
	while (s_index < s.length()) {
		while (s[s_index] != t[t_index]) {
			++t_index;
		}
		result.push_back(t_index + 1);
		++s_index;
		++t_index;
	}

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

	return 0;
}

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

Python プログラム例（ABC352B）

Python 版も基本的な考え方は同じです。以下がそのプログラムです。

"""AtCoder Beginner Contest 352 B"""
s = input()
t = input()

result = []
s_index = 0
t_index = 0
while s_index < len(s):
    while s[s_index] != t[t_index]:
        t_index += 1
    result.append(t_index + 1)
    s_index += 1
    t_index += 1

print(*result)

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

最後に

今回のプログラムでは、一番上のレベルの繰り返し文に while を使いました。今回は、2つのインデックスを操作する必要があります。for 文で s_index を制御して、t_index を for 文の本体で制御する必要があります。このように制御変数が散らばる場合には、while 文の方が抜け漏れが少なくなると考えています。制御変数の対称性が見やすくなります。

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