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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 359

A問題：Count Takahashi

A – Count Takahashi

問題文(要約)

文字列が N 個与えられます。

i 番目 (1 ≤ i ≤ N) に与えられる文字列 S_i は Takahashi か Aoki のどちらかと等しいです。

Si が Takahashi と等しい i がいくつあるか求めてください。

解答

n = int(input())  # 入力された文字列の数を取得

cnt = 0  # Takahashiのカウントを初期化

# N回繰り返し、各文字列をチェック
for _ in range(n):
    if input() == 'Takahashi':  # 入力された文字列が'Takahashi'であるかをチェック
        cnt +=1  # Takahashiのカウントを増やす
print(cnt)  # 最終的なTakahashiの数を出力

考え方）

入力文字が ‘Takahashi’ であるかどうかを判断し、そうであれば cnt を増やしていきます。

コード詳細

input()関数で入力を受け取り、それを整数型に変換して、Nに代入します。これが、与えられる文字列の数です。
cnt という変数を0に初期化します。この変数は、文字列「Takahashi」の数をカウントするために使います。
for ループを使って、N回繰り返し処理を行います。各ループで次の操作を行います:
- input()関数で新しい文字列を入力します。
- その文字列が「Takahashi」であるかをチェックします。
- もし「Takahashi」であれば、cntを1増やします。
ループが終了した後、print(cnt)で「Takahashi」の数を出力します。

B問題：Couples

B – Couples

問題

2N 人の人が横一列に並んでおり、左から i 番目の人は色 Ai の服を着ています。ここで、服の色は 1 から N の N 色であり、それぞれの色についてちょうど 2 人の人がその色の服を着ています。

i=1,2,…,N のうち、以下の条件を満たすものは何通りあるか求めてください。

色 i の服を着た二人の人の間にはちょうど一人いる。

解答

n = int(input())  # 人数の半分Nを取得
A = list(map(int, input().split()))  # 服の色の配列を取得

cnt = 0  # 条件を満たすペアの数をカウントする変数を初期化

# 2番目の人から始めて、2N番目の人までをチェック
for i in range(2, 2 * n):
    if A[i - 2] == A[i]:  # 現在の人と2つ前の人の色が同じかどうかをチェック
        cnt += 1  # 条件を満たす場合、カウントを増やす
print(cnt)  # 最終的なカウントを出力

考え方）

条件 “色 i の服を着た二人の人の間にはちょうど一人いる。”を言い換えると、２つ隣の人と同じ色 i になっているかを確認すれば良くなります。そのため、for文を 2から始めて一つづつ確認をしていきます。

コード詳細

input()関数で入力を受け取り、それを整数型に変換して、Nに代入します。これが、色の種類の数です。
次に、input()関数でスペース区切りの整数列を受け取り、map(int, input().split())で整数のリストに変換してAに代入します。このリストが、各人が着ている服の色を示しています。
cnt という変数を0に初期化します。この変数は、条件を満たすペアの数をカウントするために使います。
for ループを使って、2番目の人から2N番目の人までをチェックします。各ループで次の操作を行います:
- A[i-2]とA[i]の値が同じかどうかを確認します。これは、現在の人と2つ前の人の服の色が同じかどうかをチェックしています。
- もし同じ色であれば、cntを1増やします。
ループが終了した後、print(cnt)で条件を満たすペアの数を出力します。

C問題：Tile Distance 2

C – Tile Distance 2

問題(要約)

2×1のタイルが敷き詰められた座標平面上で、高橋君は点(S_x+0.5, S_y+0.5)から点(T_x+0.5, T_y+0.5)へ移動します。高橋君は異なるタイルを通るたびに通行料1を支払います。高橋君が目的地にたどり着くために支払う通行料の最小値を求めなさい。

解答

sx, sy = map(int, input().split())  # スタート地点の座標(Sx, Sy)を取得
tx, ty = map(int, input().split())  # ゴール地点の座標(Tx, Ty)を取得

cost = abs(ty - sy)  # 縦方向の移動でかかる最低コストを計算

# スタート地点のタイルの位置を決定
if (sx + sy) % 2 == 0:
    rmin = sx - cost  # タイルの右側にいる場合の最小x座標
    rmax = sx + cost + 1  # タイルの右側にいる場合の最大x座標
else:
    rmin = sx - cost - 1  # タイルの左側にいる場合の最小x座標
    rmax = sx + cost  # タイルの左側にいる場合の最大x座標

# ゴール地点がタイルの範囲内かをチェック
if rmin <= tx <= rmax:
    pass  # 範囲内であれば追加のコストは不要
elif rmin > tx:
    cost += (rmin - tx + 1) // 2  # 範囲外なら追加コストを計算
elif tx > rmax:
    cost += (tx - rmax + 1) // 2  # 範囲外なら追加コストを計算

print(cost)  # 最小コストを出力

解き方）

2×1のタイルであるため、縦方向の移動分のコストは必ず必要になります。縦方向の移動分で横方向がどこまで行けるかを考えます。その際に、2×1のタイルのどちらがわにいるかをまずは判断します。

(S_x + S_y) % 2 == 0が
- 偶数の時：タイルの左側
- 奇数の時：タイルの右側

タイルの右左側の位置を考えつつ、縦方向分の移動で稼働できる横範囲を求めます。縦方向の移動分をコストに加算します。

そして、最終的なコストを下記のように計算します：

縦方向の移動分の横方向の範囲内：縦方向のコストで到達可能
縦方向の移動分の横方向の範囲外：（範囲外分＋１）// 2 分を加算

解き方(詳細)：

input()関数でスタート地点(S_x, S_y)とゴール地点(T_x, T_y)の座標を取得します。
ゴール地点のy座標とスタート地点のy座標の差の絶対値を取り、それを縦方向の移動でかかる最低コストとして計算し、変数costに代入します。
スタート地点のタイルの位置を決定するために、(S_x + S_y) % 2 == 0 かどうかを判断します。
- 偶数ならば、高橋君は2×1タイルの右側にいることを示します。この場合、範囲を[Sx – cost, Sx + cost + 1]として計算します。
- 奇数ならば、高橋君は2×1タイルの左側にいることを示します。この場合、範囲を[Sx – cost – 1, Sx + cost]として計算します。
ゴール地点が計算されたタイルの範囲内にあるかをチェックします。
- 範囲内であれば、追加のコストは不要です。
- 範囲外であれば、ゴール地点がタイルの範囲を超えた分だけ追加コストを計算します。
最終的な通行料costを出力します。