AtCoder

ABC282 B問題(Let’s Get a Perfect Score)を解く

AtCoder_ABC282_B

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

2つの文字列を選び、条件を満たすか判定する問題です。AtCoder Problems による Difficulty は、72 でした。ABC B問題として、標準的な問題です。

解答案

問題を解く方針を書きだします。

  • 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進数を使って計算量を減らした例を紹介しました。このような工夫が将来、別のところで役立つかもしれません。

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

COMMENT

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

CAPTCHA