B - Postal Card 解説 by KoD
想定解 : 二重ループを用いて実装する
それぞれの \(i = 1, 2, \dots, N\) について、\(j = 1, 2, \dots, M\) を全て試し、\(S_i\) の末尾 \(3\) 文字が \(T_j\) と一致するかどうかを判定することで正解することができます。
変数 count
を 0
で初期化し、\(i = 1, 2, \dots, N\) それぞれに対して、以下の処理を行います。
- 真偽値変数
found
をfalse
で初期化する。これは条件を満たす \(j\) が見つかったかどうかを表す。 - \(j = 1, 2, \dots, M\) に対して、以下の処理を行う。
- \(S_i\) の末尾 \(3\) 文字が \(T_j\) と一致しているなら、
found
にtrue
を代入する。
- \(S_i\) の末尾 \(3\) 文字が \(T_j\) と一致しているなら、
found
の値がtrue
ならcount
の値を1
増やす。
文字列 S
の末尾 \(3\) 文字を得る方法は言語に応じて様々です。C++ なら S.substr(S.size() - 3)
(S.size() == 6
なので S.substr(3)
と等価) とし、Python なら S[-3:]
とすればよいです。
実装例 (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n), t(m);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
for (int j = 0; j < m; ++j) {
cin >> t[j];
}
int answer = 0;
for (int i = 0; i < n; ++i) {
string suffix = s[i].substr(3);
bool match = false;
for (int j = 0; j < m; ++j) {
if (suffix == t[j]) {
match = true;
}
}
if (match) {
answer += 1;
}
}
cout << answer << '\n';
return 0;
}
実装例 (Python)
n, m = map(int, input().split())
s = [input() for _ in range(n)]
t = [input() for _ in range(m)]
answer = 0
for i in range(n):
found = False
for j in range(m):
if s[i][-3:] == t[j]:
found = True
if found:
answer += 1
print(answer)
別解 1 : 二分探索で \(T_j\) を見つける
こちらは少し高度な内容です。\(T_1, T_2, \dots, T_M\) を辞書順で昇順に並べ替えておくと、これらの中に指定された文字列が存在するかどうかを \(O(\log M)\) で検索することができます。制約が \(1 \leq N, M \leq 2\times 10^5\) と大きくなった場合、想定解では実行時間制限に間に合いませんが、この方法なら余裕を持って間に合います。
実装例 (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n), t(m);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
for (int j = 0; j < m; ++j) {
cin >> t[j];
}
sort(begin(t), end(t));
int answer = 0;
for (int i = 0; i < n; ++i) {
if (binary_search(begin(t), end(t), s[i].substr(3))) {
answer += 1;
}
}
cout << answer << '\n';
return 0;
}
別解 2 : 入力の特性を利用する
\(S_i\) は \(0\) 以上 \(10^6\) 未満の整数に対応し、\(T_j\) は \(0\) 以上 \(10^3\) 未満の整数に対応しています。\(S_i\) が表す整数を \(S_i'\)、\(T_j\) が表す整数を \(T_j'\) とおくと、\(S_i\) の末尾 \(3\) 文字が \(T_j\) に一致することは \(S_i'\) を \(10^3\) で割ったあまりが\(T_j'\) に等しいことと同値です。よって、\(k = 0, 1, \dots, 10^3 - 1\) に対し、\(T_j' = k\) となる \(j\) が存在するかどうかを求めておくことで、各 \(i\) に対し条件を満たす \(j\) が存在するかどうかを定数時間で求めることができます。
実装例 (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> s(n);
array<bool, 1000> exist = {};
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
for (int j = 0; j < m; ++j) {
int t;
cin >> t;
exist[t] = true;
}
int answer = 0;
for (int i = 0; i < n; ++i) {
if (exist[s[i] % 1000]) {
answer += 1;
}
}
cout << answer << '\n';
return 0;
}
投稿日時:
最終更新: