AtCoder が提供しているABC（AtCoder Beginner Contest）334 のE問題をC++とPythonで解いてみました。ABC334は、2023年12月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Christmas Color Grid 1（Difficulty : 1195）
問題はリンク先をご覧ください。
ABC334 E問題 Christmas Color Grid 1
緑色マスの連結成分に番号を付けて、赤色マスを調べます。AtCoder Problems による Difficulty は 1195 でした。
解答案
入力例3のグリッドは以下でした。
#...
.#.#
..##この緑色マス（#）の連結成分に以下のような番号を付けます。
1000
0203
0033ここまで準備ができれば、赤色マス（値が0のマス）の四方を調べて、連結成分の増減を調べます。
- 四方に連結成分が無ければ、連結成分はひとつ増えます。
- 四方に1種類だけ連結成分があれば、連結成分の個数は変わりません。
- 四方に2種類から4種類の連結成分があれば、連結成分の個数は1個から3個減ります。
結果的に、（1-四方の連結成分の個数）だけ連結成分が増えます。
C++ プログラム例（ABC334E）
プログラムの補足です。
- DFSを使って連結成分に番号を付けます（14ー29行目）。
- グリッドを走査して、’#’ を見つける毎に連結している関数 dfs を呼び出して、連結しているグリッドに番号を付けます（48行目）。
- 赤色マスの四方にいくつの連結成分があるかをsetコンテナを使って調べます。連結成分の増減を変数 result に格納していきます（61ー71行目）。
- 期待値を整数とするために mod 998244353 で出力する必要があります。ACL を使いました（2、5行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
typedef modint998244353 mint;
int h, w;
vector<string> s;
vector<vector<int>> num;
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
void dfs(int i, int j, int n) {
s[i][j] = '.';
num[i][j] = n;
for (int d = 0; d < 4; ++d) {
int next_i = i + di[d];
int next_j = j + dj[d];
if ((0 <= next_i)&&(next_i < h)
&&(0 <= next_j)&&(next_j < w)
&&(s[next_i][next_j] == '#')) {
dfs(next_i, next_j, n);
}
}
return;
}
int main()
{
cin >> h >> w;
s.resize(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
num.resize(h);
for (int i = 0; i < h; ++i) {
num[i].assign(w, -1);
}
mint num_g = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
++num_g;
dfs(i, j, num_g.val());
}
}
}
mint result = 0;
mint num_r = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (num[i][j] != -1) {
continue;
}
++num_r;
set<int> t;
for (int d = 0; d < 4; ++d) {
int next_i = i + di[d];
int next_j = j + dj[d];
if ((0 <= next_i)&&(next_i < h)
&&(0 <= next_j)&&(next_j < w)
&&(num[next_i][next_j] != -1)) {
t.insert(num[next_i][next_j]);
}
}
result += num_g + (mint)1 - (mint)t.size();
}
}
result = result / num_r;
cout << result.val() << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC334E）
Python の string 型は、書き換えができないためリストとして格納します（29ー33行目）。また、再帰関数の呼出回数の上限も増やしておきます（2、4行目）。基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 334 E"""
import sys
sys.setrecursionlimit(10**6)
MOD = 998244353
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
def dfs(i, j, n):
global h, w, s, num, di, dj
s[i][j] = '.'
num[i][j] = n
for d in range(4):
next_i = i + di[d]
next_j = j + dj[d]
if 0 <= next_i < h and \
0 <= next_j < w and \
s[next_i][next_j] == '#':
dfs(next_i, next_j, n)
return
h, w = map(int, input().split())
s = [["." for _ in range(w)] for _ in range(h)]
for i in range(h):
st = input()
for j in range(w):
s[i][j] = st[j]
num = [[-1 for _ in range(w)] for _ in range(h)]
num_g = 0
for i in range(h):
for j in range(w):
if s[i][j] == '#':
num_g += 1
dfs(i, j, num_g)
result = 0
num_r = 0
for i in range(h):
for j in range(w):
if num[i][j] != -1:
continue
num_r += 1
t = set()
for d in range(4):
next_i = i + di[d]
next_j = j + dj[d]
if 0 <= next_i < h and \
0 <= next_j < w and \
num[next_i][next_j] != -1:
t.add(num[next_i][next_j])
result += num_g + 1 - len(t)
result %= MOD
result *= pow(num_r, MOD - 2, MOD)
result %= MOD
print(result)こちらも「AC」と判定されました。
最後に
わたしにとっては難しい問題をコンテスト中に解くことができました。今年最後のABCを良い結果で締めくくることができました。
引き続き ABC の問題を紹介していきます。
