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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 348

A問題：Penalty Kick

A – Penalty Kick

問題文

髙橋君はサッカーの試合で N 回ペナルティキックを蹴ります。

髙橋君は i 回目のペナルティキックでは、i が 3 の倍数の場合は失敗しそれ以外の場合は成功します。

髙橋君がペナルティキックを蹴ったときの結果を出力してください。

解答

n = int(input())  # ユーザーから入力を受け取り、整数としてnに格納

ans = ""  # 結果を格納するための空文字列
for i in range(1, n+1):  # 1からnまで繰り返し
    ans += 'x' if i % 3 == 0 else 'o'  # もしiが3の倍数なら'x'を、そうでなければ'o'をansに追加
print(ans)  # 結果の文字列を出力

考え方）

n回for文を回し、3で割り切れるかを確認していくことにより解くことができます。

下記がポイントになります。

ansの空文字の準備し、文字列を追加していきます
for文は、通常0スタートのため、1スタートにしてn+1までのn回の繰り返しにしています。
通常のif文でも問題ないですが、簡略化のため一行で記載しています。

コード詳細

ユーザーからペナルティキックの回数 n を入力として受け取ります。
空の文字列 ans を初期化して、キックの結果を記録します。
1から n までの数に対してループを行い、各回のキックを処理します。
各キック回数 i が3の倍数かどうかを判断します（i % 3 == 0 を使って判定）。
3の倍数であれば、結果文字列 ans に ‘x’（失敗）を追加し、そうでなければ ‘o’（成功）を追加します。
全てのキックの結果が文字列 ans に保存された後、この結果を出力します。

B問題：Farthest Point

B – Farthest Point

問題

平面上にN個の点があり、各点は一意の座標 (X_i, Y_i) を持ちます。各点に対して、その点から最も遠い点の番号を求めます。距離が最大である点が複数ある場合、番号が最も小さい点の番号を出力します。距離はユークリッド距離を用いて計算されます。

解答

import math

n = int(input())  # ユーザーから点の数Nを入力として受け取る

xy = [list(map(int, input().split())) for _ in range(n)]  # 各点の座標をリストに格納

for i in range(n):  # 各点iに対して
    dist = 0  # 最大距離を初期化
    num = -1  # 最大距離を与える点の番号を初期化
    for j in range(n):  # 他の全ての点jに対して距離を計算
        tmpDist = math.sqrt((xy[i][0] - xy[j][0])**2 + (xy[i][1] - xy[j][1])**2)  # 点iと点jのユークリッド距離
        if tmpDist > dist:  # もし新しい距離が今までの最大距離より大きければ
            dist = tmpDist  # 最大距離を更新
            num = j + 1  # 最大距離を与える点の番号を更新
    print(num)  # 各点iから最も遠い点の番号を出力

ポイント）

N≦100と点の数が少ないため、全検索を実施しています。つまり、for文をネストし（２重のfor文）、各点に対して全ての組み合わせを計算していきます。

コード詳細

プログラムはまずユーザーから点の数 n を入力として受け取ります。
次に、各点の座標 (X_i, Y_i) を入力し、リスト xy に格納します。
各点 i について、他の全ての点 j とのユークリッド距離を計算します。
距離計算は、座標差の平方を足した後、平方根を取ることで行います。
点 i からの距離が最も大きい点 j の番号を記録します。距離が同じ場合は番号が小さい点が自動的に選ばれます（ループが番号順に行われるため）。
各点 i に対して最も距離が大きい点の番号を出力します。

別解）scipyのdistanceモジュールを使った場合。

ユークリッド距離が簡単に求められます。

from scipy.spatial import distance  # scipyのdistanceモジュールをインポート

n = int(input())  # ユーザーから点の数Nを入力として受け取る

xy = [list(map(int, input().split())) for _ in range(n)]  # 各点の座標をリストに格納

for i in range(n):  # 各点iに対して
    dist = 0  # 最大距離を初期化
    num = -1  # 最大距離を与える点の番号を初期化
    for j in range(n):  # 他の全ての点jに対して距離を計算
        tmpDist = distance.euclidean(xy[i], xy[j])  # 点iと点jのユークリッド距離を計算
        if tmpDist > dist:  # もし新しい距離が今までの最大距離より大きければ
            dist = tmpDist  # 最大距離を更新
            num = j + 1  # 最大距離を与える点の番号を更新
    print(num)  # 各点iから最も遠い点の番号を出力

C問題：Colorful Beans

C – Colorful Beans

問題

N 種類のビーンズが 1 粒ずつあります。 i 種類目のビーンズはおいしさが A_i で色が C_i です。ビーンズは混ぜられており、色でしか区別することができません。

あなたはビーンズの色を 1 つ選び、その色のビーンズをどれか 1 粒食べます。ビーンズの色をうまく選ぶことで、食べる可能性のあるビーンズのおいしさの最小値を最大化してください。

解答

from collections import defaultdict

n = int(input())  # ユーザーからビーンズの種類数Nを入力として受け取る

beans = defaultdict(int)  # 色ごとにおいしさの最小値を記録する辞書

for _ in range(n):
    a, c = map(int, input().split())  # おいしさaと色cを入力
    if beans[c] == 0:
        beans[c] = a  # その色のビーンズがまだない場合は初期値として設定
    else:
        beans[c] = min(beans[c], a)  # 既存のその色のビーンズと比較して最小値を更新

maxTaste = 0  # 食べるビーンズのおいしさの最小値の最大化値
for k, v in beans.items():
    maxTaste = max(maxTaste, v)  # 各色について、おいしさの最小値の中で最大のものを探す

print(maxTaste)  # 最終的に選べる色の中でのおいしさの最小値の最大化値を出力

ポイント）

次のステップで解答を導いています。

ビーンズの色ごとにおいしさの最小値を辞書型で記録
ビーンズの色ごとのおいしさの最小値を比較し、おいしさの最大値を算出

連想配列のdefaultdictを用いており、登録時にその色がビーンズにまだ無いかも判別しています。

解き方(詳細)：

プログラムは最初にビーンズの種類数 n をユーザーから入力として受け取ります。
defaultdict を用いて、色ごとにその色のビーンズのおいしさの最小値を保持します。
n 種類のビーンズについて、それぞれのおいしさ a と色 c を入力します。
色 c に対応する現在のおいしさの最小値と比較して、必要に応じてその値を更新します。ここで beans[c] の初期値が0なのは、Pythonの int のデフォルト値が0だからです。
全ての色に対して、その色のビーンズを選んだ場合のおいしさの最小値の中で最大のものを探します。
最終的にその最大値を出力します。これは選ぶことのできる色の中でのおいしさの最小値が最大化された値です。