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

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

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

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

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

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

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

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

defaultdict (コンテナデータ型、辞書のサブクラス)　・・・　問題B, 問題C

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

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

AtCoder Beginner Contest 314

A問題：3.14

A – 3.14

問題(要約)

小数点第100までの円周率が与えられる。円周率を小数点第N位まで出力する

解答

# 番号1
pie='1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'

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

# 番号3
ans='3.'+pie[:n]

# 番号4
print(ans)

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

与えられた円周率に対して、下記のように扱う

小数点部分だけを抜き出す
文字列として扱う

上記で扱うことにより、スライス機能を使って答えを出力する

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

与えられた円周率の小数点部分を変数pieに代入する
入力 nを受け取る
- n: 整数型で受け取る
目的の円周率を作成する
- 整数部分 3. は固定であるため、3. と小数点部分を組み合わせる
- 小数点部分は、文字列 pie の n 文字目までを取得すればいいため、スライス機能を使って文字列を取得する
  - pie[:n] は、[ ] の左側にスタート文字 0 (省略)、右側にエンド文字 n を表す
ansを出力する

B問題：Roulette

B – Roulette

問題(要約)

N人の人がルーレットの賭けに参加した。ルーレットの出目は 0から36 の37個の整数のどれかである。人_i は、C_i 個の C₁, C₂, … , C_i に賭ける

ルーレットの出目がXだった場合に、賭けた目の個数が最も少ない人たちの番号を昇順に出力する

解答

# 番号1
from collections import defaultdict

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

# 番号3
Bets = defaultdict(set)
Nums = [0] * (n+1)

# 番号4
for i in range(n):
    c=int(input())
    Nums[i+1] = c
    A=list(map(int,input().split()))
    for j in range(c):
        Bets[A[j]].add(i+1)

# 番号5
x=int(input())

# 番号6
if x in Bets:
    cnt=38
    Ans=[]
    for i in Bets[x]:
        if Nums[i]<cnt:
            Ans = [i]
            cnt = Nums[i]
        elif Nums[i]==cnt:
            Ans.append(i)
    print(len(Ans))
    print(*Ans)

# 番号7
else:
    print(0)
    print()

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

賭ける番号 C_i に対して、人_i の情報をひもづける -> 出目 X に対して誰が勝ったかがわかる

その上で、賭けた数が少ない人を抜き出す必要があるため、下記の手順を行う

各人の掛けた数を管理するリストを準備する
掛けた番号と人の関係リストから、勝った人の番号を抽出
掛けた数と勝った人の番号リストから、賭けた数が少ない人を抜き出す

以下詳細

辞書の拡張型のdefaultdictを用いるため、インポートを行う
＊辞書の値にリストや集合を持ってくることが容易
入力 n を受け取る
- n : 整数型で受け取る
下記２つの変数を準備する
- Bets: ルーレットの出目に対する賭けた人の数を管理する
  　　　インポートしたdefaultdictを用いて、辞書型のvalue(右側)を集合とする
- Nums: 人_i が賭けた数を管理する。
  　　　 n+1 とすることで配列のインデックス番号と問題文の番号を合わせている
N人が賭けた番号と出目を受け取りつつ、上記２つの変数に紐付けを行う
- カウンタ変数 i を用いてfor文を実行する。i は人i 情報となる
  - 入力 c を整数型で受け取る
  - 受け取った c を Nums の人_(i+1) 番目に登録する
    ＊ (i+1) はリストが 0 始まりのための調整
  - 賭けた番号の A を整数型のリストで受け取る
  - for文を用いて、賭けた目をひとつづつ取り出す
    - Betsに賭けた目に対する人_(i+1) を登録していく
    - 各賭けた数字に対して、誰が賭けたかがわかる
ルーレットの結果の出目 x を整数型で受け取る
ルーレットの出目 x に賭けた人がいるかどうかを確認する
Betsは辞書型であるが、in Bets とすることで、key(左側) に存在するかを確認できる
- 賭けた人が存在するため、賭けた最小の数の人を確認する
- 下記二つの変数を準備する
  - cnt: 賭けた数の最小値を確認する。初期値は出目の数より大きい38としている
  - Ans: 賭けた最小の数の人の番号を保存していく配列
- for文を用いて、ルーレットの出目 x に賭けた人番号を取り出す
  ( for i in Bets[x] とすることで、人番号 i を取り出せる)
  - if Nums[i]<cnt: 現在の賭けた数の最小値 cnt と人i の賭けた数 Nums[i] を比較する
    - Nums[i] が小さい場合は、Ansに人番号 i を登録し、cntも更新する
  - Nums[i] == cnt: 現在のcntとNums[i] が同じ場合は、最小値同士のためAnsリストに人番号 i を追加する
上記6のルーレットの出目 x に賭けた人がいない場合の出力を行う
- 誰もいないため、人数は 0 とする
- 誰もいないため、人番号は空白にする。＊注意：空白の出力必要＊

C問題：Rotate Colored Subsequence

C – Rotate Colored Subsequence

問題(要約)

英小文字からなる長さNの文字列Sが与えれる。Sの各文字には、M色のうちのどれかの色が塗られており、Sの i番目の文字は C_i の色が塗られている

各色 i = 1, 2, …, M において、下記の操作を繰り返す

Sの色i で塗られた文字からなる部分を右に1つ巡回シフトする

上記の操作を全て終わった後の文字列を出力する

解答

# 番号1
from collections import defaultdict

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

# 番号3
colors = defaultdict(list)
for i,c in enumerate(C,start=1):
    colors[c].append(i)

# 番号4
s_Num = [x for x in range(n+1)]

# 番号5
for k,v in colors.items():
    rotation_v = [v[-1]]+v[:-1]
    for i,j in zip(v, rotation_v):
        s_Num[i]=j

# 番号6
for i in s_Num[1:]:
    print(S[i-1],end="")
print()

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

下記２つのリストを準備する

辞書にカラー毎の文字列Sのインデックス番号を登録する
文字列Sの順番とインデックス番号の情報をもたしたリストを作成する

カラー毎のインデックス番号を取り出し、巡回したインデックス番号を作成する

上記を用いて、文字列Sのインデックス番号がどのように変換したかを確認する

上記の番号を用いて文字列を並び替える

以下詳細

辞書の拡張型のdefaultdictを用いるため、インポートを行う
＊辞書の値にリストや集合を持ってくることが容易
入力 n, S, C を受け取る
- n: 整数型で受け取る
- S: 文字列型のままで受け取る
- C: 数字に変換し、リストで受け取る
色毎の文字のインデックス番号をまとめる
- colors: リストを持った辞書型で定義をする
- 色配列Cを一つづつ確認していく
  - for文にenumerateを用いることにより、インデックス番号と要素を同時に取り出す。また、enumerateの引数に start=1 を適用し、インデックス番号を1からにしている
  - 辞書のキーを色cとして、文字のインデックス番号を登録する
インデックス番号に文字順、各要素は文字列Sのインデックス番号に当たるs_Numを準備する
- 入力例1の場合
  - 文字列S: apzbqrcs
  - s_Num: [0, 1, 2, 3, 4, 5, 6, 7, 8]
  - s_Num[1]は、a, s_Num[2]は、p, …, s_Num[8]は、s を示す
  - 例えば、s_Num: [0, 2, 1, 3, 4, 5, 6, 7, 8]となった場合は、pazbqrcs となり、a と p が入れ替わることになる
色毎の要素を抽出し、目的の操作 (巡回) を行う
- for文を用いて、辞書型のcolorsのkey, valueを取り出す。.items()をつけることにより、辞書型のkey, valueの両方に同時にアクセスできる (カウンタ変数は省略してk,v としている)
  - スライスを用いて、取り出したリストを巡回させ rotation_v とする
    - v[-1]でリストの最後の要素(値) -> 配列にするため[ ]を追加
      ＊値のままだと + のところでエラーが出るため注意＊
    - v[:-1]でリストの最後の要素を配列
    - 配列同士にしたため + で配列の組み合わせを行う
  - zipを用いて、配列 v と配列 rotation_v からそれぞれ要素を順番に取り出す
    - 文字列のインデックス番号の配列 s_Num を更新していく
      - s_Num[i] = j は、i番目の文字を選択をそのインデックス番号を j とする
s_Numの順番に文字順、各要素にSのインデックス番号が示されているため、for文でひとつづつ取り出していく。ただし、s_Num[0]はダミーであるので、この部分は飛ばす
- print()文のend=””を用いることにより改行を入れずに文字列を準備つなげる
- for文を抜けた後に最後に改行を追加する（解答形式合わせ）