ABC325の解説記事 (PyPy3 ABC)

# はじめに
問題は[こちら](https://atcoder.jp/contests/abc325/tasks)
初心者（灰色〜茶色）向けです。
自力ACしたC問題まで実施します。
# A - Takahashi san
https://atcoder.jp/contests/abc325/tasks/abc325_a
## 考え方
そのままです。文字列S, Tを
S T
を受け取って、
S+半角スペース+'san'
を表示すれば終わりです。
[模範解答](https://atcoder.jp/contests/abc325/editorial/7446)　のように「,」区切りで入れるとprintの出力結果は半角スペース区切りで出力されます。

https://web-camp.io/magazine/archives/16596
## 解答例
```Python3:私の解答
s, t = input().split()
print(s+" san")
```
# B - World Meeting
https://atcoder.jp/contests/abc325/tasks/abc325_b
## 考え方
愚直に、0~23時でそれぞれ会議参加可能な人数の合計値を求め、その最大値を考えます。その方針を実現するために、各地域の人数を持つ辞書（pDict）、各地域の参加可能な時刻（標準時）のSetをもつ辞書（tDict）を使用しています。
1. 24の長さのリスト（peopleCntList）を用意します。ここに各時刻（0~23時）の参加可能な人数の合計値を格納します。
1. 各地域の人数を持つ辞書（pDict）、各地域の参加可能な時刻（**標準時**）のSetをもつ辞書（tDict）を用意します。どちらも地域iをキーにします。
tDictの値をListではなく、Setにしているのは、後々の参照の際のTLEリスクからで、Listでも差し支えないと思います。
1. 各地域の人数、標準時からのズレを読み込みます。 pDict には問題のW_iを格納します。
tDictに格納するのは下記からなる、Set です。
```math
（X_i+9）\%24, (X_i+10)\%24, (X_i+11)\%24, \dots , (X_i+17)\%24
```
格納内容について説明します。
現地の0時が標準時基準だとX_i時になる訳ですから、現地の9時は標準時基準だとX_i+9時です。
ここで重要なのは、1日は24時間ですから、24以上は24を引く必要があります。
例えば、X_i = 20 の時、 現地時間9時は 標準時基準で 20+9 = 29時ですが、これは 29-24 =　５時 ですね。
ただ、「24以上の時に、24を引く」　ではなく、「24で割ったあまり」とした方が管理が楽になります。（24で割ったあまり、とすれば、24を超えたかどうか　にかかわらず、一つの式でかけるからです。）
また、格納するのは会議開始時刻とします。（会議の所要時間は1時間ですから、18時は格納しません。）
解答例では、内包表記を使用しています。
4. 各時間iについて、各地域jが会議参加可能時刻であれば、peopleCntList[i]の値を pDict[j]だけ増加させます。
5. peopleCntList の最大値を表示して終了です。
## 解答例
```Python3:私の解答
n = int(input())
pDict = dict()
tDict = dict()
peopleCntList = [0]*24
for i in range(n) :
    pDict[i], x = map(int, input().split())
    tDict[i] = {(x+j)%24 for j in range(9, 18)}
for i in range(24) :
    for j in range(n) :
        if i in tDict[j] :
            peopleCntList[i] += pDict[j]
print(max(peopleCntList))
```
# C - Sensors
https://atcoder.jp/contests/abc325/tasks/abc325_c
## 考え方
Sensor をグループ分けします。グループ分けといえば、UnionFind木です。
下記の記事を参考にしましたので、ご参照ください。

https://kunassy.com/unionfind-atcoder-python/#google_vignette

また、UnionFind木の概要についてはAtCoder公式の記事もご参考ください。

https://atcoder.jp/contests/practice2/tasks/practice2_a

https://drken1215.hatenablog.com/entry/2022/12/14/212330

また、BFSやDFSでも解けますのでぜひ他の記事もご参考になさってください。

大枠の方針としては、
1. センサーの座標の Set (sensors) と sensorの座標とセンサーの番号を対応づける辞書(sensorsNumber)を用意する。
1. 各座標をチェックして、センサーであれば、その座標のtupleをsensorsに格納する。行の若い順、列の若い順にセンサーをナンバリングしてsensorsNumberで番号を管理する
1. 各センサーについて、周辺9マスにセンサーがあればそのセンサーを同じグループとしてunionする
1. グループの数を数えて終了

どうしてセンサーの座標の Set (sensors) と sensorの座標とセンサーの番号を対応づける辞書　なんていうのを用意しているのかというと、二次元 UnionFind木のようなものを作成するよりも、UnionFindをシンプルにしてしまった方が実装が楽だったからですw UnionFindはセンサーの数の大きさで作成しています。

計算量は センサーの数(h*w) * 周辺マスの数(自マス含め)9 * UnionFindのマージロジックの実行回数です。なんとか間に合います。
## 解答例
```Python3:私の解答
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

h, w = map(int, input().split())
sensors = set()
sensorsNumber = dict()
cnt = 0
for i in range(h) :
    s = input()
    for j in range(w) :
        if s[j] == '#' :
            sensors.add((i,j))
            sensorsNumber[(i,j)] = cnt
            cnt += 1
uf = UnionFind(len(sensors))
for (i,j) in sensors :
    for k in range(max(0, i-1), min(i+2, h)) :
        for l in range(max(0, j-1), min(j+2, w)) :
                if (k,l) in sensors :
                    uf.union(sensorsNumber[(i,j)], sensorsNumber[(k,l)])
print(uf.group_count())
```
# 参考文献
#### Latex
http://www.ic.daito.ac.jp/~mizutani/tex/special_characters.html

# 感想
今回D問題が解けず悔しかったです、、、　最適な印字順がわかリませんでした。
問題

https://atcoder.jp/contests/abc325/tasks/abc325_d

解説

https://atcoder.jp/contests/abc325/editorial/7448

年内入緑目指して頑張ります。