AtCoder が提供しているABC（AtCoder Beginner Contest）287 のE問題をC++とPythonで解いてみました。ABC287は、2023年1月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Karuta（Difficulty : 1093）
問題はリンク先をご覧ください。
ソートして文字列の差を求めることに帰着しました。AtCoder Problems による Difficulty は 1093 でした。
解答案
問題の構造を理解するために、入力例2をプログラムを使わないで解いてみます。入力例2は以下となります。
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
aこの文字列をソートして、前後の文字列と何文字まで一致しているか調べます。ソートした文字列と前後の文字列と一致している文字数を以下に記しました。
a -> 1
abra -> 4
abracadabra -> 4
acadabra -> 1
adabra -> 1
bra -> 3
bracadabra -> 3
cadabra -> 0
dabra -> 0
ra -> 2
racadabra -> 2この値は、出力例2と一致しています。
ただし、単純にソートすると、もともと何行目の文字列であったかの情報が失われます。C++ の場合は pair、Python の場合はタプルにより何行目にあったかを保持します。文字列でソートするため、pair もしくはタプルの最初の要素を文字列にします。
C++ プログラム例（ABC287E）
二つの文字列の何文字目まで一致しているかを求める関数 diff を分けて実装しました。
方針に従い、文字列と行を組にして vector コンテナに格納して、sort します。入力例2で試したように前後の文字列の何文字目まで一致しているか求めて配列 result に格納します。
最後に result を出力します。以下が、C++ のプログラムです。
#include <bits/stdc++.h>
using namespace std;
int diff(string s1, string s2)
{
int limit = min(s1.length(), s2.length());
for (int i = 0; i < limit; ++i) {
if (s1[i] != s2[i]) {
return i;
}
}
return limit;
}
int main()
{
int n;
cin >> n;
vector<pair<string, int>> s(n);
for (int i = 0; i < n; ++i) {
string temp_s;
cin >> temp_s;
s[i] = make_pair(temp_s, i + 1);
}
sort(s.begin(), s.end());
vector<int> result(n + 1);
result[s[0].second] = diff(s[0].first, s[1].first);
for (int i = 1; i < n - 1; ++i) {
result[s[i].second] = max(diff(s[i - 1].first, s[i].first),
diff(s[i].first, s[i + 1].first));
}
result[s[n - 1].second] = diff(s[n - 2].first, s[n - 1].first);
for (int i = 1; i <= n; ++i) {
cout << result[i] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC287E）
Python 版では、C++ のプログラムを移植しました。
"""AtCoder Beginner Contest 287 E"""
def diff(s1, s2):
limit = min(len(s1), len(s2))
for i in range(limit):
if s1[i] != s2[i]:
return i
return limit
n = int(input())
s = []
for i in range(n):
s.append((input(), i + 1))
s.sort()
result = [0] * (n + 1)
result[s[0][1]] = diff(s[0][0], s[1][0])
for i in range(1, n - 1):
result[s[i][1]] = max(diff(s[i - 1][0], s[i][0]),
diff(s[i][0], s[i + 1][0]))
result[s[n - 1][1]] = diff(s[n - 2][0], s[n - 1][0])
for i in range(1, n + 1):
print(result[i])こちらも「AC」と判定されました。
最後に
コンテスト中は、vector<pair<string, int>> ではなく、map<string, int> を使って解いていました。C++ の map はソートする必要がないのですが、重複があると上書きされるため、動作しませんでした（逆に string に重複がない場合は、うまく動作しました）。重複している場合の処理をしている間に時間が切れました。
公式の動画解説で、pair を使っていることを聞いて、後は自力でプログラムしました。コンテスト中に粘ったことは、実力向上に役立つのではないかと願っています。
引き続き ABC の問題を紹介していきます。
