初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC325_A-C問題】

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC325のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回使用している機能・アルゴリズム

DFS (深さ優先探索)　　　　　　　　　　　　　　　・・・　問題C

今回の参加コンテスト(ABC325)
感想

今回の参加コンテスト(ABC325)

AtCoder Beginner Contest 325

A問題：Takahashi san

A – Takahashi san

問題(要約)

与えられた苗字（文字列S）と名前（文字列T）を組み合わせ、間にスペースと敬称”san”を加えて、指定された順序で連結した文字列を出力する

解答

print(input().split()[0],'san')

下記の内容を1行で記載しています。（短くまとめれると熟練者風に見えますね）

input() 関数を使用してユーザーからの入力を受け取ります。
split() メソッドを使って、入力文字列をスペースで分割し、それぞれの要素をリストに格納します。
リストの最初の要素（苗字）を input().split()[0] で取得します。
取得した苗字の後ろに文字列”san”を追加して、print() 関数で出力します。

B問題：World Meeting

B – World Meeting

問題(要約)

世界中にN個の拠点があり、各拠点には社員数W_iとその拠点の現地時間X_iが与えられます。1時間の会議を開くために、各社員は自分の拠点の現地時間9:00から18:00の間に会議が行われる必要があります。できるだけ多くの社員が参加できるように、最大で何人の社員が参加できるか求める

解答

n = int(input())  # 拠点の数をユーザーから入力として受け取る

# 拠点ごとの社員数と現地時間を格納するリストを初期化
W = [None] * n
X = [None] * n

# 拠点ごとに社員数と現地時間を入力として受け取り、リストに格納
for i in range(n):
    w, x = map(int, input().split())
    W[i] = w
    X[i] = x

ans = 0  # 最大の参加社員数を格納する変数を初期化

# 24時間の範囲で会議の開催時間帯を試すループ
for t in range(24):
    cnt = 0  # 会議に参加できる社員数をカウントする変数を初期化
    
    # 各拠点について、会議の開催時間帯に社員が参加できるかチェック
    for i in range(n):
        mtg_time = X[i] + t  # 会議の開催時間を計算
        
        # 会議の開催時間が9:00から18:00の間にある場合、社員数をカウント
        if mtg_time > 24:
            mtg_time -= 24  # 24時を超えた場合は翌日に持ち越す
        if 9 <= mtg_time < 18:
            cnt += W[i]  # 会議に参加できる社員数をカウント

    ans = max(ans, cnt)  # それまでの最大の参加社員数と現在の参加社員数を比較し、大きい方をansに格納

print(ans)  # 最大の参加社員数を出力

以下詳細

各拠点の社員数と現地時間をリストに保存する： ユーザーから拠点の数（n）を受け取り、各拠点の社員数（W）と現地時間（X）をリストに格納します。
24時間の範囲で会議の開催時間を試す： 24時間すべての範囲について、会議の開催時間を変化させながら以下の手順を繰り返します：
各拠点に対して会議の開催時間帯に社員が参加できるかチェックする：
- 各拠点について、会議の開催時間（9:00から18:00の間）に社員が参加できるかどうかをチェックします。
- 会議の開催時間は拠点の現地時間に会議の開始時刻を足したものです。
- ただし、会議の開催時間が24時を超える場合は翌日に持ち越します。
各拠点で参加できる社員数をカウントする： 各拠点において、会議に参加できる社員の数（9:00から18:00の間に働いている社員数）をカウントします。
最大の参加社員数を更新する： 各時間帯での参加社員数を計算し、それまでの最大の参加社員数と比較して、より大きい場合はそれを最大の参加社員数として更新します。
最大の参加社員数を出力する： 上記の手順を24時間の範囲で繰り返した後、最大の参加社員数を出力します。

C問題：Sensors

C – Sensors

問題(要約)

H行W列のマス目があり、一部のマス目にセンサが配置されています。センサは上下左右斜めに隣接したマス目と連動し、一つのセンサとして動作します。センサが配置されているマス目は、文字列S₁,S₂,…,S_Hによって与えられ、各文字列のj文字目が#の場合、対応するマス目にセンサが配置されています。隣接したセンサ同士が連動して動作するとき、各センサが連動したセンサの総数を求める

解答

隣接するセンサの情報をグラフとして構築することにより、通常のDFSで解くことができます。

＊言語設定で、Python (PyPy 3.10-v7.3.12) を選ぶとTLE となってしまいましたが、Python (CPython 3.11.4) を用いることによりACが取得できました。

回答の解き方）

入力の受け取り： まず、マス目の行数（H）と列数（W）を取得し、各マス目のセンサの配置情報を二次元リスト S に格納します。
隣接するセンサの情報をグラフとして構築： 上下左右斜めに隣接するセンサ同士が連動するので、センサの位置情報をもとにグラフを構築します。具体的には、各マス目にセンサがあるかどうかをチェックし、隣接するマス目にセンサがあれば、それらのマス目をグラフ上で連結します。この時、各マス目をグラフ上でノードとし、隣接するマス目間に辺を持たせます。
深さ優先探索（DFS）によるセンサグループの探索： グラフが構築されたら、深さ優先探索（DFS）を用いて各センサグループを探索します。未訪問のノード（センサがあるマス目）を起点にDFSを実行し、そのセンサグループ内の全てのセンサを訪れます。DFSによってセンサグループを探索し終えたら、新しいセンサグループを探すために次の未訪問ノードを起点にDFSを再帰的に実行します。
センサグループの数を数える： DFSを使ってセンサグループを探索するたびに、グループ数をカウントします。全てのマス目を探索し終えたら、グループの総数が問題の答えとなります。

詳細はコード内にコメントで追記しています。

import sys
sys.setrecursionlimit(10 ** 8)  # 再帰の深さ制限を設定する

h, w = map(int, input().split())  # 行数hと列数wを取得

# 各マスのセンサの配置情報を2次元リストSに格納
S = [list(input()) for _ in range(h)]

# グラフの隣接リストを初期化
graph = [list() for _ in range(h * w)]

# 上下方向のセンサの連動をチェックして隣接リストを構築
for i in range(h - 1):
    for j in range(w):
        if S[i][j] == '#' and S[i + 1][j] == '#':
            pos = w * i + j
            graph[pos].append(pos + w)
            graph[pos + w].append(pos)

# 左右方向のセンサの連動をチェックして隣接リストを構築
for i in range(h):
    for j in range(w - 1):
        if S[i][j] == '#' and S[i][j + 1] == '#':
            pos = w * i + j
            graph[pos].append(pos + 1)
            graph[pos + 1].append(pos)

# 右下方向のセンサの連動をチェックして隣接リストを構築
for i in range(h - 1):
    for j in range(w - 1):
        if S[i][j] == '#' and S[i + 1][j + 1] == '#':
            pos = w * i + j
            graph[pos].append(pos + w + 1)
            graph[pos + w + 1].append(pos)

# 左下方向のセンサの連動をチェックして隣接リストを構築
for i in range(h - 1):
    for j in range(1, w):
        if S[i][j] == '#' and S[i + 1][j - 1] == '#':
            pos = w * i + j
            graph[pos].append(pos + w - 1)
            graph[pos + w - 1].append(pos)

# ノードの訪問状態を管理するリストを初期化
visited = [False] * (h * w)

# 深さ優先探索を行う関数を定義
def dfs(node):
    if not visited[node]:
        visited[node] = True
        
        # 隣接するノードに対して再帰的に深さ優先探索を実行
        for neighbor in graph[node]:
            dfs(neighbor)

ans = 0  # センサの連動グループの数をカウントする変数を初期化

# 全マス目をチェックしてセンサの連動グループを数える
for i in range(h):
    for j in range(w):
        node = w * i + j
        if S[i][j] == '#' and not visited[node]:
            dfs(node)  # 未訪問のセンサを起点に深さ優先探索を実行し、連動するセンサを探索
            ans += 1  # 一つのセンサの連動グループを探索し終えたので、グループ数を増やす

print(ans)  # センサの連動グループの総数を出力

参考：2次元配列→1次元配列への変換(graphの作り方)

pos は、マス目の座標 (i, j) を一次元の配列内のインデックスに変換するための式です。この変換によって、二次元のマス目上の位置を一次元のリスト内の位置に対応づけることができます。具体的には、マス目が H 行 W 列である場合、マス目の位置 (i, j) の一次元のリスト内の位置は pos = i * W + j として計算できます。

この pos の計算は、以下のように説明できます：

i: 行番号。i は0からH-1までの範囲で変化します。
j: 列番号。j は0からW-1までの範囲で変化します。
W: マス目の列数。

したがって、i * W + j の計算によって、マス目 (i, j) は、一次元のリスト内の位置 pos に対応づけられます。この pos を用いて、グラフ上でのノード（センサがあるマス目）を一意に識別し、それらを隣接リスト graph で管理します。このような変換を行うことで、二次元の概念を一次元のリスト内で扱えるようになり、プログラムが効率的に実装できるようになります。

感想

今週もC問題まで解けました！順位も久しぶりに3000番台を取れて大満足です !(^o^)!

B問題は最初戸惑いましたが、時差と24時間を考慮しながら、全ての時間帯を確認することで解ける方法が見つかりました。実装ができ答え合わせをしたところ、回答が合わない・・・。最初、max_cntを持ってくるところにcntを持ってきていたミスがありましたが、修正して再度チャレンジし、無事に正解にたどり着きました。

C問題は、深さ優先探索とすぐに思いつき、実装を開始しました。ただし、まだスラスラとはDFSのコードが出てこず、前回の自分のブログ記事を参考にしました。今回の問題の特性を考慮するために修正が必要でしたが、過去の自分のコードがベースになっているので修正もでき、無事に正解になりました。

ブログでまとめていることにより記憶が定着し、更にブログの検索欄で検索することによりすぐに目的の記事に辿り着くことができました。記憶する際に人に教えるつもりで勉強すると良いというのを改めて実感しました。

Ratingも540点と少しづつ上昇してきていますので、この勢いでレベルアップを図っていきたいと思います。

それでは、良い競プロライフを～！(*＾▽＾)／