AtCoder が提供しているABC（AtCoder Beginner Contest）315 のD問題をC++とPythonで解いてみました。ABC315は、2023年8月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Magical Cookies（Difficulty : 1531）
問題はリンク先をご覧ください。
問題に記載してある手順で処理します。各行と各列の文字数をカウントしておくと間に合います。AtCoder Problems による Difficulty は 1531 でした。
解答案
基本的には、問題文に書いてある手続きに従って処理をします。ただし、素直に行または列の文字がすべて同じか確認していると計算量的に間に合いません。
各行と各列に含まれる英小文字26文字の頻度をカウントしておきます。
最初の状態で、その行に同じ文字がW個含まれていれば、手続き1で印がつきます。同じように、その列に同じ文字がH個含まれていれば、手続き2で印が付きます。
印がついた行や列を抜いていき、繰り返して手続きを処理します。
C++ プログラム例（ABC315D）
手続きを以下のように実装しました。
- 前準備
- 各行の文字頻度を配列 h_char に、各列の文字頻度を配列 w_char に格納します（15ー18行目）。
- 手続き全体
- 変数 change を使って手続きで印がついたか管理します。
- 手続き1
- 英小文字26文字について、その行に含まれている文字が w_result（初期値 w）個含まれていれば、その文字を配列 h_del_char に記録して、印をつけます（35ー39行目）。
- もし一度でも印が付いていれば、その行は確認しません（32ー33行目）。
- 手続き2
- 英小文字26文字について、その列に含まれている文字が h_result（初期値 h）個含まれていれば、その文字を配列 w_del_char に記録して、印をつけます（47ー51行目）。
- もし一度でも印が付いていれば、その列は確認しません（44ー45行目）。
- 手続き3
- ある行に印がついていたら、h_result を減らして、それぞれの列からその文字を抜いておきます（57ー59行目）。
- ある行に印がついていたら、w_result を減らして、それぞれの行からその文字を抜いておきます（63ー65行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> c(h);
for (int i = 0; i < h; ++i) {
cin >> c[i];
}
vector<vector<int>> h_char(h, vector<int>(26, 0));
vector<vector<int>> w_char(w, vector<int>(26, 0));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
++h_char[i][c[i][j] - 'a'];
++w_char[j][c[i][j] - 'a'];
}
}
int h_result = h;
int w_result = w;
vector<bool> h_deleted(h, false);
vector<bool> w_deleted(w, false);
bool change = true;
while (change) {
change = false;
vector<int> h_del_char;
vector<int> w_del_char;
for (int i = 0; i < h; ++i) {
if (h_deleted[i]) {
continue;
}
for (int k = 0; k < 26; ++k) {
if ((h_char[i][k] == w_result)&&(w_result >= 2)) {
h_deleted[i] = true;
h_del_char.push_back(k);
change = true;
}
}
}
for (int j = 0; j < w; ++j) {
if (w_deleted[j]) {
continue;
}
for (int k = 0; k < 26; ++k) {
if ((w_char[j][k] == h_result)&&(h_result >= 2)) {
w_deleted[j] = true;
w_del_char.push_back(k);
change = true;
}
}
}
for (int k : h_del_char) {
--h_result;
for (int j = 0; j < w; ++j) {
--w_char[j][k];
}
}
for (int k : w_del_char) {
--w_result;
for (int i = 0; i < h; ++i) {
--h_char[i][k];
}
}
}
cout << h_result * w_result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC315D）
Python版は、C++のプログラムをほぼそのまま移植しました。以下のプログラムは、「Python (CPython 3.11.4)」でTLE判定でした。「Python (PyPy 3.10-v7.3.12)」でAC判定でした。
"""AtCoder Beginner Contest 315 D"""
h, w = map(int, input().split())
c = [input() for i in range(h)]
h_char = [[0 for j in range(26)] for i in range(h)]
w_char = [[0 for j in range(26)] for i in range(w)]
for i in range(h):
for j in range(w):
h_char[i][ord(c[i][j]) - ord('a')] += 1
w_char[j][ord(c[i][j]) - ord('a')] += 1
h_result = h
w_result = w
h_deleted = [False] * h
w_deleted = [False] * w
change = True
while change:
change = False
h_del_char = []
w_del_char = []
for i in range(h):
if h_deleted[i]:
continue
for k in range(26):
if h_char[i][k] == w_result and w_result >= 2:
h_deleted[i] = True
h_del_char.append(k)
change = True
for j in range(w):
if w_deleted[j]:
continue
for k in range(26):
if w_char[j][k] == h_result and h_result >= 2:
w_deleted[j] = True
w_del_char.append(k)
change = True
for k in h_del_char:
h_result -= 1
for j in range(w):
w_char[j][k] -= 1
for k in w_del_char:
w_result -= 1
for i in range(h):
h_char[i][k] -= 1
print(h_result * w_result)最後に
D問題としては実装量も多く難しい問題でした。行と列ごとに英字26文字の頻度をカウントしておくことがコツでした。
引き続き ABC の問題を紹介していきます。
