ABC210 A～C問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

ABC210(AtCoder Beginner Contest 210)　A～C問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

A - Cabbages

キャベツを買う個数が
・A個以下の場合
　NX円
・A個より多い場合
　AX+(N-A)Y円
となります。
これをそのままif文にして出力すればOKです。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
N,A,X,Y=map(int, input().split())

# 買う個数がA個以下の場合
if N<=A:
    # NX円を出力
    print(N*X)
# そうでない場合(買う個数がA個より多い場合)
else:
    # AX+(N-A)Y円を出力
    print(A*X+(N-A)*Y)

B - Bouzu Mekuri

for文を使ってSを1文字目から順に確認し、初めて0が出るのは何番目か確認します。

pythonではSの1文字目はS[0]、2文字目はS[1]、...と0始まりで1つずつずれます。
S[0],S[2],S[4],...など偶数番目が1だった場合は高橋くんが負け
S[1],S[3],S[5],...など奇数番目が1だった場合は青木くんが負け
となります。

注意点としてS[i]が1かの判定について
if S[i]==1:
と書くと失敗します。S[i]は文字列で、1は数値だからです。
if S[i]=="1":
と書いて1も文字列にしましょう。

【提出】

# 入力の受け取り
N=int(input())
S=input()

# i=0~N-1まで
for i in range(N):
    # Sのi文字目が1の場合
    if S[i]=="1":
        # iが偶数ならば
        if i%2==0:
            # Takahashiを出力
            print("Takahashi")
        # iが奇数ならば
        else:
            # Aokiを出力
            print("Aoki")
        # 終了
        exit()

C - Colorful Candies

cについて
0~K-1番目の色の種類数
1~K+1番目の色の種類数
2~K+2番目の色の種類数
...
を確かめていけば解けそうですが制約が大きいのでTLEします。

たとえば
K＝3
c：1 2 3 4 5
のとき、確認する範囲は図のようになります。

0~2番目が赤色の線
1~3番目が青色の線
2~4番目が黄色の線

まず赤色の線の部分(0~2番目)に色が何種類あるか確認します。

次に青色の線の部分(1~3番目)を確認するわけですが、このとき赤色の線の部分(0~2番目)から1が消え、代わりに4が入っただけで2,3は変わっていません。

同様に黄色の線の部分(2~4番目)は青色の線の部分(1~3番目)から2が消え、5が増えただけで3,4は変わりません。

つまり確認する範囲を右にずらしても変化するのは端の2つだけということです。
このやり方ならそれぞれの範囲の種類数の確認は端の2箇所だけで済むのでTLEしません。

具体的な手順は以下です。
○0~K-1番目までの色を確認する。このとき色iのキャンディがいくつあるかをdefaultdict(連想配列)で管理する。
　※defaultdict(連想配列)がわからない人は解説最後の「defaultdict(連想配列)について」を見てください。
　色iのキャンディの個数が0→1になったら(そこまでになかった色ならば)色の種類数をプラス1する。
i=1~N-Kまで
　(1)色c[i-1]の個数をマイナス1する
　(2)色c[i-1]の個数が1→0になったら(その色のキャンディがなくなったら)色の種類数をマイナス1する
　(3)色c[i+K-1]の個数をプラス1する
　(4)色c[i+K-1]の個数が0→1になったら(新しい色のキャンディならば)色の種類数をプラス1する
　(1)～(4)を行い、色の種類数が今までで一番大きければ答えを更新する。

具体例を見ましょう。
入力例1を使います。
7 3
1 2 1 2 3 3 1

まず0~2までの色数を確認します。
0番目：色1
　色1の個数：0→1
　色2の個数：0
　色3の個数：0
　色1が0→1となったので種類数をプラス1します。
　種類数：0→1
1番目：色2
　色1の個数：1
　色2の個数：0→1
　色3の個数：0
　色2が0→1となったので種類数をプラス1します。
　種類数：1→2
2番目：色1
　色1の個数：1→2
　色2の個数：1
　色3の個数：0
　種類数は増えません。
　種類数：2

次に1~3ですがここで変化するのは
0番目の色がなくなる
3番目の色が増える
だけです。この2つ分の情報だけ確認し、更新します。
0番目：色1
　色1の個数：2→1
　色2の個数：1
　色3の個数：0
　種類数：2
3番目：色2
　色1の個数：1
　色2の個数：1→2
　色3の個数：0
　種類数：2

2~4も同様に
1番目の色がなくなる
4番目の色が増える
だけです。この2つ分の情報だけ確認し、更新します。
1番目：色2
　色1の個数：1
　色2の個数：2→1
　色3の個数：0
　種類数：2
4番目：色3
　色1の個数：1
　色2の個数：1
　色3の個数：0→1
　色3が0→1となったので種類数をプラス1します。
　種類数：3

3~5も同様に
2番目の色がなくなる
5番目の色が増える
だけです。この2つ分の情報だけ確認し、更新します。
2番目：色1
　色1の個数：1→0
　色2の個数：1
　色3の個数：1
　色1が1→0となったので種類数をマイナス1します。
　種類数：3→2
5番目：色3
　色1の個数：0
　色2の個数：1
　色3の個数：1→2
　種類数：2

4～6も同様に
3番目の色がなくなる
6番目の色が増える
だけです。この2つ分の情報だけ確認し、更新します。
3番目：色2
　色1の個数：0
　色2の個数：1→0
　色3の個数：2
　色2が1→0となったので種類数をマイナス1します。
　種類数：2→1
6番目：色1
　色1の個数：0→1
　色2の個数：0
　色3の個数：2
　色1が0→1となったので種類数をプラス1します。
　種類数：1→2

種類数の最大値は2～4番目の3だったので3が答えです。

defaultdict(連想配列)について
この問題はそれぞれの色のキャンディが何個あるか管理しなければならないですが、リストで管理するとリストの大きさがキャンディの種類数=最大10^9となり、MLE(メモリ制限超過)します。
そこで連想配列を使います。これは色i：X個というような対応付を行えるデータ構造です。(辞書という言い方もします)
連想配列はdict()と書くことでも使えますがデフォルトの値(初期値)が設定できません。
そのためデフォルトの値を使える連想配列としてdefaultdictというものを使います。
書き方は以下です。

# defaultdictのインポート
from collections import defaultdict
# int:デフォルトの値を0にする
変数=defaultdict(int)

defaultdict(int)と書くことで初期値を0にできます。
あとは変数[キー]=値と書くことでキー(キャンディの色)に値(個数)を対応づけできます。
詳しく知りたい人は以下を参照してください。

【提出】

# 入力の受け取り
N,K=map(int, input().split())
c=list(map(int, input().split()))

# defaultdictのインポート
from collections import defaultdict
# int:デフォルトの値を0にする
colors=defaultdict(int)

# 色の種類数を数える変数
cnt=0

# i=0~K-1まで
for i in range(K):
    # c[i]の個数をプラス1
    colors[c[i]]+=1
    # c[i]の個数が0→1になったら
    if colors[c[i]]==1:
        # 色の種類数プラス1
        cnt+=1

# 答え　暫定答えをcntとする
ans=cnt

# i=1~N-Kまで
for i in range(1,N-K+1):
    # c[i-1]の個数をマイナス1
    colors[c[i-1]]-=1
    # c[i-1]の個数が1→0になったら
    if colors[c[i-1]]==0:
        # 色の種類数マイナス1
        cnt-=1
    # c[i+K-1]の個数をプラス1
    colors[c[i+K-1]]+=1
    # c[i+K-1]の個数が0→1になったら
    if colors[c[i+K-1]]==1:
        # 色の種類数プラス1
        cnt+=1
    # cntのほうが大きかったら答えを更新
    ans=max(ans,cnt)

# 答えの出力
print(ans)

【広告】

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

1～24問目まではサンプルとして無料公開しています

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。

【kindle】

【booth(pdf】