(ABC294)A-C問題のpythonでの解法

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

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

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

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

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

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

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

数字→アルファベット化　・・・　B問題

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

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

AtCoder Beginner Contest 294

A問題：Filter

A – Filter

問題(要約)

整数列Aの中から、元の順番を維持したまま偶数だけ取り出す。

解答

# 入力nを受け取り、整数型に変換(キャスト)する
n=int(input())

# スペース区切りの入力を受け取り(input())、split()で空白区切りを行う(リスト化)
# map関数を用いて、各要素を整数型(int)に変換(キャスト)を行う
# map関数の形式になっているため、リスト型(list())に戻す
A = list(map(int,input().split()))

ans=[]
for a in A:
    if a%2==0:
        ans.append(a)
print(*ans)

考え方

入力nと配列Aを受け取る
答えを入れる配列ansを準備する
for文を用いて配列の各要素を呼び出す
偶数判定のため、2で割り切れるかを確かめ、割り切れたら配列ansに追加(右側に追加)
printのアンパック(*：アスタリスク)を用いて、回答を出力
＊リストのアンパックは、リスト内の要素をスペース区切りで出力できる

B問題：ASCII Art

B – ASCII Art

問題(要約)

　H行W列の行列の各要素に0以上26以下の番号が与えられている。0の時は、ピリオド( . )、そうでなければアルファベット(1: A, 2: B, 3: C, ・・・)を出力する

解答

# 空白区切りの入力受け取り(input())、split()で空白区切りを行う(リスト化)
# map関数を用いて、それぞれを整数型(int)に変換(キャスト)
h,w=map(int,input().split())

for _ in range(h):
    tmp=[]
    A=list(map(int,input().split()))
    for a in A:
        if a==0:
            tmp.append(".")
        else:
            tmp.append(chr(64+a))
    print(*tmp,sep="")

考え方

h行の入力を受け取るため、for文をh回繰り返す
各行毎に処理を行うため、一時保存の配列tmpを用意する
各行の空白区切りの入力を配列Aに代入する
配列Aの各要素aに対してアルファベット化の処理を行う
- a=0の時、tmp配列にピリオド( . )を追加する
- それ以外の時は、アルファベットをtmp配列に追加する
  chr関数は数字をアルファベット化することができる。chr(65)=A, chr(66)=B, ・・・
リストをアンパック(アスタリスク、各要素を空白区切りにする)して出力する。
ただし、そのままでは要素間に空白が含まれてしまうため、print関数のsepのオプションを用いて空白をなくす(sep=””を追加することにより、要素間の隙間を無しにできる)

C問題：Merge Sequences

C – Merge Sequences

問題(要約)

重複の数字がない二つの単調増加の配列A, Bが与えられ、それを昇順に組み合わせたCを作成し、Cにおいて、それぞれの配列の要素が何番目に当たるかを出力する

解答

# 空白区切りの入力を受け取り、整数型(int)に変換し、n,mに代入する
n,m=map(int,input().split())
# 配列A,Bをそれぞれ受け取り、整数型(int)に変換し、リストとして受け取る
A=list(map(int,input().split()))
B=list(map(int,input().split()))

C=[0] * (n+m)
Acnt,Bcnt=[],[]
i,j=0,0
for k in range(n+m):
    if i<n and (j>=m or A[i]<B[j]):
        C[k] = A[i]
        Acnt.append(k+1)
        i+=1
    else:
        C[k] = B[j]
        Bcnt.append(k+1)
        j+=1
print(*Acnt)
print(*Bcnt)

考え方

AとBを組み合わた配列Cを格納するための空の配列を準備する。
C配列の長さは、A配列の長さ＋B配列の長さ (n+m) とし、0で初期化する
求める回答(各配列のC配列における順番)を入れる空の配列Acnt, Bcntを準備する
A, B配列から昇順で要素を選び、C配列に追加していく。そのために、A, B配列の何番目まで選んだのかを記憶するための変数 i(A配列), j(B配列)を0で初期化する
C配列の長さ分(n+m)、for文を繰り返す。Cの何番目を示すためにカウンタとしてkを用いる
- A[i] < B[j] (A[i] の方が小さい) 時。
  ただし、状況により i が n を超えてしまう。B配列を取得終わる(j >= m)ことがあるため、if文に条件を追加する。
  if文の判定は左側が優先されるため、i < n を先に判定するようにする必要がある。i < n をandの右側に持ってきた場合は、i が n を超える場合が発生し、エラーとなる
  - Cのk番目がAのi番目にあたるため、C[k]にA[i]を代入する
  - AcntにC配列の順番kを代入する。A[i]の要素がC配列における順番を保存
  - iに1を足す
- A[i] > B[j] (B[j] の方が小さい) 時
  - Cのk番目がBのj番目にあたるため、C[k] に B[j] を代入する
  - BcntにC配列の順番kを代入する。B[j]の要素がC配列における順番を保存
  - jに1を足す
配列Acnt, Bcnt をアンパックしながら出力する