Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

【競プロ練習】AtCoder Beginner Contest 171をやってみた

AtCoder Beginner Contest 171に参加しました。
初めての競技プログラミングコンテスト参加です。

3完、D問題は実行時間の壁に阻まれ、Eも実装しましたがTLE今見直すとなんとも言えないコードで恥ずかしい……

A - Alphabet

#Alphabet
S = input()
if S in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
    print('A')
else:
    print('a')

アルファベット一文字の入力に対し、大文字or小文字を返す問題。
ASCIIコードなどから判定できればよかったのですが、そういうことをPythonで実装したことがなかったので、ご覧のとおり無理やり解答しました。

B - Mix Juice

#Mix Juice
N, K = list(map(int, input().split()))
P = sorted(map(int, input().split()))
print(sum(P[0:K]))

N種類の果物それぞれの価格が与えられ、K種類の果物1つづつ購入したときの最低価格を求める。

N種類の価格をソートし小さい方からK個の合計値として解答。

C - One Quadrillion and One Dalmatians

#One Quadrillion and One Dalmatians
alphabet = list('abcdefghijklmnopqrstuvwxyz')
N = int(input())-1

def shin26(N):
    if(int(N/26)!=0):
        return(shin26(int(N/26)-1)+alphabet[N%26])
    return alphabet[N%26]

print(shin26(N))

EXCELの列番号みたいに入力にたいし、A〜Z,AA〜AZ,BA~...を返す問題(答えは小文字)。
N進数を求める再帰関数をa~zの文字列を返すように変更して制作しました。
ここでもa~zのlistを作成することで、listのアドレスを与えることでアルファベットを入手できるようにしています。

このあとに、Python上で切り捨て割算の演算子「//」を知りました。(int と割算演算子を組み合わせる必要はなかった)

D - Replacing

###失敗###
#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())

for i in range(Q):
    B, C = list(map(int, input().split()))
    CC = A==B
    NC = CC==False
    A = A*(NC) + C*CC
    print(A.sum())

D問題は時間内にできませんでした。ある配列Aが与えられ、BをCに置き換えることを繰り返しそのたびにAの合計値を出力する問題。
最初は愚直に置換してましたが、実行時間超過であえなく撃沈。

終了直後に配列内のBの個数さえわかれば、直前の合計値と差分を求められるとアドバイスをいただきました(ありがとうございます!!)

###失敗###
#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    if B in u:
        posB = np.where(u==B)
        asum += int(count[posB]) * (C-B)
        # print(u)
        # print(count)
        if not (C in u):
            u[posB] = C
        else :
            posC = np.where(u==C)
            count[posC] += count[posB]
            u = np.delete(u,posB)
            count = np.delete(count,posB)
    print(asum)

配列Aをある数uがcount個あるという配列に変換。
BからCに変えるときはその数を変更、統合できれば統合という方針で行いました(出力は前述のように差分から求める)が、こちらもあえなく撃沈。

listの検索は遅い

知ってた……。Python上でfor文回すこと遅いです(いつもはfor文回す計算があれば行列演算に置き換えてnumpyで回しています)。
さらにいうと、C++使いの知り合いも同じ方法では実行時間超過を食らっていました。

B→Cの変換ツリーを作って最後に適用する案

各変換ごとに出力が必要なので不可能。

結局は解説をチラ見して
「入力される整数はたかだか$10^5$なので$10^5$の配列を作りアドレス番地にその数字の個数を入れる」
確かにこれは、検索が必要ない!

ということで、以下の解答でACいただきました。

#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
L = np.zeros(10**5,int)
for i in range(len(u)):
    L[u[i]-1] = count[i]
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    asum += L[B-1] * (C-B)
    L[C-1] += L[B-1]
    L[B-1] = 0
    print(asum)

E - Red Scarf

###失敗###
#Red Scarf
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
output = ''

def binary(A, p):
    if not np.all(A==0) :
        return binary( (A-A%2)/2 , p+1 ) + ((A%2).sum())%2 * 2**p
    return ((A%2).sum())%2 * 2**p

for i in range(N):
    ken = (np.delete(A,i))
    output += str(int(binary(ken,0)))
    if i != N-1:
        output += ' '

print(output)

xorの知識がなかったのでbinaryで判定しました。終

2進数の各桁の1の個数で判定できるということだけは理解したのでこうしましたが、TLE。
知り合いに、すべての数値のxorを取って、そのあと自身の数値とxorとればできるというアドバイスで以下でACをいただきました。

#Red Scarf
N = int(input())
A = list(map(int, input().split()))
output = list()

axor = A[0]
for i in range(1,N):
    axor ^= A[i]

for i in range(N):
    output.append(axor^A[i])
print(*output)

appendのメソッドなど少し覚えた知識を加えました。

まとめ

F問題は手を付けられていません。次のABCではより多くの完答数を目指したいと過去問を解いて精進中です。いずれそのことも記事に起こしたい。。。

Octpascal
最近、競技プログラミングを初めました。 プログラミングは大学で研究のデータ処理のためにPythonを使っていました。 Verilog HDL, Spice は少しできます。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away