AtCoder

ABC287 D問題(Match or Not)を解く

AtCoder_ABC287_D

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

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

D問題 Match or Not(Difficulty : 796)

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

ABC287 D問題 Match or Not

下準備をすることにより間に合う問題です。AtCoder Problems による Difficulty は 796 でした。

解答案

問題文に従い、S’ を生成して、T と比較して、”Yes” か “No” を出力するプログラムを紹介します。プログラムでは、S’ を変数 temp_t としています。

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

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

	for (int i = 0; i <= t.length(); ++i) {
		string temp_t = s.substr(0, i) + s.substr(s.length() - t.length() + i);
		bool result = true;
		for (int j = 0; j <= t.length(); ++j) {
			if ((temp_t[j] != '?')&&(t[j] != '?')&&(temp_t[j] != t[j])) {
				result = false;
				break;
			}
		}
		if (result) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}

	return 0;
}

文字列 T の長さの上限がほぼ 3 × 105 です。一方、内側のループは、T の長さの二乗の回数演算するため、残念ながらいくつかのテストケースで TLE(Time Limit Exceeded)判定となりました。

計算量を少なくする工夫が必要になります。

二つの Bool 型の配列 left と right を導入します。

left[i] は、文字列 S と T の先頭(左)から、i 文字が一致しているか、’?’ 込みで判断した内容を保持しておきます。

right[i] は、left と逆に文字列 S と T の最後(右)から、i 文字が一致しているか、’?’ 込みで判断した内容を保持しておきます。

配列 left と right をあらかじめ計算しておけば、S’ と T が一致するかは、left[i] とright[|T| – i] の論理積によって判断できます。

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

配列 left と right は、ある添え字 i で false になれば、それ以降の値は、すべて false になります(14-15行、18-19行)。

S’ が T と一致判定は、すっきりと書けています(23行目)。

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

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

	vector<bool> left(t.length() + 1);
	vector<bool> right(t.length() + 1);
	left[0] = true;
	right[0] = true;
	for (int i = 0; i < t.length(); ++i) {
		left[i + 1] = left[i]
		            && ((s[i] == '?')||(t[i] == '?')||(s[i] == t[i]));
		int si = s.length() - 1 - i;
		int ti = t.length() - 1 - i;
		right[i + 1] = right[i]
		             && ((s[si] == '?')||(t[ti] == '?')||(s[si] == t[ti]));
	}

	for (int i = 0; i <= t.length(); ++i) {
		if (left[i] && right[t.length() - i]) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}

	return 0;
}

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

Python プログラム例(ABC287D)

Python 版も、C++ を移植しました。

"""AtCoder Beginner Contest 287 D"""
s = input()
t = input()

left = [False] * (len(t) + 1)
left[0] = True
right = [False] * (len(t) + 1)
right[0] = True
for i in range(len(t)):
    left[i + 1] = left[i] and \
                  (s[i] == '?' or t[i] == '?' or s[i] == t[i])
    si = len(s) - 1 - i
    ti = len(t) - 1 - i
    right[i + 1] = right[i] and \
                   (s[si] == '?' or t[ti] == '?' or s[si] == t[ti])

for i in range(len(t) + 1):
    print("Yes" if left[i] and right[len(t) - i] else "No")

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

Python は記述性が良いのですが、C++ プログラムを移植すると時間的に不利になることが多いです。しかし、このD問題については、Python 版の方が実行時間が短かったです。

最後に

あらかじめ計算することにより、繰り返されるクエリの計算量を下げる工夫は、累積和の場合と似ているかもしれません。コンテスト中にうまく気づくことができました。このような工夫で正解できるとプログラミングが楽しくなります。

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

COMMENT

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

CAPTCHA