AtCoder

ABC296 A問題(Alternately)を解く

AtCoder_ABC296_A

AtCoder が提供しているABC(AtCoder Beginner Contest)296 のA問題をC++とPythonで解いてみました。ABC296は、2023年4月1日21:00に実施されました。

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

A問題 Alternately(Difficulty : 14)

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

ABC296 A問題 Alternately

与えられた文字列が条件を満たしているか判定する問題です。AtCoder Problems による Difficulty は 14 でした。

解答案

N と文字列 S を読み込み、問題の条件を満たしているか判断します。

C++ プログラム例(ABC296A)

文字列の文字が M と F が交互に並んでいるか確認します。条件を満たしているかを bool 型変数 result に格納します。初期値を true として、条件を満たさないときに false にしています。

最初の文字が M か F かでプログラムを分けました(12、20行目)。先頭の文字が M の場合は、添え字が偶数のときに M か、奇数のときに F かを確認しています(14-18行目)。先頭の文字が F の場合は、逆になります(22-26行目)。

A問題としては少し長くなりましたが、以下が、C++プログラムとなります。

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

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;

	bool result = true;
	if (s[0] == 'M') {
		for (int i = 1; i < n; ++i) {
			if ((i % 2 == 0)&&(s[i] != 'M')) {
				result = false;
			} else if ((i % 2 == 1)&&(s[i] != 'F')) {
				result = false;
			}
		}
	} else if (s[0] == 'F') {
		for (int i = 1; i < n; ++i) {
			if ((i % 2 == 0)&&(s[i] != 'F')) {
				result = false;
			} else if ((i % 2 == 1)&&(s[i] != 'M')) {
				result = false;
			}
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

問題の制約に「S は、M および F のみからなる」とあります。

文字が2種類しかないため、「交互に並んでいる」=「前の文字と異なる」と言い換えることができます。この制約を使ってプログラムの条件が簡単になりました(13行目)。

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

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;

	bool result = true;
	for (int i = 0; i < n - 1; ++i) {
		if (s[i] == s[i + 1]) {
			result = false;
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

どちらも AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC296A)

Python は、C++の2つ目のプログラムを移植しました。

"""AtCoder Beginner Contest 296 A"""
n = int(input())
s = input()

result = True
for i in range(n - 1):
    if s[i] == s[i + 1]:
        result = False

print("Yes" if result else "No")

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

最後に

最初に紹介したプログラムでは、文字を丁寧に確認しました。その後に制約を活かして、プログラムを簡潔に書くことができました。問題の言い換えは、上位でも必要なスキルだと考えています。

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

COMMENT

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

CAPTCHA