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

abc312 AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 312

A問題：Chord

A – Chord

問題(要約)

英大文字からなる長さ3の文字列 S が与えられます。Sが与えられた文字列と等しいかを判断する

解答

# 番号1
check=['ACE', 'BDF', 'CEG', 'DFA', 'EGB', 'FAC', 'GBD']

# 番号2
S=input()

# 番号3
if S in check:
    print('Yes')
else:
    print('No')

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

与えられた文字列をリストに格納し、文字列 S が含まれるかどうかを判断する

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

  1. 与えられた文字列リストを配列 check に登録する
  2. 入力Sを受け取る
  3. 文字列が配列checkに含まれるかを確認する
    • 含まれる場合は、”Yes”を出力する
    • 含まれない場合は、”No”を出力する

別解) 内包表記を用いることにより1行で記載することができる。考え方は上記と同様。

print('Yes' if input() in ['ACE', 'BDF', 'CEG', 'DFA', 'EGB', 'FAC', 'GBD'] else 'No')

（こういう回答がすぐに書けるようになったら、カッコイイ！）

B問題：TaK Code

B – TaK Code

問題(要約)

2次元コード Tak Codeは以下の特徴を持っている

  • 縦 9 マス 横 9 マスの領域である。
  • 左上及び右下の縦 3 マス 横 3 マスの領域に含まれる計 18 マスは全て黒である。
  • 左上及び右下の縦 3 マス 横 3 マスの領域に八方位で隣接する計 14 マスは全て白である。

縦Nマス、横Mマスに白 . , 黒 # が配置してあるグリッドが与えられ、この中のTak Codeの位置(左上位置)を全て出力する

解答

# 番号1
n, m=map(int,input().split())
S = [input() for _ in range(n)]

# 番号2
TakCode = [
    '###.?????', 
    '###.?????', 
    '###.?????', 
    '....?????', 
    '?????????', 
    '?????....', 
    '?????.###', 
    '?????.###', 
    '?????.###'
    ]

# 番号3
def checkTakCode(i,j):
    for k in range(9):
        for l in range(9):
            if (i+k>=n) or (j+l>=m):
                return False
            if TakCode[k][l] != '?':
                if TakCode[k][l] != S[i+k][j+l]:
                    return False
    return True

# 番号4
ANS=[]

# 番号5
for i in range(n):
    for j in range(m):
        if S[i][j]=='#':
            boo=checkTakCode(i,j)
            if boo:
                ANS.append((i+1,j+1))
# 番号6
for r,c in ANS:
    print(r,c)

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

TakCodeの配列を事前に登録する。与えられた配列Sを左上から順番に確認し、# マークだった場合に、登録したTakCodeと比較する。決まりごとの部分が同じ場合にその座標を登録する

以下詳細

  1. 入力 n, m, S を受け取る
    • n, m: 整数型で受け取る
    • S: 内包表記をもちいて2次元配列で入力を受け取る
  2. Tak Code情報を登録する
    • 与えられた規則に則って、TakCode配列を作成する。
      • 規則がない部分は、? 文字で表現している
    • 入力例1の説明の中に上記の配列があるので、その情報をもちいてコピペすると楽。
  3. TakCodeと一致するかどうかの簡易関数 checkTakCode を作成する
    • 引数には、確認したい領域の左上の行列番号を与える
    • TakCodeは 9 x 9 であるため、２重のfor文(カウンタ変数 k, l)を準備する
      • TakCodeかどうかを確認する際に与えられた枠外に出てしまうのを防ぐため、if文で制限を持たせる ( if (i+k>=n) or (j+l>=m) )
        • 枠から外れた場合は、False を返す
      • TakCodeの ? 部分は任意であるため、この部分の確認はスキップする
        • TakCodeの規則部分と抜き出した元の配列が一致するかを確認する
          (if TakCode[k][l] != S[i+k][j+l] の部分)
          • 一致しなかった場合は、TakCodeではないため、Falseを返す
    • for文を全て確認し終えた場合はTakCodeであるため、Trueを返す
  4. 求めるTakCodeの左上の番地を保持するためのANSの空配列を準備する
  5. 配列Sを左上から右下にかけて一つづつ確認する
    • ２重のfor文で値を取り出し、その値が # であるかを確認する
      • # である場合は、checkTakCode を実行する。引数には現在の位置i, jを渡す
      • checkTakCodeの結果(True or False) をbooで受け取る
      • booがTrueの場合は、TakCodeを発見できたので、ANSに現在の座標情報をタプルで登録する
        ＊ 回答は左上を1始まりにしているので、それぞれに1を足している
  6. ANSに登録したタプルを取り出し出力する

C問題：Invisible Hand

C – Invisible Hand

問題(要約)

りんご市場にN人の売り手とM人の買い手のがいる。下記の条件を満たす金額を求める

  • りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。

解答

# 番号1
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))

# 番号2
_C = set(A+B)
C = sorted(_C | {x+1 for x in _C})

# 番号3
sellP,buyP=0,m
idxS, idxB = 0,0

# 番号4
for c in C:
    # 番号4-1
    if idxS<n:
        while c >= A[idxS]:
            idxS+=1
            if idxS==n:
                break
    # 番号4-2
    if idxB<m:
        while c > B[idxB]:
            idxB+=1
            if idxB==m:
                break
    # 番号4-3
    if idxS >= m-idxB:
        exit(print(c))

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

売り手と買い手のリストを昇順に並び替えて、次の追加リストCを作成する

  1. 更に売り手と買い手のリストを組み合わせ (重複は削除)
  2. 上記1で作成したリストに1円を足した値を作る
  3. 上記1, 2を組み合わせ、昇順に並び替える

新たな価格リストに対して、売り手と買い手の数を数えていく。売り手と買い手を昇順かすることにより、インデックス番号で管理することで再計算をせずに求めることができる

以下詳細

  1. 入力 n, m, A, B を受け取る
    • n, m: 整数型で受け取る
    • A, B: 整数型のリストでそれぞれ受け取り、昇順に並び替えを行う
  2. AとBの組み合わせとそれぞれに1を加算したリストCを作る
    • _C: AとBの集合 (一時保管用)
    • 内包表記、和集合、ソートを用いてCを作る
      • {x+1 for x in _C}: 内包表記を用いて _C の値に1を加算したリストを作る
      • _C | {x+1 for x in _C}: 和集合を用いて元の _C と上記で作成したものを組み合わせる
      • 上記をsorted()を行うことにより、昇順の配列を作成する
  3. 売り手と買い手のインデックスを保持するための変数を準備する
    • idxS, idxB = 0, 0 : 売り手と買い手のリストのインデックスを保持する変数
  4. Cの各金額に対する買い手と売り手の数を求める
    1. 売り手の人数 (インデックス番号) を求める
      • idxSがリストから外れないように制限を設ける (if idxS < n)
      • while文を用いて、現行の価格 c がインデックスの何番目に当たるかを確認
      • このwhile文に対してidxSがリストから外れないように制限(idxS==n)を設け、外れた場合は、breakでwhile文を抜ける
    2. 買い手の人数 (インデックス番号 ) を求める
      • 上記の売り手の時と同様のやり方でインデックス番号を求める
    3. 売り手の人数 idxS が 買い手の数 m – idxB よりも多くなった場合にその金額を出力する

感想

C問題まで解けた先週の喜びを胸に、今週も頑張りましたが…。

B問題までしか解けませんでした(´・ω・｀) 

B問題は、パターン認識系の問題に初めて挑戦したので、最初はどう進めればいいのか戸惑いましたが、Pythonのdefを使った簡易関数で解答にたどり着けました。

C問題は、インデックスの考えで徐々に正解に近づけていけていたのですが、時間内には完璧な回答にならず(T_T)

数ヶ月前までは簡易関数を作ることに戸惑っていた自分がいましたが、今回はスムーズに作成できたので、少しずつ実力がついてきたんだと感じています。(｀・ω・´)ゞ

自分の実力を花火のように打ち上げる日を夢見て、これからも競プロライフを楽しんでいきたいと思います！

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

コメント

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