ABC210参戦記

前回の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)