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

abc323 AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 323

A問題：Weak Beats

A – Weak Beats

問題(要約)

与えられた16文字の文字列Sについて、位置が2以上かつ16以下の偶数の文字が0であれば”Yes”を、そうでなければ”No”を出力する。

解答

# 入力として文字列Sを受け取る
S = input()

# 文字列Sの各文字とその位置に対して処理を行う
for i, s in enumerate(S, start=1):
    # 位置が2以上かつ偶数で、かつその文字が'0'でない場合
    if i >= 2 and i % 2 == 0 and s != '0':
        # 'No'を出力してプログラムを終了
        exit(print('No'))

# 条件を満たす文字がない場合、'Yes'を出力
print('Yes')
  1. 入力の受け取り: 最初に、ユーザーからの入力として文字列Sを受け取ります。
  2. 文字列Sを順にチェック: enumerate()関数を使って、文字列Sの各文字とその位置（1から始まるインデックス）を取得します。このループを使って、文字列Sの各位置の文字に対して以下の条件をチェックします。
  3. 特定の条件のチェック:
    • i >= 2: 位置が2以上であることを確認します。
    • i % 2 == 0: 位置が偶数であることを確認します。
    • s != '0': 文字が’0’でないことを確認します。
    これらの条件がすべて満たされない場合、'No'を出力してプログラムを終了します。
  4. 条件を満たす場合の処理: ループが終了した時点で、条件を満たす文字が見つからなかった場合は、'Yes'を出力します。

B問題：Round-Robin Tournament

B – Round-Robin Tournament

問題(要約)

1からNまでの番号がついたN人のプレイヤーが総当たり戦を行い、各試合の結果が与えられています。各プレイヤーの試合結果はN個の文字列S1, S2, …, SNによって表されます。文字’o’はプレイヤーが試合に勝利したことを、文字’x’はプレイヤーが試合に敗北したことを示します。また、自分自身との試合の結果は’-‘となります。

プレイヤーの順位は、勝利した試合数が多い順に決まり、勝利した試合数が同じ場合は、プレイヤーの番号が小さいほうが優先されます。問題では、各プレイヤーの番号を勝利数が高い順に並べ替え、その結果を出力することが求められています。

解答

辞書と辞書をキーで並び替えることにより、順位を算出する

# プレイヤーの数nを入力として受け取る
n = int(input())

# NxNの試合結果行列Sを入力として受け取る
S = [list(input()) for _ in range(n)]

# プレイヤーごとの勝利数を記録する辞書winNumsを初期化
winNums = {}

# 各プレイヤーの勝利数を計算し、winNumsに格納する
for i in range(n):
    cnt = 0
    for j in range(n):
        if S[i][j] == 'o':
            cnt += 1
    winNums[i + 1] = cnt

# 勝利数に基づいてプレイヤーを降順でソートする
sortedWinNums = sorted(winNums.items(), key=lambda x: x[1], reverse=True)

# ソートされた結果を出力する
for i, v in sortedWinNums:
    print(i, end=' ')
print()

以下詳細

  1. プレイヤー数と試合結果の入力： 最初に、プレイヤーの数nを入力として受け取ります。次に、NxNの試合結果行列Sを入力として受け取ります。この行列は、プレイヤーiがプレイヤーjに勝った場合は”o”、負けた場合は”x”、自分自身との試合は”-“で構成されています。
  2. 各プレイヤーの勝利数を計算： ネストしたループを使用して、各プレイヤーが何回勝利したかを数えます。外側のループはプレイヤーiを、内側のループはプレイヤーjを表します。プレイヤーiがプレイヤーjに”o”（勝利）がある場合、cnt変数を増やします。
    ここで、winNumsは各プレイヤーの番号をキーとし、勝利数を値として持つ辞書です。
  3. 勝利数に基づいてプレイヤーを降順でソート： sorted()関数を使って、winNums辞書を勝利数を基準に降順でソートします。sorted()関数のkeyパラメータにはlambda関数を使用し、辞書の値（勝利数）を基準にソートします。
  4. 結果の出力： ソートされた結果をループで順に取り出し、プレイヤーの番号をスペースで区切って出力します。

C問題：World Tour Finals

C – World Tour Finals

問題(要約)

N人のプレイヤーが参加するプログラミングコンテストが行われ、競技時間の半分が終了しました。コンテストではM問の問題があり、各問題の得点は500以上2500以下の100の倍数です。

各プレイヤーi（1からNまで）について、既に解いた問題がo、未解決の問題がxで表される文字列Siが与えられます。プレイヤーiの総合得点は、解いた問題の点数の合計にi点のボーナス点を加えたものです。

各プレイヤーiがまだ解いていない問題を少なくとも何問解くことで、そのプレイヤーiの総合得点が他のプレイヤー全員の現在の総合得点を上回ることができるかを出力することが求められています。

解答

問題番号とプレイヤー番号をふまえた辞書で扱うことにより、すでに解いた問題か解いていないかを判断しながら計算していく。

# プレイヤー数nと問題数mを入力として受け取る
n, m = map(int, input().split())

# 各問題の点数を辞書Aに格納する（キー: 問題番号、値: 点数）
A = {}
for key, value in enumerate(list(map(int, input().split()))):
    A[key] = value

# 問題の点数で降順にソートする
sortedA = sorted(A.items(), key=lambda x: x[1], reverse=True)

# プレイヤーごとの解答状況を表す文字列Sを入力として受け取る
S = [list(input()) for _ in range(n)]

# プレイヤーごとの総合得点を計算し、pointsに格納する（キー: プレイヤー番号、値: 総合得点）
points = {}
for i in range(n):
    point = i + 1
    for j in range(m):
        if S[i][j] == 'o':
            point += A[j]
    points[i] = point

# 総合得点で降順にソートする
sortedPoints = sorted(points.items(), key=lambda x: x[1], reverse=True)

# 各プレイヤーが解かなければならない問題数を格納するリストansを初期化
ans = [0] * n

# 各プレイヤーについて、他のプレイヤーの現在の総合得点を上回るために解かなければならない問題数を計算
for i in range(n):
    if i == 0:
        # 1位のプレイヤーの場合、必要な問題数は0で初期化
        ans[sortedPoints[0][0]] = 0
        highestPoint = sortedPoints[0][1]  # 1位のプレイヤーの総合得点を保存
        continue
    else:
        # 2位以降のプレイヤーの場合、他のプレイヤーの現在の総合得点を上回るために解かなければならない問題数を計算
        point = sortedPoints[i][1]  # 現在のプレイヤーの総合得点
        cnt = 0  # 解かなければならない問題数のカウンター
        for j in range(m):
            # まだ解かれていない問題ならば、点数を加算し、カウンターを増やす
            if S[sortedPoints[i][0]][sortedA[j][0]] != 'o':
                point += sortedA[j][1]
                cnt += 1
                # 現在の総合得点が1位のプレイヤーを上回る場合、ループを終了
                if point > highestPoint:
                    break
        ans[sortedPoints[i][0]] = cnt  # 解かなければならない問題数をリストansに格納

# 各プレイヤーの解かなければならない問題数を出力
for a in ans:
    print(a)

以下詳細

  1. 問題点数の取得とソート： 最初に、問題の点数を保持する辞書Aに問題番号をキーとして、その問題の点数を値として格納します。これを点数の降順でソートしたsortedAリストを得ます。
  2. プレイヤーの解答状況の取得： プレイヤーごとの解答状況を示す文字列を受け取り、それを2次元リストSに格納します。このとき、S[i][j]が’o’の場合、プレイヤーiが問題jを解いていることを示し、’x’の場合は未解決であることを示します。
  3. プレイヤーの総合得点の計算： 各プレイヤーについて、解いた問題の点数を合計し、ボーナス点（プレイヤーの番号）を加えて総合得点を計算します。得点をpoints辞書に保存します。
  4. プレイヤーの解かなければならない問題数の計算： points辞書を総合得点の降順でソートしたsortedPointsリストを作成します。プレイヤーごとに、他のプレイヤーの現在の総合得点を上回るために解かなければならない問題数を計算します。このとき、点数が高い問題から順に、まだ解かれていない問題を解いていき、総合得点が他のプレイヤーを上回るかどうかをチェックします。
  5. 解かなければならない問題数の出力： 各プレイヤーの解かなければならない問題数をリストansに格納し、それを出力します。

感想

今週もC問題まで解けました！難易度は先週に引き続き低め(250点問題)だと思いますが、二週連続C問題まで解けたことが嬉しいです。

B問題、C問題ともに辞書型を用いて解くことができました。具体的には、辞書型を使って問題の特定の部分を効率的に管理したり、valueを基準に辞書をソートする方法を活用しました。これによって、問題の要点を的確に把握でき、解法のスピードが向上しました。

特に、C問題では二次元配列リストの各要素に辞書型の要素を割り当てる方法を用い、問題を解決しました。最初は複雑に感じましたが、着実な学習と練習の成果として、自信を持ってこのアプローチを活用できたことが大きな進歩だと感じています。

Ratingは茶コーダーの500付近で停滞しておりますが、新しいアプローチ(辞書型のソート等)やテクニックの習得によって、着実に成長を感じています。今後も着実な学びとチャレンジを続け、次なるステップに進むための基盤を築いていきたいと思います。

引き続き、楽しみながら続けていきたいと思います。

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

コメント

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