【ABC337】競プロのA-C問題を40代サラリーマンがPython解説！初心者にもわかりやすく

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 337

A問題：Scoreboard

A – Scoreboard

問題文

チーム高橋とチーム青木が N 回の試合を行いました。 i 回め (1≤i≤N) の試合ではチーム高橋が Xi​ 点、チーム青木が Yi​ 点を獲得しました。

N 回の試合で獲得した得点の合計がより多いチームの勝ちです。

どちらのチームが勝ったか出力してください。 ただし、獲得した得点の合計が等しい場合は引き分けとなります。

解答

# 入力される試合の回数Nを取得
n = int(input())

# チーム高橋とチーム青木の得点合計を初期化
T, A = 0, 0

# N回の試合についてループ
for _ in range(n):
    # それぞれの試合での両チームの得点を取得
    x, y = map(int, input().split())
    # チーム高橋とチーム青木の得点を加算
    T += x
    A += y

# 得点合計を比較して結果を出力
if T == A:
    print("Draw")  # 得点が同じ場合は引き分け
elif T > A:
    print("Takahashi")  # チーム高橋が勝利
else:
    print("Aoki")  # チーム青木が勝利

考え方）

チーム高橋とチーム青木にそれぞれfor文を使って点数を加算していき、トータル得点で二つのチームをif文を用いて比較しています。

  1. 試合の回数の入力: 最初に、試合の回数 n を標準入力から取得します。
  2. 得点合計の初期化: 次に、チーム高橋（T）とチーム青木（A）の得点合計を格納する変数を0で初期化します。
  3. 試合ごとの得点の加算: n 回の試合についてのループを回します。各試合での得点 x（チーム高橋）、y（チーム青木）を標準入力から取得し、それぞれのチームの合計得点に加算します。
  4. 勝利チームの決定: 最後に、T と A の値を比較して、勝利チームを決定します。合計得点が同じ場合は “Draw”、T が大きい場合は “Takahashi”、A が大きい場合は “Aoki” と出力します。

B問題：Extended ABC

B – Extended ABC

問題(要約)

与えられた文字列 S が以下の条件を満たす場合、拡張 ABC 文字列と呼ぶ。

  1. 文字列 S が拡張 A 文字列であれば、そのすべての文字は ‘A’ です。
  2. 文字列 S が拡張 B 文字列であれば、そのすべての文字は ‘B’ です。
  3. 文字列 S が拡張 C 文字列であれば、そのすべての文字は ‘C’ です。
  4. 文字列 S が拡張 ABC 文字列であれば、拡張 A 文字列、拡張 B 文字列、拡張 C 文字列をこの順に連結したものです。

空文字列は拡張 A、B、C 文字列の全てに該当します。与えられた文字列 S が拡張 ABC 文字列かどうかを判断し、「Yes」または「No」を出力します。

解答

import re  # 正規表現モジュールのインポート

S = input()  # 入力文字列の取得

# 正規表現を使用して、拡張 ABC 文字列のパターンに一致するか確認
if re.match(r'^A*B*C*$', S):
    print("Yes")  # 拡張 ABC 文字列の場合は "Yes" 出力
else:
    print("No")  # それ以外の場合は "No" 出力

解き方）

正規表現を用いていくことにより、間違いが少なく解けます。

  1. 正規表現モジュールのインポート: まず、Pythonの re モジュール（正規表現を扱うためのモジュール）をインポートします。
  2. 入力文字列の取得: 次に、input() 関数を使用してユーザーから文字列 S を入力として取得します。
  3. 拡張 ABC 文字列パターンのチェック:
    • 正規表現 r'^A*B*C*$' を使用して、文字列 S が拡張 ABC 文字列の条件に一致するかをチェックします。
    • この正規表現の意味は次のとおりです:
      • ^ は文字列の開始を意味します。
      • A* は0個以上の ‘A’ が連続することを意味します。
      • B* は0個以上の ‘B’ が連続することを意味します。
      • C* は0個以上の ‘C’ が連続することを意味します。
      • $ は文字列の終了を意味します。
  4. 結果の出力:
    • re.match 関数がパターンに一致する場合、print("Yes") を実行して文字列が拡張 ABC 文字列であることを示します。
    • パターンに一致しない場合は、print("No") を実行して拡張 ABC 文字列ではないことを示します。

別解）

コンテスト中は下記の解き方で解きましたが、if文の抜けがあり不正解が続いてしまったので、正規化の方が間違いが少なく解けると思います。

from itertools import groupby  # itertoolsモジュールからgroupby関数をインポート

S = input()  # 入力文字列の取得

words = []  # 連続する文字を格納するリストを初期化

# 文字列Sの各文字について、連続する文字をグループ化
for char, _ in groupby(S):
    words.append(char)  # 各グループの文字をwordsリストに追加

# 拡張 ABC 文字列の条件をチェック
if words == ['A'] or words == ['B'] or words == ['C']:
    print('Yes')  # 文字列が 'A' または 'B' または 'C' のみで構成されている場合
elif words == ['A', 'B'] or words == ['A', 'C'] or words == ['B', 'C']:
    print('Yes')  # 文字列が 'AB', 'AC', 'BC' のどれかの形式である場合
elif words == ['A', 'B', 'C']:
    print('Yes')  # 文字列が 'ABC' の形式である場合
else:
    print('No')  # 上記のいずれにも当てはまらない場合

C問題：Lining Up 2

C – Lining Up 2

問題

人 1, 人 2,…, 人 N の N 人が一列に並んでいます。

並び方の情報が長さ N の数列 A=(A1​,A2​,…,AN​) として与えられます。

Ai​ (1 ≤ i ≤ N) は次のような情報を表しています。

  • Ai​=−1 のとき、人 i は先頭に並んでいる。
  • Ai​≠−1 のとき、人 i は人 Ai​ のすぐ後ろに並んでいる。

列に並んでいる人の番号を先頭から順番に出力してください。

解答

n = int(input())  # 人数Nを入力
A = list(map(int, input().split()))  # 並び方の情報を持つ数列Aを入力

# 数列Aから、-1以外の値を持つ要素のインデックス（人の番号）と値（前の人の番号）の辞書を作成
dicA = {v: k for k, v in enumerate(A, start=1) if v != -1}

# 先頭にいる人の番号を探し、出力する人のリストに最初に追加
order = A.index(-1) + 1
ANS = [order]

# 残りの人々の順番を辞書を使って決定し、リストに追加
for i in range(1, n):
    order = dicA[order]
    ANS.append(order)

print(*ANS)  # 人々の番号を順番に出力


解き方）

リストのインデックスと値の扱いを問う問題です。for文を用いてindex()で位置を毎回特定すると、制限時間を超えてしまうため、辞書に登録し、直接検索を行っています。

下記がコードの詳細です。

  1. 入力の取得: まず、人数 n と数列 A を入力として取得します。
  2. 辞書の作成: 数列 A から -1 以外の要素を抽出し、その値（前の人の番号）とインデックス（人の番号）のペアを辞書 dicA に格納します。
  3. 先頭の人の特定: 数列 A で -1 の位置を見つけ、そのインデックス（人の番号）を order に格納し、出力リスト ANS に最初に追加します。
  4. 残りの人の順番を決定: for ループを使い、辞書 dicA を参照しながら、次に並ぶ人の番号を順に ANS に追加します。
  5. 結果の出力: 最終的に、ANS リストに格納された順番に人々の番号を出力します。

感想

今回は、C問題まで解くことができましたが、B問題で落とし穴にハマってしまいました。

A問題は、基本的なfor文の問題で、すぐに解くことができました。

B問題は、文字並びを確かめる問題でした。groupbyを用いることにより、連続している所を気にする必要がなくなるため、この方法で進めました。解放的には悪くはなかったのですが、その後の条件分岐を適切に設定できずに、不正解の嵐（７連発）。なんとか正解まで辿り着けたことは良かったです。開放においては、正規化を用いると非常に楽に解けることが分かりましたので、正規表現について理解を深めていきたいと思います。

C問題は、インデックスを扱う問題でした。当初は、for文で毎回全てのインデックスを探すアプローチを試みましたが、時間制限を超えてしまいました。その後、辞書を使って情報を管理することで、正解に辿り着くことができました。

B問題で時間を取られたことにより、先週に引き続き順位は下がり、530になってしまいました。C問題を先に解くなどして、順位をキープする戦略も次回は考えたいと思います。

それでは、皆さんも競プロライフを楽しんでくださいね！(*＾▽＾)／

コメント

タイトルとURLをコピーしました