AtCoder

ABC307 B問題(racecar)を解く

AtCoder_ABC307_B

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

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

B問題 racecar(Difficulty : 70)

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

ABC307 B問題 racecar

与えられた文字列を連結した文字列が回文となっているか判断する問題です。AtCoder Problems による Difficulty は 70 でした。

問題タイトル “racecar” も回文になっています。

解答案

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

プログラムの注意点と工夫は以下です。

  • 自分自身を繰り返す文字列は対象となりません(30ー32行目)。
  • 与えられた文字列が回文か判定する関数 is_ok を分けました(4ー16行目)。
  • 変数 result の初期値は false として、ひとつでも回文が見つかれば、true になります(27、34行目)。

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

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

bool is_ok(string s)
{
	int size = s.length();

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

	return result;
}

int main()
{
	int n;
	cin >> n;
	vector<string> s(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}

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

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

	return 0;
}

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

Python プログラム例(ABC307B)

Python 版は、C++ のプログラムを移植しました。回文を求める関数 is_ok では、添え字で負の数が使えるため、C++ よりもすっきりと書けています(9行目)。

"""AtCoder Beginner Contest 307 B"""


def is_ok(s):
    size = len(s)

    result = True
    for i in range(size // 2):
        if s[i] != s[-(i + 1)]:
            result = False

    return result


n = int(input())
s = [input() for i in range(n)]

result = False
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if is_ok(s[i] + s[j]):
            result = True

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

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

最後に

回文か判定する基本的な問題でした。このような問題も制約を読み落とさず解きたいです。

ABC307 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA