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

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

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

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

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

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

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

今回使用している機能・アルゴリズム

defaultdict (コンテナデータ型、辞書のサブクラス)　・・・　問題B、問題C
丸め誤差最小化(decimal)　　　　　　　　　　　　　・・・　問題C

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

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

AtCoder Beginner Contest 308

A問題：New Scheme

A – New Scheme

問題(要約)

8個の整数が与えられ、下記の３つの条件に当てはまっているかを判断する

S₁ ≦ S₂ ≦ S₃ ≦ ・・・ ≦ S₈
全て 100 以上、675 以下
全て 25 の倍数

解答

# 番号1
S=list(map(int,input().split()))

# 番号2
if not ((100 <= S[0] <= 675) and (S[0]%25==0)):
    exit(print("No"))

# 番号3
for i in range(1,8):
    if (S[i-1] <= S[i]) and (100<=S[i]<=675) and (S[i]%25==0):
        pass
    else:
        exit(print("No"))
# 番号4
print

考え方 (下の番号は、コード内のコメント番号と連携している)

基本的には、問題の指示通りにfor文を使って対応していく。

ただし、順番に増えていることを確認するために、

S₁ だけ単体で確認
S₂ ~ S₈ をfor文で確認

以下、プログラム内容詳細

入力Sを受け取る。mapを用いて整数化も実施
S1 の確認を行う
- if文を用いて規定の範囲内、25 で割り切れるかを確認する
- if文が成り立たなければ、プログラムを終了させ、”No”を出力する
for文を1から 8 まで繰り返す
- if文とandの組み合わせで問題文の３つの条件を確認する
  - 条件に当てはまれば、次を確認 (pass: 何もしない)
  - 条件に当てはまらなければ、”No” を出力しプログラムを終了させる
途中でプログラムが終了しなければ、全ての場合でOKとなるため、”Yes”を出力させる

B問題：Default Price

B – Default Price

問題(要約)

お皿の色によって価格が変わる場合に、N皿の料理を食べた時の合計金額を計算する。食べた皿の色と皿の色と価格は下記によって表される

C_i : i 皿目に食べた料理の皿の色
D_i : 料理の皿の価格設定の色　＊D₁ ~ D_M であることに注意
P_i : 料理の皿に対応した価格　＊ P₀: 上記Dの色に含まれない場合

解答

# 番号1
from collections import defaultdict

# 番号2
n,m=map(int,input().split())
C=list(input().split())
D=list(input().split())
P=list(map(int,input().split()))

# 番号3
dish_info = defaultdict(int)
for i in range(m):
    dish_info[D[i]]=P[i+1]

# 番号4
total=0

# 番号5
for c in C:
    if c in D:
        total+=dish_info[c]
    else:
        total+=P[0]

# 番号6
print(total)

考え方(下の番号は、コード内のコメント番号と連携している)

辞書型のdefaultdictを用いて、Di と Pi を登録する

食べた皿の色を確認して、D配列に含まれるか含まれないかを確認しつつ、値段を合計する

色と価格を登録するために、辞書型のdefaultdictをインポートする
入力 n, m, C, D, P をそれぞれ受け取る。C, D, P はリスト型で受け取る
dish_info変数に辞書型のdefaultdictを適用する
- 皿の色 (D配列) と価格 (P配列) を辞書型に登録する
- 注意：P₀ は、配列Dに含まれない場合なので、P₀の場合は辞書型に登録しない
合計金額を保持する total を準備する
食べた皿 C配列を順番に確認していく
- 食べた皿の色が D配列に含まれるかを確認する
  - 含まれる場合：辞書型の値を呼び出して total に加える
  - 含まれない場合： P₀ の値を total に加える
合計金額 total を出力する

C問題：Standings

C – Standings

問題(要約)

N人の人がコイントスを何回か行った。人i が表を出した回数を Ai、裏を出した回数を Bi とする。

コイントスの成功確率は Ai / (Ai + Bi) で表される。

成功率の高い順に並び替えを行う。ただし、成功率が同じ場合は、人の番号が小さい方を優先する

解答

# 番号1
from collections import defaultdict
import decimal

# 番号2
orders=defaultdict(float)
decimal.getcontext().prec = 50

# 番号3
n=int(input())
for i in range(n):
    a,b = map(decimal.Decimal,input().split())
    # 番号3-1
    orders[i+1]= a / (a+b)

# 番号4
for k,v in sorted(orders.items(), key=lambda x:x[1], reverse=True):
    print(k,end=" ")
print()

考え方(下の番号は、コード内のコメント番号と連携している)

それぞれの成功率を算出し、辞書型を用いて並び替えを行う。ただし、ポイントは、decimalを宣言することで、計算途中の桁おちや丸め誤差を防ぐようにする

以下詳細

辞書型のdefaultdictと桁落ちを防ぐためのdecimalをインポートする
defaultdictとdicimalを使用するための準備を行う
- 変数ordersを辞書型で宣言する。成功確率を保持するため、float型にする
- decimalの精度を指定。ここでは、50桁に設定。
  ＊ decimalの標準の28桁でもACになりました。その場合はこの記述は無しでも可
入力の受け取る
- nは整数型で受け取る
- a, b はdecimalを適用するため、map関数を用いて、decimalを適用する
  ＊注意：decimalに渡す際は、テキスト文字で渡す
  1. 成功率を計算 a / (a+b) し、辞書型のordersに番号とともに登録する
成功率の高い順にソートを行い、結果を出力する
- sort関数を用いてordersを並び替えを行う。辞書型の並び替えのポイントは下記
  - orders.items()とすることにより、(key, value)のタプルを参照できるようにする
    （補足参照)
  - lambda関数を用いて、タプル(key, value)のvalueを参照する
  - reverse=Trueにすることにより、昇順並びにする
- 辞書型のkeyに番号が登録されているため、key + 1 をしたものを要望方式に従って、出力する

補足：辞書型のdictとdict.items()の違い

辞書型dictをdict.items()で用いる時の違いを下記でまとめてもらいました

違い	`dict`	`dict.items()`
概要	辞書型オブジェクトを表す	キーと値のペアを表す
返り値	キーを使用して値にアクセスする	`(key, value)` のタプルとしてキーと値のペアを返す
使用例	`my_dict['key']`	`for key, value in my_dict.items():`
必要な時	値を直接取得する場合	キーと値のペアを両方使う場合