Atcoder 灰diff埋め ABC120C~145C 振り返り

ABC120 C - Unification【AC】

　無駄にテクニカルな解法で解いたけれど，解説でよりシンプルな方法に気付いたパターンです．
　cou[0]=赤色のボールの数，cou[1]=青色のボールの数とします．Sの左から順にボールを入れていき，ボールの数に合わせcouの値を上下させます．ボールを入れたことでボールが消えるパターンを考えます．異なる色のボールが一つでも存在したら，入れるボールと異なる色のボールが1つ必ず消えます．
　異なる色のボールをプログラムで，s^1と表現しました．sはボールの色を表す0か1です．^はxorを表す演算子で0^1=1, 1^1=0となります．右項を1にすれば，s^1はsを反転した値が返ってくることが分かります．これで，異なる色のボールを表せられます．

S = map(int, list(input()))
cou = [0, 0]
ans = 0

for s in S:
    if cou[s^1] != 0:
        ans += 2
        cou[s^1] -= 1
    else:
        cou[s] += 1

print(ans)

　しかし，そもそも最終的に筒には1種類のボールしか残らないので，少ない方の色のボールは全て消え，その個数分多い方のボールも消えるので2*min(赤色のボールの個数, 青色のボールの個数)とすれば良いです．

S = input()
print(2*min(S.count("0"), S.count("1")))

ABC141 C - Attack Survival【AC】

　逆から考える事で解けるようになる問題です．問題に書いてあるとおり，正解した人以外のポイントを-1するという方法で解くと，正解者以外の値を-1する必要があるので一問ごとにO(N)の時間が掛かり，問題がQ個あるのでO(NQ)となり間に合いません．
　今回は，正解者以外の値を-1する工程がボトルネックとなっているので，ここをなんとかすることを考えます．正解者以外の値を操作しようとするとO(N)ですが，正解者のみの値を操作するのならO(1)です．
　まず始めに全員が全ての問題で不正解だったと仮定します．するとポイントはK-Qとなります．ここから，正解者のみに値を+1します．そして，最終的に値が1以上なら勝ち抜けたと分かります．
　処理を逆から考える事で計算量を削減できることがある事が分かります．

N, K, Q = map(int, input().split())
A = [K-Q for _ in range(N)]
for _ in range(Q):
    A[int(input())-1] += 1

for a in A:
    if a > 0:
        print("Yes")
    else:
        print("No")