くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 141 C - Attack Survival

Python3で解く AtCoder Beginner Contest 141 C - Attack Survival

AtCoder カウンター クエリ処理 ABC-C

カウントした値を持ってからクエリを処理する系っていうパターン。 別の方法もある。先に持ち点から全クエリ分引き算しておいて正解したら足す。

概要

問題
・最初の時点で全員{\displaystyle K}ポイントもっている。
・{\displaystyle Q}回クイズを行って、{\displaystyle i}回目に正解した{\displaystyle A_i}以外のポイントが1ずつ減少
・クイズが終わったとき、ポイントが 1以上残っているかどうかを判定

解くときに考えた内容

愚直にやると、 {\displaystyle N-1}人分{\displaystyle Q}回処理があるので{\displaystyle O(NQ)}

要するに各人のマイナスポイントさえわかれば、{\displaystyle K}から引けばいい。マイナスポイントは、

{\displaystyle - Q + A_i}が正解した数

誰が何回正解したかをカウントする。そこで、
{\displaystyle A_i}から{\displaystyle A_N}について、

{\displaystyle 0} < {\displaystyle K - Q + A_i}が正解した数 を計算して判定すればいい。

自分は思いつかなかったが、どちらにカッコをつけるかで、イメージが変わる。 {\displaystyle K - Q }として後から正解者に1ポイント足していくというのでも同じ。

コード

from collections import Counter

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]
a_c = Counter(a)
for i in range(1, n+1):
    if 0 < k + a_c.get(i, 0) - q:
        print('Yes')
    else:
        print('No')
# そもそも全員からq引いて、当たった人に1足すってやればよかった...
# n, k, q = map(int, input().split())
# l = [k-q] * n 
# for i in range(q):
#     a = int(input())
#     l[a-1] += 1
# for i in range(n):
#     if l[i] > 0:
#         print('Yes')
#     else:
#         print('No')