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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 352

A問題：AtCoder Line

A – AtCoder Line

問題文(要約)

AtCoder線にはN個の駅があり、1番からN番まで番号付けされています。この鉄道には上り列車と下り列車があり、高橋君は駅Xから駅Yまでどちらか一方の列車を使って移動しようとしています。移動中に特定の駅Zに停車するかどうかを判定する問題です。

解答

# 入力を受け取り、整数に変換します。
n, x, y, z = map(int, input().split())
# 駅Xから駅Yへの移動経路に駅Zが含まれているかを判定し、結果を出力します。
print("Yes" if min(x, y) <= z <= max(x, y) else "No")

考え方）

上りと下りがあるため、駅xと駅yの最小値と最大値を求め、駅zがその区間に含まれるかを確認します。

コード詳細

入力の取得と変換：n, x, y, z の4つの整数を入力から受け取り、整数型に変換します。ここで n は駅の総数を、x は出発駅、y は到着駅、z は判定対象の駅を表します。
条件判定：min(x, y) <= z <= max(x, y) の条件式で、駅Zが駅Xと駅Yの間にあるかどうかをチェックします。これにより、駅Xから駅Yに向かう途中で駅Zに停車するかどうかが判定されます。
結果の出力：条件式が真（True）の場合は "Yes" を、偽（False）の場合は "No" を出力します。これにより、高橋君が駅Zに停車するかどうかの回答が得られます。

B問題：Typing

B – Typing

問題（要約）

高橋君は目を閉じて英小文字の文字列 S を入力しようとしましたが、タイピングミスがあります。間違って入力された文字を消そうとしてバックスペースを押しましたが、バックスペースキーが壊れていて間違い文字が削除されませんでした。その結果、実際に入力された文字列が T になりました。T の中で正しく入力された文字の位置（1から始まるインデックス）を求める問題です。

解答

S = input()  # 正しく入力しようとした文字列Sを入力
T = input()  # 実際に入力された文字列Tを入力

ans = []  # 正しく入力された文字の位置を格納するリスト
j = 0  # 文字列Sのインデックスを追跡するための変数

for i, t in enumerate(T):  # 文字列Tを一文字ずつ取り出しながら、そのインデックスも取得
    if S[j] == t:  # 文字列Sのj番目の文字と文字列Tのi番目の文字が一致するか確認
        ans.append(i + 1)  # 一致した場合、その位置（1-indexed）をansに追加
        j += 1  # 文字列Sの次の文字に移動
print(*ans)  # 結果を空白で区切って出力

考え方）

文字列Sの序数を j とおき、文字列Tの中にS[ j ] が現れたら j の数を加算することにより解いていきます。

コード詳細

入力の取得: S と T 、2つの文字列を入力します。S は意図した入力、T は実際の入力です。
正しい文字の検出: T の各文字に対して、S の文字と一致するかを確認します。これにより、正しく入力された文字を特定します。
位置の保存: 文字が一致した場合、その位置（1から始まるインデックス）をリスト ans に保存します。
インデックスの更新: 文字が一致するたびに S のインデックス j をインクリメントして、次の比較の準備をします。
結果の出力: 最終的に ans リストに保存された位置を出力します。これには print(*ans) を使い、リスト内の要素を空白で区切って出力します。

C問題：Merge the balls

C – Merge the balls

問題（要約）

N人の巨人がいて、それぞれの巨人は固有の肩の高さ A_i と頭の高さ B_i を持っています。これらの巨人を特定の順序で積み重ねることにより、最上部の巨人の頭がどの程度の高さに達するかを求める問題です。肩の上に次の巨人が乗ることでその巨人の頭の高さがどう変わるかを計算し、最も高くなる組み合わせの頭の高さを求めます。

解答

n = int(input())  # 入力される巨人の数N

highest_head = 0  # 最大の頭の高さ（頭部分のみ）

height = 0  # 現在の積み上げた肩の高さの合計

for _ in range(n):
    a, b = map(int, input().split())  # 各巨人の肩の高さaと頭の高さbを入力
    height += a  # 肩の高さを加算して積み上げる
    highest_head = max(highest_head, b - a)  # その巨人の頭の位置（相対値）で最大のものを更新

print(height + highest_head)  # 積み上げた肩の高さ合計と、最大の頭の位置を合算して出力

ポイント）

最上部の高さは、下記の式で求めることができます。

最上部の高さ　＝　各巨人の肩の高さの合計　＋　最も頭の長い巨人の頭の長さ　

そのため、各頭の長さを求め、その中から最も頭の長い巨人の頭の長さを探すことにより、求めることができます。

解き方(詳細)：

入力の取得と初期化：巨人の数 N を入力し、最終的に求める最高の頭の高さと肩の高さの累積値を初期化します。
巨人の情報読み取りと処理：N 回のループを使って各巨人の肩の高さ a と頭の高さ b を入力します。巨人を積み上げる際、その巨人の肩の高さ a を現在の積み上げ高さに加え、同時にその巨人の頭の位置（b−a）が現在までのどの巨人の頭の位置よりも高いかを確認し、最大値を更新します。
最終結果の計算と出力：すべての巨人を積み上げた後の肩の高さ合計 height と最大の頭の位置 highest_head を加算し、それを出力します。これが積み重ねた巨人の中で最も高くなる頭の高さです。