【python】100日後に緑コーダーになるためのABC212 C,D問題【7日目】

はじめに

100日後に緑コーダーになるためにAtcoder Beginner Contest212の解説を行います。
今回はC,D問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。

対象読者

灰・茶コーダー

C - Min Difference

https://atcoder.jp/contests/abc212/tasks/abc212_c

解法

近い値を二分探索

出題者の意図

二分探索が使えるか
答えが与えられた配列の順序に依らないことに気付くか

考察

Bの配列から使用する値を取り出して、その配列との差が最も小さくなる値をAから選ぶ必要がある。
Aを昇順にソートした後に二分探索を使って最適な値を探索。
ただし、二分探索で取得したインデックスが0の時とNの時で場合分けが必要

コード

from bisect import bisect_left

N,M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort()
ans = pow(10,9)
for b in B:
    idx = bisect_left(A, b)
    if idx == 0:
        ans = min(ans,abs(A[idx]-b))
    elif idx == N:
        ans = min(ans,abs(A[idx-1]-b))
    else:
        ans = min(ans,abs(A[idx]-b),abs(A[idx-1]-b))
print(ans)

D - Querying Multiset

https://atcoder.jp/contests/abc212/tasks/abc212_d

解法

ボールを優先度付きキューで管理

出題者の意図

優先度付きキューが使えるか
リスト全体に処理するのではなく、クエリごとに足し算と引き算することを思いつけるか

考察

最小値を取り出していくので優先度付きキューを使うことはわかる。
問題はクエリ2のリスト全体に加算する操作をどうするか。
ここでは発想を変えてクエリ3で答えを出すときに、いままでクエリ2の加算分を足して出力することを考えてみる。
そうすると優先度付きが保てるように、途中にクエリ1でリストにボールを追加するときに加算分を引き算したらよい。

from heapq import heappop, heappush

Q = int(input())

ball = []
cnt = 0
for i in range(Q):
    query = list(map(int,input().split()))
    p = query[0]
    if p == 1:
        x = query[1]
        heappush(ball,x-cnt)
    elif p == 2:
        x = query[1]
        cnt += x
    else:
        print(heappop(ball)+cnt)