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

abc310 AtCoder

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

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

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

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

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

今回使用している機能・アルゴリズム
  • defaultdict (コンテナデータ型、辞書のサブクラス)　・・・　問題B

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

AtCoder Beginner Contest 310

A問題：Order Something Else

A – Order Something Else

問題(要約)

定価 P 円のドリンクを買おうとしている。Q円で飲めるクーポン券を持っているが、クーポンを使う場合は、料理を一品頼む必要がある。ドリンクが飲める最小金額を求める

解答

# 番号1
n,p,q = map(int,input().split())
D=list(map(int,input().split()))

# 番号2
total=10**5

# 番号3
for i in range(n):
    if q+D[i] < p:
        total = min(total, q+D[i])

# 番号4
if total < p:
    print(total)
else:
    print(p)

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

定価 P 円と、クーポンのQ円 + 料理１品の値段を比較する。支払い金額が最小値になるところをmin関数を使って求める

A < B の条件が成り立つため、隣り合う条件としては下記になる

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

  1. 入力n, p, q, Dを受け取る。
    • n, p, q: map関数を用いて整数化
    • D: map関数を用いて整数化し、配列化している (一つの変数で受け取るため)
  2. 最小値を格納するためのtotalを定義する。初期値は、PとQの最大値105に設定する
  3. for文を用いて１品料理のそれぞれの値段を取り出す
    • q + D[i] < P：定価よりもクーポン＋１品料理の値段の方が安い場合の存在確認
      • 更に、現行のtotalの金額よりも安いかどうかを確認し、安い方をtotalに設定する
  4. if文を用いて、total か P がどちらが安いかを最終判断する
    • total < P: totalを出力する
    • total >= P: Pを出力する

B問題：Strictly Superior

B – Strictly Superior

問題(要約)

N個の商品がある。各商品は下記情報が与えられる

  • Pi: i番目の商品の価格
  • Ci: i番目の商品の機能の数
  • Fi,j: I番目の商品のj番目の機能

下記の条件を満たす上位互換が存在するかどうかを判断する

  • Pi​≥Pj​ である
  • j 番目の製品は i 番目の製品がもつ機能をすべてもつ
  • Pi​>Pj​ であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ

解答

# 番号1
from collections import defaultdict
products = defaultdict(list)

# 番号2
n,m=map(int,input().split())

# 番号3
for i in range(n):
    tmp=list(map(int,input().split()))
    p,c = tmp[0],tmp[1]
    F = set(tmp[2:])
    products[i]=p,c,F

# 番号4
sortedProducts = sorted(products.items(), key=lambda x: x[1][0], reverse=True)

# 番号5
for i in range(n):
    if i+1 < n:
        for j in range(i+1,n):
            # 番号5-1
            if sortedProducts[i][1][2] <= sortedProducts[j][1][2]:
                # 番号5-2
                if (sortedProducts[i][1][0] > sortedProducts[j][1][0]) or (sortedProducts[j][1][1] > sortedProducts[i][1][1]):
                    exit(print("Yes"))
# 番号6
print("No")

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

  • それぞれの商品情報を辞書に登録し、金額の高い順に並び替える
  • 金額が高い方を基準として、安い方がすべの機能を保持しているかを確認する
  • “Pi​>Pj​ であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ” を確認する

以下詳細

  1. 各商品情報を登録するための辞書コンテナ型のdefaultdictをインポートする
    • 商品情報を登録するproductsをdefaultdictのリスト型で定義する
  2. 入力 n, m を整数型で受け取る
  3. 商品情報をfor文を使って一つづつ受け取る
    • tmp: 各行を整数型に変換しつつ、リスト型で受け取る
      　　 ＊文字数が決まっていないため、一旦1行全部を受け取っている
    • p, c: 金額と機能の数を変数に割り当てる（直接tmpで扱っても良い）
    • F: 各機能のナンバー、tmpの２番目以降を集合化する
      　 ＊スライサの使い方は、下記の補足を参照
    • 辞書型のproductsに通し番号の i をキーとして登録する
      • 例) ０行目の行情報が “10000 2 1 3” の場合は、{0: (10000, 2, {1, 3}) で登録される
      • {0: (10000, 2, {1, 3}) -> 0: 通し番号、10000: 価格、2: 機能の数、{1,3}: 機能番号
  4. 価格が高い順に辞書型のproductsを並び替える
    • products.items()を用いて、辞書型のkey, valueを扱えるようにする
      (タプル型: (key, value))
    • key部分にlambda関数を用いる事により並び替えたいものを選択する
      ＊ 今回のvalueは、(p, c, {F}) で成り立っているため、x[1][0]で選択する。
      　 x[1][0] … 辞書型のvalueの 0 番目の要素、つまり 価格p
  5. 価格の高い製品(カウンタ変数 i)を基準として、価格の安い製品(カウンタ変数 j) を全パターン比較する
    • if i + 1 < n を行う事により、i + 1 がリストの範囲外になりエラーになるのを防ぐ
      ＊ 高い方の製品の基準を i としているため、j のカウンタ変数を i + 1 ~ n で残りの商品を確認できる
      1. 製品 j の機能 Fj が、製品 i の機能Fi を全て含んでいるかを確認する
        • sortedProducts[i][1][2]: 製品 i 番目 – 辞書のvalue – ２番目の集合Fi を示す
        • if A <= B は、集合Aが集合Bに全て含まれる(包括)されているかを確認
      2. “Pi​>Pj​ であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ” を確認する
        • (sortedProducts[i][1][0] > sortedProducts[j][1][0]) は、価格の比較
          ＊sortedProducts[i][1][0]: 製品 i 番目 – 辞書のvalue – 0番目の価格p を示す
        • (sortedProducts[j][1][1] > sortedProducts[i][1][1]) は、機能数の比較
          ＊sortedProducts[i][1][0]: 製品 i 番目 – 辞書のvalue – 1番目の機能数c を示す
        • 上記のどちらかを満たせば、要望の条件を満たすことができるので、”Yes”を出力し、プログラムを終了させる
  6. 要望に一致する条件がなかったため、”No”を出力させる

C問題：Reversible

C – Reversible

問題(要約)

ボールがいくつか刺さった棒があり、各ボールには英小文字が1個書かれている。左端から英子文字を読んだ場合と右端から読んだ英子文字は同じものとみなす (棒を中心を起点に左右くるっと回すイメージ）。N個の英子文字が与えられる場合に、何種類の棒が存在するかを求める

解答

# 番号1
n=int(input())

# 番号2
setS=set()
cnt=0

# 番号3
for _ in range(n):
    s=input()
    rs = s[::-1]
    if s not in setS:
        cnt+=1
    setS.add(s)
    setS.add(rs)
print(cnt)

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

各文字列sが反転文字列rsを集合に登録する。この集合に含まれていなければ、カウンタを増やし数を数える

以下詳細

  1. 入力 n を整数型で受け取る
  2. setS と cnt の変数を準備する
    • setS: 文字列を集合として格納
    • cnt: 新たな文字列が出て来た時にカウント
  3. for文を用いて、文字列sを一つづつ確認していく
    • 入力 s を取り込む
    • 入力 s の逆読みを rs に設定する。スライスの使い方は補足参照
    • 入力 s が集合setSに含まれていないか確認する
      • 含まれていなければ、タイプの違う棒であるので、cntを１加算する
    • 入力 s と 逆順の rs を集合tに登録する。入力 s の逆順にも対応できるようにする
  4. 棒の本数の cnt を出力する

補足：スライスの使い方

スライスの各引数の意味と説明を下記表にまとめてもらいました

スライスの使い方第1引数第2引数第3引数説明
sequence[a:b]abインデックスaからbの直前までの要素を取得する。
sequence[a:]aインデックスaから最後の要素までを取得する。
sequence[:b]b最初の要素からインデックスbの直前までの要素を取得する。
sequence[a:b:c]abcインデックスaからbの直前までの要素をcのステップで取得する。
sequence[::-1]-1逆順に要素を取得する。
chatGPTにまとめてもらいました

C問題では、最後の要素の逆順を使用している

感想

ふて寝してしまった。。。順位が8000番台で、過去最低という結果にショックを受けました。始めからつまづき気味でした。A問題から一度不正解を出してしまいました。次のB問題は時間がかかりましたが、解法を見つけ提出。18/19 で不正解でした。あと一問、くっ、悔しいです。（´；ω；｀）

修正を試みましたが、一問の壁を越えられず、一旦諦めてC問題に挑戦しました。C問題は比較的簡単でしたが、提出した結果は不正解でした。なぜだろうと心の中で叫びつつ、B問題も解けず、C問題も解けず、ショック状態になりました。順位を確認すると、7000番台でしたし、残り時間も20分という状況で、もうパニックでした（＞﹏＜）

でも、正解に近いB問題だけでも解きたくて、何度も問題文を読み返しました。すると、残りの3分で問題の意図を取り違えていたことに気づき、B問題の正解に辿り着くことができました。（＾＾）

終わった直後にC問題を見直すと、なんと “not” を入れ忘れていたことに気づきました。あぁー、もったいない！（╯°□°）╯

毎週のコンテストでは、なかなか上手くいかず、苦戦が続いています。でも、苦戦が自分を強くすると信じて、来週も頑張っていきたいと思います。次回はきっと上手くいくはずです！（＾０＾）／

それでは、良い競プロライフを〜！(*＾▽＾)／

コメント

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