ABC210のA,B,C問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

シンプル：余計なことを考えずに済む
実装が楽：ミスやバグが減ってうれしい
時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo

よかったらLGTMしていただけると、私のやる気がでます！

ABC210 まとめ

全提出人数: 8876人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB----	300	22分	6435(6211)位
400	AB----	300	8分	5251(5027)位
600	ABC---	600	74分	4292(4073)位
800	ABC---	600	40分	3324(3105)位
1000	ABC---	600	23分	2441(2224)位
1200	ABC---	600	13分	1725(1508)位
1400	ABCD--	1000	100分	1182(978)位
1600	ABC-E-	1100	126分	792(598)位
1800	ABCDE-	1500	123分	514(341)位
2000	ABCDE-	1500	76分	318(180)位
2200	ABCDE-	1500	56分	191(88)位
2400	ABCDE-	1500	41分	113(40)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	4044	91.1 %	89.4 %	28.4 %	1.0 %	0.5 %	0.0 %
茶	1517	99.0 %	99.1 %	74.4 %	4.6 %	1.5 %	0.1 %
緑	1150	99.5 %	99.7 %	95.0 %	13.7 %	6.9 %	0.0 %
水	700	99.6 %	99.7 %	98.4 %	39.1 %	29.4 %	0.3 %
青	355	100.0 %	100.0 %	99.7 %	70.1 %	75.5 %	4.5 %
黄	178	93.3 %	93.3 %	92.7 %	80.3 %	86.0 %	8.4 %
橙	36	91.7 %	97.2 %	91.7 %	88.9 %	91.7 %	36.1 %
赤	15	100.0 %	100.0 %	100.0 %	93.3 %	93.3 %	86.7 %

※表示レート、灰に初参加者は含めず

A問題『Cabbages』

問題ページ：A - Cabbages
灰コーダー正解率：91.1 %
茶コーダー正解率：99.0 %
緑コーダー正解率：99.5 %

考察

買うキャベツがA個以下の場合

$N$ 個のキャベツすべてが $X$ 円なので、$N\times{X}$ 円です。

買うキャベツがA個より多い場合

$A$ 個のキャベツが $X$ 円で、$N - A$ 個のキャベツが $Y$ 円です。

つまり、$A\times{X} + (N-A)\times{Y}$ 円です。

コード

def main():
    N, A, X, Y = map(int, input().split())
    if N <= A:
        ans = N * X
    else:
        ans = A * X + (N - A) * Y
    print(ans)


if __name__ == '__main__':
    main()

B問題『Bouzu Mekuri』

問題ページ：B - Bouzu Mekuri
灰コーダー正解率：89.4 %
茶コーダー正解率：99.1 %
緑コーダー正解率：99.7 %

考察

問題文に『山札には少なくとも $1$ 枚の悪いカードが含まれていることが保証されます。』とあるので、悪いカード1は必ず存在します。

山札の上から順番にめくっていって、先に悪いカードを引いた人が負けなので、『一番はじめに出てくる悪いカード』が上から何枚目かわかればいいです。言い換えると、二番目以降の悪いカードは何番目だろうとどうでもいいです。

Pythonのインデックスが $0$ からはじまるのに合わせて、山札の一番上のカードを $0$ 番目ということにします。『一番はじめに出てくる悪いカード』が $0,2,4,6,\dots$ 番目ならば高橋君が負けで、$1,3,5,7,\dots$ 番目なら青木君が負けです。

実装

forループで最初に '1' が出るのが何番目か探してもいいですが、S.index('1')と書いたほうが楽です。一番はじめに'1'が出現するインデックスがいくつか返してくれます。

コード

def main():
    N = int(input())
    S = input()
    x = S.index('1')  # はじめに'1'が出現するインデックス
    print('Takahashi' if x % 2 == 0 else 'Aoki')  # 負ける人を答えるのに注意


if __name__ == '__main__':
    main()

C問題『Colorful Candies』

問題ページ：C - Colorful Candies
灰コーダー正解率：28.4 %
茶コーダー正解率：74.4 %
緑コーダー正解率：95.0 %

考察

素直にやるとTLEになる

$1$ ～ $K$ 番目の種類数、$2$ ～ $K+1$ 番目の種類数、$3$ ～ $K + 2$ 番目の種類数……を素直に求めようとすると、下のようなコードになりますが、この方法はTLEになります。

def main():
    N, K = map(int, input().split())
    C = list(map(int, input().split()))
    ans = 0
    for i in range(N - K + 1):
        L = C[i:i + K]
        score = len(set(L))
        ans = max(ans, score)
    print(ans)


if __name__ == '__main__':
    main()

$N - K + 1$ 個の長さ $K$ の配列1つの種類数を求めるのに $O(K)$ かけているので、全体の計算量は $O(NK)$ です。$K\le{N}\le{3\times10^5}$ の制約では間に合いません。

前回の結果を使いまわして高速化する

たとえば、$K=3$ のとき、$1$ ～ $3$ 番目のキャンディと $2$ ～ $4$ 番目のキャンディには、どちらにも $2,3$ 番目のキャンディが含まれていて、左端の $1$ 番目、右端の $4$ 番目のキャンディが含まれているかいないかだけが違います。

ここで、どの色のキャンディがいくつあるかを数えます。『1個右の区間』に行くときは

一番左の色のキャンディを1個捨てる
右の色のキャンディを1個増やす

の2つの操作をすればいいです。

この操作で、0個になったキャンディがあれば種類数を1減らして、0個から1個になったキャンディがあれば種類数を1増やせばいいです。（種類数の管理を自力で実装する必要はなく、標準ライブラリを活用すれば簡単にできます）

実装

キャンディの色は最大で $10^9$ 種類あります。長さが $10^9$ のリストで管理しようとすると、MLE（メモリ上限超過）になります。

そこで、collections モジュールのCounter を使います。存在する要素だけを管理できるので、メモリの問題はなくなります。

さらに、len(counter) で、含まれているKeyの数（≒種類数）を $O(1)$ で求めることができます。ただし、ある色のキャンディの個数が $0$ 個でも、Keyとして含まれていれば len(counter) で数えられてしまいます。個数が $0$ 個になった色のキャンディーはdelを使って削除する必要があります。（説明が若干雑な気もしますが、コードを読んでください）

コード

def main():
    from collections import Counter

    N, K = map(int, input().split())
    C = list(map(int, input().split()))
    counter = Counter(C[:K])  # 最初のK個はループせずにこれでいいです
    ans = len(counter)  # 最初のK個の種類数
    for i in range(K, N):
        left = C[i - K]  #  1回目が K - K = 0（一番左）になるようにします
        right = C[i]
        counter[left] -= 1
        counter[right] += 1
        if counter[left] == 0:
            del counter[left]  # 0個でもlenで数えられてしまうので、delで消します
        ans = max(ans, len(counter))  #  現在の種類数で答えを更新します
    print(ans)


if __name__ == '__main__':
    main()

【AtCoder解説】PythonでABC210のA,B,C問題を制する！

目次

アプリ AtCoderFacts を開発しています