AtCoder が提供しているABC（AtCoder Beginner Contest）282 のB問題をC++とPythonで解いてみました。ABC282は、2022年12月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Let’s Get a Perfect Score（Difficulty : 72）
問題はリンク先をご覧ください。
ABC282 B問題 Let’s Get a Perfect Score
２つの文字列を選び、条件を満たすか判定する問題です。AtCoder Problems による Difficulty は、72 でした。
解答案
問題を解く方針を書きだします。
- N、M と N 個の文字列 Si を読み込む。
- Si から二つ選び、同じ場所に対して、どちらかの文字列に ‘o’ が含まれていれば、条件を満たす。
- 条件を満たす、二つの組み合わせの個数を出力する。
C++ プログラム例（ABC282B）
方針に従い、素朴にプログラムしました。
文字列の数 N は30以下であるため、2つの文字列の組み合わせは最大 $(30 \times 29)/ 2$ 通りになります。文字列の長さ分 M は30以下のため、ループ回数は、最大で、$(30 \times 29)/ 2 \times 30$ となります。
短い時間で計算できる量です。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
int result = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
bool temp_f = true;
for (int k = 0; k < m; ++k) {
if ((s[i][k] == 'x')&&(s[j][k] == 'x')) {
temp_f = false;
}
}
if (temp_f) {
++result;
}
}
}
cout << result << endl;
return 0;
}上記は、計算量 $O(N^2M)$ です。工夫すると、計算量 $O(NM)$ または、$O(N^2)$ で計算することができます。
今回は、文字列の長さが30以下なので2進数に変換可能です。
入力例1は、以下の文字列でした。
ooooo
oooxx
xxooo
oxoxo
xxxxxこれを以下の手順で2進数に変換します。
- o を 1 に、x を 0 に変換する。
- 変換した数字を逆に読む。
入力例1は、上から、31、7、28、21、0 となります。
次に「どちらかの文字列に ‘o’ が含まれていれば、条件を満たす」は、文字列を変換した、2進数の OR を計算して、すべて1が立っていれば条件を満たします。
文字列を2進数に変換する計算量が $O(NM)$ となります。OR を取って比較する計算量が $O(N^2)$ となります。このため、計算量は、$O(NM + N^2)$となります。前述の素朴なプログラムの計算量は、$O(N^2M)$ となります。計算量としては改善できています。（2023/1/5 計算量に関する記述に誤りがあり修正しました。）
この考えに従いプログラムしました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<unsigned int> p(n, 0);
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
for (int j = 0; j < m; ++j) {
if (s[j] == 'o') {
p[i] += (1 << j);
}
}
}
int result = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if ((p[i] | p[j]) == (1 << m) - 1) {
++result;
}
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC282B）
Python も2例紹介します。最初は素朴な2つの文字列を組み合わせて計算しています。
"""AtCoder Beginner Contest 282 B"""
n, m = map(int, input().split())
s = [input() for i in range(n)]
result = 0
for i in range(n):
for j in range(i + 1, n):
temp_f = True
for k in range(m):
if s[i][k] == 'x' and s[j][k] == 'x':
temp_f = False
if temp_f:
result += 1
print(result)次に2進数を使いプログラムを移植しました。
"""AtCoder Beginner Contest 282 B"""
n, m = map(int, input().split())
p = [0] * n
for i in range(n):
s = input()
for j in range(m):
if s[j] == 'o':
p[i] += 1 << j
result = 0
for i in range(n):
for j in range(i + 1, n):
if p[i] | p[j] == (1 << m) - 1:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
素朴な計算と、2進数を使って計算量を減らした例を紹介しました。このような工夫が将来、別のところで役立つかもしれません。
引き続き ABC の問題を紹介していきます。
