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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 290

A問題：Contest Result

A – Contest Result

問題(要約)

N問の配点がそれぞれ与えられ、M問を解いた番号を与えられた時の得点を求める

解答

# 空白区切りの入力を受け取り(input())、split()で空白区切りにする(リスト化)
# map関数を用いて、上記のリストの要素に整数型(int)を当てはめる(キャスト)
# map関数の0番目をn, 1番目をmとして代入する
n,m=map(int,input().split())

# 空白区切りの入力を取得(input())、split()で分割(リスト化)
# map関数で上記のリストの要素に整数型(int)を当てはめる(キャスト)
# list()を用いることにより、リストとして受け取る
A=list(map(int,input().split()))
# 上記配列Aと同様
B=list(map(int,input().split()))

# 下記参照
cnt=0
for i in B:
    cnt+=A[i-1]
print(cnt)

考え方

合計点を記憶するための変数cntを作り、初期値0とする
for文を用いて、B配列の番号をそれぞれ取り出し、カウンタ i に代入する。
配列AのB配列の問題番号の得点を取り出し、cntに加える。
- カウンタ i は、問題番号を示し、1始まり。
- 配列Aは問題順の配列になっており、0始まり。
- カウンタ i から1を引いた ( i – 1 ) が、配列Aの問題順に当たる
- cnt += A[ i – 1] は、cnt = cnt + A[ i – 1] を省略した形
合計点が格納されたcntをprintを用いて出力する

B問題：Qual B

B – Qual B

問題(要約)

　順位順に並んだ長さNの文字列Sが与えられ、決勝への参加の有無を記号 o, x で示してる。決勝への参加を希望したうちの上位k人が参加可能になる。決勝へ参加する人を o とした順位順の配列を出力する。

解答

# 空白区切りの入力を受け取り(input())、split()で空白区切りにする(リスト化)
# map関数を用いて、上記のリストの要素に整数型(int)を当てはめる(キャスト)
# map関数の0番目をn, 1番目をkとして代入する
n,k=map(int,input().split())
# 文字列入力を受け取り、s に代入する
s=input()

# 下記参照
cnt=0
T=[]
for i in range(len(s)):
    if s[i]=="o" and cnt<k:
        T.append("o")
        cnt+=1
    else:
        T.append("x")
print(*T, sep="")

考え方

決勝への参加人数制限 k を超えないようにするため、変数 cnt を用いて “o” の数を記憶させる。
cntの初期値は0とする
回答の配列を格納するため、Tの空配列を作る
for文を用いて、一文字づつ参加有無 “o” を確認していく。
＊len(s)で配列の長さを取得し、range() を用いることにより配列長さ分forを繰り返す
- i番目の配列s、s[ i ] が “o” と等しいかを確認
  - さらに、cnt が k よりも小さいかを確認 (k人の人数制限のため)
    ＊コードでは、演算子 and を用いて一行で同時に判断を行なっている
    - 配列に “o” を追加する
    - 参加者を一人選んだため、cntに一人を加える (cnt+=1)
- i番目の配列s、s[ i ] が “o” と等しくない場合
  - 配列に “x” を追加する
print関数を用いて、リストをアンパック(*)、隙間を削除しながら出力する
- リストのアンパックは、リストにアスタリスクをつけることにより、リスト内の全てを空白区切りで出力できる
- printのオプション関数の sep は、要素間を制御できる sep=”” とすることで隙間無しとなる

C問題：Max MEX

C – Max MEX

問題(要約)

　長さNの非負整数列Aが与えられ、K要素を選んで順番を保ったまま抜き出した配列をBとし、MEX(B)の最大値を求める
MEX(B)は以下の条件を満たす唯一の非負整数mとして定義される

0 ≦ i < m を満たす全ての整数 i がBに含まれる
mがBに含まれない

更に要約すると、配列Aからk個抜き出し配列Bを作り、配列Bに含まれない0以上の一番小さい値を求める。
　例： B = [2, 0, 2]の時 m = 1、B = [0, 1, 9]の時 m = 2、B = [0, 2, 1] の時 m = 3

解答

# 空白区切りの入力を受け取り(input())、split()で分割する(リスト化)
# map関数で各要素に対して、整数型(int)を当てはめる(キャスト)
n,k=map(int,input().split())

#下記参照
A=set(map(int,input().split()))
#print(A)
for i in range(k):
    if i not in A:
        exit(print(i))
print(k)

考え方

問題文より、今回の配列Bと非負整数mは下記の特徴を持っている
- 配列Bは配列Aの任意の場所を抽出できる
- 非負整数mは、配列Bに含まれない0以上の最小値
- 非負整数mは、配列Bの要素数K以上になりえない (0 ≦ m ≦ K)
上記より、配列Aに 0 〜 K-1までの要素が含まれているかを確認する。含まれていない要素があれば、その要素が最大値となり、全て含まれていれば、配列Bの長さ文のKが最大値となる
(ここから実際のコード説明)
空白区切りの配列Aを下記の手順で取り込む
- input().split()で分割する(リスト化)
- map関数で各要素に対して整数型(int)を当てはめる(キャスト)
- 検索を高速化するために、set関数(集合化)を適用する
  ＊リストは要素一つづつ確認するのに対して、集合は一回で含まれているか確認可能
  　（リストは順番を維持するが、集合は順番を持たない)
カウンタ i のfor文を用いて、配列Aに含まれない k-1 までの最小値を調べる
＊ pythonではrange(k) とすることにより、i ≦ k-1 までfor文を繰り返えす
- if文で i が集合Aに含まれるかを確認する
  - 含まれていないものがあれば、最大値となるためprint関数で出力し、exitでプログラムを抜ける
for文を途中で抜けることなく終了した場合は、kが最大値になるため、kを出力する