【AtCoder】ABC210をPython3で解説

ABC210の解説。

A - Cabbages

解説

キャベツ1つ$x$円。
もし、キャベツを$A$個より多く買うとき、次から買うキャベツは$Y$円で買うことができる。

キャベツを$N$個買うとき、必要な金額はいくらかという問題。

問題文の通り実装すれば、ACできる。注意点は、もし$A$よりも多いとき、というところだ。

コード

n, a, x, y = map(int, input().split())

if n > a:
    print(x*a+(n-a)*y)
else:
    print(x*n)

B - Bouzu Mekuri

解説

問題の解釈をすると、文字列$S$のなかで先に$1$を出したほうの名前を出力するという問題。

文字列$S$を1文字ずつ確認していって、$1$が出たときに条件分岐。偶数番目なら、青木くんの負けなのでprint('Aoki')、奇数番目なら、高橋くんの負けなのでprint('Takahashi')を出力します。

コード

n = int(input())
slist = list(input())
cnt = 0

for s in slist:
    cnt += 1
    if s == '1':
        if cnt % 2 != 0:
            print('Takahashi')
        else:
            print('Aoki')
        break

C - Colorful Candies

解説

$N$個のキャンディーがそれぞれ$c$色になっている。連続した$K$個のキャンディーからとれる最大の色の種類数を取るという問題。

今回の注意点は、$K$と$N$の最大値が$3 \times 10^5$であるということ。つまり、計算量が$O(n^2)$となると、TLEしてしまう。したがって、これより少ない計算量で解かなければならない。

コードにおいて工夫した点は、dequeとdict()を使ったことだ。いわゆるしゃくとり法を用いた。
詳しくはこちらを御覧いただきたい。https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

先にコードを示す。

コード

# dequeをimport
from collections import deque

# input()
n, k = map(int, input().split())
clist = list(map(int, input().split()))

# 初期設定
dic = {}
cnt = 0
temp = deque()
keep = 0

for c in clist:
    temp.append(c)
    cnt += 1

    # もし辞書にcのkeyがなければ、1をカウント
    # あれば、数える
    if c not in dic:
        dic[c] = 1
    else:
        dic[c] += 1

    # keyの数を取得
    len_dic = len(dic)

    # もしkeyの数が今まで以上ならば、keepに保存
    if len_dic >= keep:
        keep = len_dic

    # tempの長さがk以上、つまり、連続する範囲を超えたなら、一番左にある古い値を取り除き、範囲外になったので、辞書のその値から1を引く
    if cnt >= k:
        t = temp.popleft()
        dic[t] -= 1
        # もしvalueが0になれば、そのまま残すと辞書のkeyの数としてカウントされてしまうので、辞書から取り除く
        if dic[t] == 0:
            dic.pop(t)

print(keep)

解説続き

連続する$K$個の色を見ていきたいので、それを保存する場所をつくる。これをキューを用いて実装する。なぜなら、キューにappend、popleftのそれぞれの操作は、計算量$O(1)$で実装できるからである。したがって、ループの中に入れても計算量を$O(n)$に保つことができる。

これと組み合わせて使うのが、dict()である。set(list())で長さを数えればいいじゃないか、という意見もあるが、list()をset()にする作業で計算量$O(n)$かかってしまう。したがって、キャンディーの色の種類の保存には、dict()を用いる。例えば、同じ色がキューにappendされたときに、辞書のkeyに当たる部分を探し出し、$+1$カウントしてあげるだけで良い。また、キューから値が出る、popleft()するときは、もし辞書のvalueが0担った場合、辞書のkeyを消してあげることで色の種類を数えることができる。

これをコードに起こしてあげると上記のようになる。詳しい解説は、コード内にコメントアウトしてあるので、そちらをみていただきたい。

編集後記

そろそろC問題で茶diff来そうだなー。