前回のABC209はD問題まで解けて、少しレートを取り戻しました。
前回のD問題が解けたのは、競プロ典型90問のおかげでした。
ABC210の開催された2021/7/17午前中は、時間を見つけて、競プロ典型90問を解き進めていました。
今回も精進結果が現れると良いな。と思いつつ参加したABC210の参加記録です。
Python3を使用している茶色コーダーです。
AからCまでのACコード付きでABC210を振り返ります。
A – Cabbages
標準入出力と条件分岐、またはfor文などによるシミュレーションが出来るかを問われる問題。
A個まではX円、A個より多い場合はY円でN個買うのに必要な値段を出力する問題ですね。
NとAの大小関係で条件分岐させればOKです。
NがA以下の場合は、N*Xが答えになます。NがAよりも大きい場合は、A個までがX円で、それよりも多い部分はY円かかるので、そられを足し合わせた数を出力すればOKですね。
# AtCoder Beginner Contest 210
# A - Cabbages
N,A,X,Y=map(int,input().split())
if N<=A:
print(N*X)
else:
print((A*X)+(N-A)*Y)
私は、コンテスト中はfor文でシミュレーションして提出しました。
N,A,X,Y=map(int,input().split())
ans=0
for i in range (1,N+1):
if i<=A:
ans+=X
else:
ans+=Y
print(ans)
B – Bouzu Mekuri
繰り返し処理と偶奇の条件判定が出来るかが問われる問題。
文字列Sを左から見ていって、はじめに’1’が出てくる時に、高橋君のターンか青木君のターンかを判定すればOKですね。
どちらのターンかを判定するのには、カウンタ変数のように使っている i の偶奇がわかれば判定できます。
# AtCoder Beginner Contest 210
# B - Bouzu Mekuri
N=int(input())
S=input()
for i in range (N):
if S[i]=='1':
if i%2==0:
print("Takahashi")
break
else:
print("Aoki")
break
はじめに出てきた悪いカードで勝敗がつくので、敗者の出力が終わったらプログラムを終了させないとWAになります。
上記のコードの場合は、breakでもexit()でも結果は変わらないです。
そのほかの方法としては、Python3の index()
を利用して、一番左にある ‘1’ のインデックスを取得する方法もありますね。
N=int(input())
S=input()
i=S.index('1')
print("Takahashi") if i%2==0 else print("Aoki")
慣れていないうちは、Sを文字列として受け取ること、判定に ‘1’ とstr型として判定することも、注意が必要かもしれないです。
C – Colorful Candies
問題の特性を理解して、計算量を意識したコードが書けるかを問われる問題。
私はキューを扱えるかが問われる問題。として解きました。
この記事の冒頭、競プロ典型90問の話を出しましたが、午前に解いた問題が、まさにこの問題の類題でした。(034 – There are few types of elements(★4))
この典型90の問題は尺取り法が想定解法なのですが、尺取り法については、この記事で紹介されている方法が、非常にわかりやすかったです。
以下、この問題を解く、方針です。
用意するデータは3種類
- 見ている区間を保持するdeque
- 見ている区間の各色のキャンディの数を保持するdict
- 見ている区間のキャンディの種類を保持するset
1.キューの長さがK未満の場合は、C[ i ] をキューに追加( append()
)する。
2.キューの長さがK以上になったら、キューの左から値を取り出し( popleft()
)、C[ i ] をキューに追加( append()
)する。
3.追加するときは、keyがC[ i ] の値を+1する。keyエラーになる場合もあるため、key in dict で False の場合は、新しい key ,value の値を設定する。
また、setにも色を追加する。
4.取り出す際は、key が C[ i ] の値を-1する。その結果、value が 0 になる場合は、set から C[ i ] を取り除く( discard()
)。
5.操作後に、今までの最高値と、setの長さを比べて、答えを更新していく。
# AtCoder Beginner Contest 210
# C - Colorful Candies
from collections import deque
N,K=map(int,input().split())
C=list(map(int,input().split()))
q=deque()
s=set()
ans=0
dic=dict()
for i in range (N):
if len(q)<K:
q.append(C[i])
s.add(C[i])
if C[i] in dic:
dic[C[i]]=dic[C[i]]+1
else:
dic[C[i]]=1
else:
p=q.popleft()
dic[p]=dic[p]-1
if dic[p]==0:
s.discard(p)
if C[i] in dic:
dic[C[i]]=dic[C[i]]+1
else:
dic[C[i]]=1
q.append(C[i])
s.add(C[i])
ans=max(ans,len(s))
print(ans)
コメント