AtCoder が提供しているABC（AtCoder Beginner Contest）279 のC問題をC++とPythonで解いてみました。ABC279は、2022年11月26日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 RANDOM（Difficulty : 272）
問題はリンク先をご覧ください。
文字列の配列を操作する問題です。AtCoder Problems による Difficulty は、272 でした。
解答案
問題を読んでも、内容が分かりにくいと感じました。このような場合は、入力例1と出力例1と、その解説を読むと分かる場合が多いです。
この問題も、入力例1を読むと、「図形Sと図形Tを列の集合と見たときに、入れ替え可能か」という問題だと分かります。さらに、「列を構成する文字列の組が一致しているか」を調べるという問題と読み替えることができます。
問題を解く方針を書きだします。
- 図形SとTを読み込む。ただし、列の文字列として読み込む。
- 図形Sを構成する列文字列を図形Tを構成する文字列をそれぞれソートする。
- ソートした結果が一致していれば、”Yes” を出力する。一致していなければ ”No” を出力する。
C++ プログラム例（ABC279C）
図形Sと図形Tを構成する列の文字列を配列として用意します。
図形Ｓを1行づつ読みながら、各列の文字列に加えていきます。図形Tも同じように処理して、ソートして比較します。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(w);
vector<string> t(w);
for (int i = 0; i < h; ++i) {
string temp_s;
cin >> temp_s;
for (int j = 0; j < w; ++j) {
s[j] += temp_s.substr(j, 1);
}
}
for (int i = 0; i < h; ++i) {
string temp_t;
cin >> temp_t;
for (int j = 0; j < w; ++j) {
t[j] += temp_t.substr(j, 1);
}
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
bool result = true;
for (int i = 0; i < w; ++i) {
if (s[i] != t[i]) {
result = false;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}実際には、配列ではなく Vector コンテナで処理しました。このため、s と t が一致していることは、等価演算子で簡単に書けます。
配列の場合は、アドレスの比較になるため同じ書き方ができません。上のプログラムのように要素毎に比較する必要があります。
以下が、Vector コンテナを等価演算子で比較したプログラムとなります（29行目）。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(w);
vector<string> t(w);
for (int i = 0; i < h; ++i) {
string temp_s;
cin >> temp_s;
for (int j = 0; j < w; ++j) {
s[j] += temp_s.substr(j, 1);
}
}
for (int i = 0; i < h; ++i) {
string temp_t;
cin >> temp_t;
for (int j = 0; j < w; ++j) {
t[j] += temp_t.substr(j, 1);
}
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
if (s == t) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}どちらも、AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC279C）
TLE 判定の解答1
単純に C++版を移植したプログラムが以下です。4つある入力例に対して、期待された出力例が出力されたことを確認しました。
"""AtCoder Beginner Contest 279 C"""
h, w = map(int, input().split())
s = ["" for i in range(w)]
for i in range(h):
temp_s = input()
for j in range(w):
s[j] += temp_s[j]
t = ["" for i in range(w)]
for i in range(h):
temp_t = input()
for j in range(w):
t[j] += temp_t[j]
s.sort()
t.sort()
print("Yes" if s == t else "No")残念ながら、結果は TLE（Time Limit Exceeded）と判定されました。76テストケースのうち、4テストケースで時間切れと判定されました。「Python(3.8.2)」だけではなく、「PyPy3(7.3.0)」でも結果は、TLE と判定されました。
TLE 判定の解答2
最初の版から、以下を変更しました。
- 図形Sと図形Tを行として読み込む。
- ソートではなく、辞書（defaultdict）として値を格納して、辞書を比較する。
"""AtCoder Beginner Contest 279 C"""
from collections import defaultdict
h, w = map(int, input().split())
s_h = [input() for i in range(h)]
t_h = [input() for i in range(h)]
s_dict = defaultdict(int)
t_dict = defaultdict(int)
for j in range(w):
s = ""
t = ""
for i in range(h):
s += s_h[i][j]
t += t_h[i][j]
s_dict[s] += 1
t_dict[t] += 1
print("Yes" if s_dict == t_dict else "No")この例も、同じテストケースで TLE と判定されました。
AC 判定の解答
AtCoder の正解者の解答を拝見すると、ほぼ同じプログラムが AC（Accepted）判定を受けていました。参考にして以下を変更しました。
- 文字列の演算ではなく、リストの演算に置き換える。
"""AtCoder Beginner Contest 279 C"""
from collections import defaultdict
h, w = map(int, input().split())
s_h = [input() for i in range(h)]
t_h = [input() for i in range(h)]
s_dict = defaultdict(int)
t_dict = defaultdict(int)
for j in range(w):
s = []
t = []
for i in range(h):
s.append(s_h[i][j])
t.append(t_h[i][j])
s_dict["".join(s)] += 1
t_dict["".join(t)] += 1
print("Yes" if s_dict == t_dict else "No")このプログラムは「AC」と判定されました。
TLE 判定されたプログラムと AC 判定されたプログラムの差分コードの背景色を変更しています。文字列の処理とリストの処理の差しかありません。まだ Python を使いこなせていないと感じます。
最後に
Python 版では、実行時間について苦戦しました。最後の差は、文字列処理とリスト処理の差しかありませんでした。Python は、リスト処理の方が速く動作するよう設計されているのかもしれません。
実行時間の面では、C++ が楽です。ただし、Python のほうが（このプログラムに限らず）すっきりと表現できています。Python の表現力と C++ の性能の良さと、それぞれの言語の特徴を再認識しました。
引き続き ABC の問題を紹介していきます。
