AtCoder が提供しているABC（AtCoder Beginner Contest）330 のD問題をC++とPythonで解いてみました。ABC330は、2023年11月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Counting Ls（Difficulty : 569）
問題はリンク先をご覧ください。
行と列にあるoの数を事前にカウントしておきます。AtCoder Problems による Difficulty は 569 でした。
解答案
L字の真ん中にある ‘o’ に注目します。同じ行にある ‘o’ の数を x とします。同じ列にある ‘o’ の数を y とします。この場合、L 字は、(x-1) × (y-1) 個できます。
L字の真ん中にある ‘o’ の場所の候補 $N^2$ に対して、行にある ‘o’ の数を求めるために $N$ 回、列にある ‘o’ の数を求めるために $N$ 回の計算が必要です。結果的に計算量は、$O(N^4) = 1.6 \times 10^{13}$ となり間に合いません。
このため、各行にある ‘o’ の個数と各列にある ‘o’ の個数を事前に求めておきます。この場合、計算量は、$O(N^2) = 4 \times 10^6$ となります。前準備に同じ計算量が必要ですが、十分に間に合います。
C++ プログラム例（ABC330D）
プログラムの補足です。
- 各行にある ‘o’ の個数 x[i] と各列にある ‘o’ の個数 y[j] を先に計算しておきます（14ー23行目）。
- マスが ‘o’ であれば、(x[i] – 1) × (y[j] – 1) を結果 result に加えていきます（25ー32行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<int> x(n, 0);
vector<int> y(n, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (s[i][j] == 'o') {
++x[i];
++y[j];
}
}
}
ll result = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (s[i][j] == 'o') {
result += (x[i] - 1) * (y[j] - 1);
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC330D）
Python版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest XXX Y"""
n = int(input())
s = [input() for i in range(n)]
x = [0] * n
y = [0] * n
for i in range(n):
for j in range(n):
if s[i][j] == 'o':
x[i] += 1
y[j] += 1
result = 0
for i in range(n):
for j in range(n):
if s[i][j] == 'o':
result += (x[i] - 1) * (y[j] - 1)
print(result)こちらも「AC」と判定されました。
最後に
前準備することに気が付けば、解きやすい問題でした。
引き続き ABC の問題を紹介していきます。
