AtCoder が提供しているABC（AtCoder Beginner Contest）345 のC問題をC++とPythonで解いてみました。ABC345は、2024年3月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 One Time Swap（Difficulty : 469）
問題はリンク先をご覧ください。
文字ごとに頻度をカウントして、解を求めます。AtCoder Problems による Difficulty は 469 でした。
解答案
$1 \leqq i < j \leqq N$ を満たす $(i, j)$ に対して、文字列 $S$ の $i$ 文字目と $j$ 文字目を入れ替える操作を考えます。この操作によって異なる文字が生み出されたとすれば、$i$ 文字目と $j$ 文字目の文字種が異なっています。
前準備として ‘a’ から ‘z’ までの文字が現れる頻度をカウントしておきます。操作によって、’a’ と ‘b’ が入れ替わる場合の数は、’a’ の個数と ‘b’ の個数の積になります。また、ある文字の頻度が2以上であれば、元の文字列と同じものが操作によって生み出すことができます。
C++ プログラム例（ABC345C）
上の考察をプログラムとして実装します。
- 文字の頻度を配列 alpha に格納します。
- 文字の頻度が2以上の文字が存在するかブール変数 nochange に格納します。
- 結果を計算します（24、28行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
string s;
cin >> s;
ll len = s.length();
vector<ll> alpha(26);
for (int i = 0; i < len; ++i) {
++alpha[s[i] - 'a'];
}
ll result = 0;
bool nochange = false;
for (int i = 0; i < 26; ++i) {
if (alpha[i] >= 2) {
nochange = true;
}
for (int j = i + 1; j < 26; ++j) {
result += alpha[i] * alpha[j];
}
}
if (nochange) {
++result;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC345C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 345 C"""
s = input()
alpha = [0] * 26
for _, ch in enumerate(s):
alpha[ord(ch) - ord('a')] += 1
result = 0
nochange = False
for i in range(26):
if alpha[i] >= 2:
nochange = True
for j in range(i + 1, 26):
result += alpha[i] * alpha[j]
if nochange:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
今回のコンテストは、D問題以降の難易度が高く、C問題までしか解くことができませんでした。このような場合は、C問題までを速くことがレート向上に効くようです。
引き続き ABC の問題を紹介していきます。
