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

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

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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 306

A問題：Echo

A – Echo

問題(要約)

長さNの英小文字列Sがある。Sのi番目の文字をSiとしたときに、S₁, S₁, S₂, S₂, …, S_N, S_N を出力する

解答

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

# 番号2
for i in range(n):
    print(S[i],S[i],sep="",end="")

# 番号3
print()

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

print文を使って、一つの文字列を２回出力させる

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

入力n, Sを受け取る
for文を文字数回分 (n回) 繰り返す
- 一回のfor文に対して、S[i] を２回出力する
- print文で文字間と文字終わりを調整する
  - sep：文字間を調整。”” を入力することにより、空白をあけない
  - end：文字終わりを調整。”” を入力することにより、文字後の空白を入れない
atCoderの解答は、最後に空白行が必要なため、空白を追加する

B問題：Base 2

B – Base 2

問題(要約)

0 と 1 からなる長さ64の整数A=(A₀, A₁, …, A₆₃) が与えられる。

　A₀2⁰ + A₁2¹ + … + A₆₃2⁶³ を求める

解答

# 番号1
A=list(map(int,input().split()))

# 番号2
ans=0
for i in range(64):
    ans+=A[i]*2**i

# 番号3
print(ans)

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

for文でカウンタ変数を0〜63まで取り出し、ans変数に計算結果を足し合わせていく。

入力 A を受け取る (リスト形式)
計算過程を記憶するansを準備し、カウンタ変数を i とし、for文を64回繰り返す
- 変数 ans に、A_i x 2ⁱ、階乗はpythonでは ** を用いる
全ての組みが足し合わさったansを出力する

C問題：Centers

C – Centers

問題(要約)

1, 2, …, N がちょうど3回ずつ現れる長さ3Nの数列Aが与えられる。i = 1, 2, … , Nについて、Aの中にある i のうち真ん中にあるものの添字を f(i) と定める。1, 2, …, N を f(i) の昇順に並べる

解答

# 番号1
from collections import defaultdict

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

# 番号3
cnts=[0]*(n+1)
orders=defaultdict(int)

# 番号4
for i in range(3*n):
    cnts[A[i]]+=1
    if cnts[A[i]]==2:
        orders[A[i]]=i

# 番号5
for k,v in sorted(orders.items(), key=lambda x: x[1]):
    print(k,end=" ")

# 番号6
print()

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

各数 i が出てくる回数をカウントし、2回目に出てきた時の順番を i と共に辞書型を用いて記憶する

辞書型を2回目に出てきた順番でソートし、数 i をソート順により出力する

以下詳細

辞書型のdefaultdictを使用するため、インポートする
（dictとの違いは下記補足参照)
入力 n, A を受け取る
二つの変数を定義する
- cnts: 各数 i が出現した回数を数える。配列は 0 からなので n+1 分準備しておく
- orders: 各 i と位置を記憶するため、辞書型で準備する
配列Aを一つづつfor文を用いて確認していく。配列Aは3N分あるため、for文の回数は3Nに設定している
- それぞれの数が出てきた回数をcnts配列のインデックス番号に応じて増やしていく
- cntsのそれぞれの数が2になったときに、ordersに数とカウンタ変数 i を登録していく
sorted関数でordersのvalue (序数) の値で並び替えを行い、key (1, 2, …, N)の値を出力する
- sorted(orders.items(), key=lambda x: x[1]) 部分は、下記の操作を行なっている
  - 辞書のキーと値を扱いため、.items()を用いる
  - keyには並び順のキーを指定する。lambda関数を用いて辞書型のvalueを指定する
    ＊辞書型は辞書型のキー(左側の値)に基づいて登録されている。そのため、直接的に辞書型のvalue(右側の値)を指定することができない。それを回避するため、lambda関数を用いている
AtCoderの解答には最後に空白が必要なため、改行を行なっている
＊５番では、print関数のend=””を用いているための対応