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

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 351

A問題：The bottom of the ninth

A – The bottom of the ninth

問題文(要約)

チーム高橋とチーム青木が野球をしています。チーム高橋が9回表までに得点をし、チーム青木が8回裏までに得点しています。9回裏が始まろうとしており、チーム青木はチーム高橋の得点を超えるために9回裏で少なくとも何点必要かを求める問題です。

解答

sumA = sum(list(map(int,input().split())))  # チーム高橋の得点を合計
sumB = sum(list(map(int,input().split())))  # チーム青木の得点を合計

print(sumA - sumB + 1)  # チーム青木が勝つために必要な得点を出力

考え方）

下記の考え方を用いて解いています。

  • チーム高橋は９回表時点でチーム青木より同点以上の点数を取っています
  • チーム青木が勝つためには、チーム高橋の合計点より１点多く取る必要があります

上記の考えのもと９回表までの合計点を出し、チーム青木が１点多くなるために必要な点数を求めます。

コード詳細

  1. 入力と得点計算： ユーザーが入力するチーム高橋とチーム青木の得点をそれぞれ sumA と sumB に合計として保存します。
  2. 得点差の計算： チーム高橋とチーム青木の得点差を sumA - sumB で計算します。
  3. 勝利に必要な得点： チーム青木が勝つためには、この得点差に1点を加えた数の点を9回裏で取る必要があります。これは、単に得点差を覆すだけでなく、勝つためには1点多く取る必要があるためです。この計算結果を出力します。

B問題：Spot the Difference

B – Spot the Difference

問題

縦 N マス、横 N マスのグリッドが 2 個与えられます。それぞれグリッド A, グリッド B と呼びます。
グリッドの各マスには英小文字が書かれています。
グリッド A の上から i 行目、左から j 列目に書かれている文字は Ai, j​ です。
グリッド B の上から i 行目、左から j 列目に書かれている文字は Bi, j​ です。 

2 つのグリッドは 1 ヵ所だけ書かれている文字が異なります。すなわち、Ai, j​ ≠ Bi, j​ である N 以下の正整数の組 (i, j) はちょうど 1 個存在します。この (i, j) を求めてください。

解答

n = int(input())  # グリッドのサイズNを入力

A=[input() for _ in range(n)]  # グリッドAのデータを行単位で入力
B=[input() for _ in range(n)]  # グリッドBのデータを行単位で入力

for i in range(n):
    for j in range(n):
        if A[i][j] != B[i][j]:  # グリッドAとBを比較し異なる文字の位置を見つけた場合
            exit(print(i+1,j+1))  # その位置を1-based indexで出力しプログラムを終了

考え方）

一箇所を除いて文字列は同じですので、for文をネストして異なる箇所を探します。リストは0から始まるため、結果を報告する際には i と j にそれぞれ 1 を加えています。

コード詳細

  1. 入力： サイズ n を入力し、その後でグリッドAとグリッドBのデータをそれぞれ入力します。
  2. グリッドの比較： 入力されたグリッドAとBを一行ずつ比較します。内部のループで、列に沿って各文字を比較し、異なる文字が見つかった場合その位置を確認します。
  3. 出力と終了： 異なる文字が見つかった最初の位置を1ベースインデックス（i+1, j+1）で出力し、プログラムを即座に終了させます。これにより、最初に見つかった異なる位置のみが出力されます。

C問題：Merge the balls

C – Merge the balls

問題

空の列と、N 個のボールがあります。i 個目 (1≤i≤N) のボールの大きさは 2Ai​ です。

これから N 回の操作を行います。
i 回目の操作では、i 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。

  1. 列にあるボールが 1 つ以下ならば操作を終了する。
  2. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 異なる ならば操作を終了する。
  3. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 等しい ならば、2つのボールを取り除き、「取り除かれた 2 つのボールの大きさの和」の大きさのボール 1 つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。

N 回の操作の後で、列にあるボールの数を求めてください。

解答

n=int(input())  # ボールの数Nを入力
A=list(map(int,input().split()))  # 各ボールの大きさの指数部を入力

stack = []  # 処理用のスタック

for a in A:
    current_ball = a
    while True:
        if stack and stack[-1] == current_ball:
            stack.pop()  # スタックの最後のボールと大きさが等しい場合、スタックから取り除く
            current_ball += 1  # 新しいボールの大きさを計算
        else:
            stack.append(current_ball)  # スタックに新しいボールを追加
            break
print(len(stack))  # 最終的なスタックの長さ（ボールの数）を出力

ポイント）

問題文から下記のポイントを押さえていきます。

問題文の理解と解釈

  • ボールは2のべき乗でサイズが与えられるが、指数の形での管理が計算を単純化する（2のAi乗のAiだけを使う）。
  • 2つの同じサイズのボールが隣り合うと合成され、一つの新しいボールになる。
  • この新しいボールは元のボールのサイズの和（指数においては+1された値）。
  • 合成が発生する度に、新しいボールはさらに合成を引き起こす可能性がある。

データ構造の選択

  • 配列stackとpop関数を利用することにより、後入先出しを実現する。
  • 各ボールをスタックに追加する前に、スタックのトップにあるボールと比較する。
  • もしトップのボールが現在のボールと同じサイズなら、トップのボールを取り除き、新しいサイズのボールを作成（指数で表すと+1）。
  • 新しいボールが再び合成を引き起こすかどうかを確認し、繰り返し合成を行う。

解き方(詳細)：

  1. 入力の取得： 入力からN個のボールの大きさの指数部をリストAとして取得します。
  2. ボールの処理： リストAからボールの大きさを取り出し、それぞれのボールに対して処理を行います。
  3. スタック操作：
    • スタックが空でなく、スタックの最後のボールの大きさが現在のボールの大きさと同じ場合、スタックからそのボールを取り除き、新しいボールの大きさを現在のボールの大きさの合計の次の大きさにします。
    • 上記の条件に当てはまらない場合、スタックに現在のボールを追加します。
  4. 終了条件のチェック： 合成が行えなくなるまで繰り返し、その後で次のボールに進みます。
  5. 最終結果の出力： 全てのボールを処理した後、スタックに残ったボールの数を出力します。これが列に残ったボールの数になります。

感想

今回はB問題までしか解けませんでした。

A問題は、9回のイニングでの各チームの得点差を計算し、チーム青木が勝つために必要な得点を求める問題でした。問題文は長かったですが、最終的には得点差+1の計算で解決しました。

B問題では、2つのN×Nのグリッドで異なる1文字を見つける問題でした。配列サイズが小さいため、全要素を比較する総当たり検索で効率的に解決することができました。

C問題に関しては、for文で各ボールを選択し、while文でボールが合成条件を満たすまでの処理を繰り返す必要がありました。最初は逆順の配列を使って直接的な解法を試みましたが、すべての合成条件を処理できずに失敗しました。この経験から、while文のより効果的な使い方を学ぶ必要があると感じています。

今回はオンタイムでの参加ができなかったので、レーティングに変動はありませんが、C問題が解けなかったことでレーティングが下がる可能性もありました。これを教訓にして、次回のコンテストではこの経験を活かしてさらに良いパフォーマンスを目指したいと思います。また、このブログを通じて振り返りを行うことで、同じ過ちを繰り返さないように努力します。

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

コメント

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