ABC212 A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け

ABC212(AtCoder Beginner Contest 212)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下

A - Alloy

入力を受け取り、問題文に書いている条件のとおりに答えを出力できるようif文を書けば良いです。
pythonでは0に等しいとする時「A=0」ではなく「A==0」と2つイコールを書くことに注意してください。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

# 入力の受け取り
A,B=map(int, input().split())

# 0<AかつB=0 純金
if 0<A and B==0:print("Gold")
# A=0かつ0<B 純銀
elif A==0 and 0<B:print("Silver")
# 0<Aかつ0<B 合金
elif 0<A and 0<B:print("Alloy")

B - Weak Password

文字列を受け取って
・4桁とも同じ数字でないか？
・右隣の番号(Xiの隣=Xi+1)が次の数字になっていないか？
を確認します。
どちらかに該当すればWeak、そうでないならばStrongです。

・4桁とも同じ数字でないか？
X1==X2、X2==X3、X3==X4をandで並べればOKです。

・右隣の番号(Xiの隣=Xi+1)が次の数字になっていないか？
受け取りを文字列にしているのでまずint(X)で数値に変換します。その後+1すればOKです。
ただし9の次(=10)は0としたいです。これは10で割った余り(%10)を取ることで変換できます。
1%10=1
2%10=2
...
9%10=9
10%10=0
といい感じに変換できます。

# 文字列として受け取り
S=input()

# 1文字ずつに分解
X1=S[0]
X2=S[1]
X3=S[2]
X4=S[3]

# 4桁とも同じ数字でないか？
if X1==X2 and X2==X3 and X3==X4:
    # 答えの出力
    print("Weak")
    # 途中で終了するときはexit()
    exit()

# 右隣の番号(Xiの隣=Xi+1)が次の数字になっていないか？
# int(X1)+1：文字列→数値に変換して+1
# %10：9の次の数字を0にするため
if (int(X1)+1)%10==int(X2) and (int(X2)+1)%10==int(X3) and (int(X3)+1)%10==int(X4):
    # 答えの出力
    print("Weak")
    # 途中で終了するときはexit()
    exit()

# 2つの条件に該当しなければStrong
print("Strong")

C - Min Difference

ソートした後A、Bの要素を順に見ていきます。

i=0,j=0としてスタートします。
(1)|A[i]-B[j]|を計算し、暫定答えとします
(2)A[i]とB[j]を比較します
・A[i]<B[j]ならば、iをプラス1します(A側を進めます)
・A[j]>B[i]ならば、jをプラス1します(B側を進めます)
・A[j]=B[i]ならば、答えは0です

(1)~(2)をi,jが最後の要素に来るまで繰り返すことで最終的な答えが出ます。

具体例で考えましょう。
ソートした後のA,Bが以下だったとします。
A: 1 6 8 15 20 30
B: 4 5 7 10 16 25

(1)|A[i]-B[j]|を計算し、暫定答えとします
|A[0]-B[0]|を計算します。
|A[0]-B[0]|=|1-4|=3です。
暫定答えを3とします。

(2)A[i]とB[j]を比較します
A[0]とB[0]を比較します。
A[0]<B[0](1<4)のため、iにプラス1します(A側を進めます)

【なぜこの操作で答えが出るか？】
|A[0]-B[1]|を計算する意味はありません。B[0]<B[1]のため、|A[0]-B[0]|<|A[0]-B[1]|となるからです。
同様に|A[0]-B[2]|,|A[0]-B[3]|,...も|A[0]-B[0]|より大きいので答えになりえません。
ゆえに|A[0]-B[?]|はもう考える必要がなく、次の|A[1]-B[?]|へ進んでも良いというわけです。

(1)|A[i]-B[j]|を計算し、暫定答えとします
|A[1]-B[0]|を計算します。
|A[1]-B[0]|=|6-4|=2です。
暫定答えだった3より小さいので暫定答えを2に更新します。

(2)A[i]とB[j]を比較します
A[1]とB[0]を比較します。
A[1]>B[0](6>4)のためjにプラス1します(B側を次に進めます)

(1)|A[i]-B[j]|を計算し、暫定答えとします
|A[1]-B[1]|を計算します。
|A[1]-B[1]|=|6-5|=1です。
暫定答えだった2より小さいので暫定答えを1に更新します。

(2)A[i]とB[j]を比較します
A[1]とB[1]を比較します。
A[1]>B[1](6>5)のためjにプラス1します(B側を次に進めます)

...
以上を最後まで(i,jがN,Mを超えるまで)繰り返すことで答えが得られます。

# 入力の受け取り
N,M=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))

# A,Bをソート
A.sort()
B.sort()

# i：Aのインデックス番号
# j：Bのインデックス番号
i=0
j=0

# 答え(最小を取るので最初はバカでかい数)
ans=10**20

 # i<N,j<Mの範囲で
while i<N and j<M:
    # |A[i]-B[j]|を計算、今までの答えより小さければ答えを更新
    ans=min(ans,abs(A[i]-B[j]))

    # もしA[i]<B[j]ならば
    if A[i]<B[j]:
        # Aを次へ
        i+=1
    # もしB[j]<A[i]ならば
    elif B[j]<A[i]:
        # Bを次へ
        j+=1
    # もしA[i]=B[j]ならば
    else:
        # 答えは0
        print(0)
        # 終了
        exit()

# 答えの出力
print(ans)

D - Querying Multiset

この問題ではまずheapの知識が必要です。
heapはリストから最小値をO(logN)で取り出せるデータ構造です。

使い方はリストを用意してheap化するだけ。
heappush(リスト,要素)で要素の追加
heappop(リスト)で最小値の取り出し

# まずインポート
import heapq

# リストを用意
que=list()

# heapify(リスト)でheap化：O(N)
heapq.heapify(que)

# heappush(リスト,要素)でheapのリストに要素を追加：O(logN)
heapq.heappush(que, 6)
heapq.heappush(que, 1)
heapq.heappush(que, 3)
heapq.heappush(que, 11)

# heappop(リスト)で最小値の取り出し(取り出した要素は消される)：O(logN)
x1=heapq.heappop(que)
x2=heapq.heappop(que)
x3=heapq.heappop(que)

print(x1)
print(x2)
print(x3)

以上のコードをコピペして実行すると
1
3
6
と小さい順に取り出されたのがわかります。

では問題を考えましょう。

操作2が来たとき、問題文そのままに袋の中の全てのボール(要素)へXiを加算していると、袋の中のボールが多い場合にTLEします。工夫が必要です。

次のように考えます。
操作1：「Xi-(今までの操作2で加算された数)」と書いたボールを入れる
操作2：加算した数を記録する。
操作3：「取り出したボールに書いている数+操作1でマイナスされた数+そのボールに操作2で加算された数」を出力する。

つまり操作2でわざわざ全部のボールにXiを加算せずとも、
・i番目の操作でXiを加算した
・このボールは?番目の操作で入れた
という情報だけ持っておけばボールを入れてから取り出すまでに何が加算されているかわかるので、ボールを取り出してから計算すればよいわけです。
さらに最小値を取り出すため、袋に入れる前に他のボールに足された数=(今までの操作2で加算された数)を引く、という処理を操作1で行います。

具体例で考えましょう。

「入力例」
5
1 3
2 10
1 5
2 2
3

まず「i番目に加算した数」を記録するplusというリストを用意します。
0番目に加算した数はありませんからplus[0]=0です。

query1：1 3
3と書いたボールを袋に入れます(heap化したリストへ入れます)
このときついでに何番目の操作で入れたボールなのかも記録します(「3」は1番目の操作で入れた)
「0を袋の中のボールへ加算した」と考え、plus[1]＝0とします。
plus=[0,0]

query2：2 10
袋の中のボールへ加算する代わりにplus[2]=10とします。
plus=[0,0,10]

query3：1 5
5と書いたボールを袋に入れる、のですが袋の中に入れる前にこれまでに足された数を引きます。
これまでに足された数はplusの要素の総和です。すなわち10です。
ゆえに5-10=-5とボールへ書いて袋にいれます。
ついでに何番目の操作で入れたボールなのかも記録します(「-5」は3番目の操作で入れた)
さらになにをマイナスしたかも記録します(-5は10引かれた)
plusの処理もやります。「0を袋の中のボールへ加算した」と考え、plus[3]＝0とします。
plus=[0,0,10,0]

query4：2 2
袋の中のボールへ加算する代わりにplus[4]=2とします。
plus=[0,0,10,0,2]

query5：3
一番小さい数の書かれたボールを取り出します。
先にplusの処理を済ませましょう。
「0を袋の中のボールへ加算した」と考え、plus[5]＝0とします。
plus=[0,0,10,0,2,0]
今入っているボールは「3」,「-5」ですから「-5」を取り出します。
「-5」は「3番目の操作で入れた」ことと「10引かれた」ことが記録されています。
「10引かれた」のでまず10足してもとの数に戻します(-5+10=5)
さらに「3番目の操作で入れた」わけですから3～5番目の操作の間に操作2で足されたものもプラスしてあげましょう。
つまりplus[3]～plus[5]の総和です。(5+(0+2+0)=7)
最終的に7を出力します

と、これで解けるかというとまだ解けず。
query5でしれっとplus[3]～plus[5]の総和ですなんて言っていますが総和の計算は欲しい長さぶんだけ計算が必要です。TLEしてしまいます。

ですのでplus[i]~plus[i+k]までの総和を高速で求める方法を考えます。
ここで累積和というテクニックを使います。

たとえば
plus=[0,3,5,7,9,11]の場合、
先に「iまでの累積和」=「plus[0]~plus[i]までの和」を作っておきます。名前はruisekiとしましょう。
ruiseki=[0,3,8,15,24,35]
plus[2]~plus[5](plus[2]+plus[3]+plus[4]+plus[5])までの和を取り出したいときはruiseki[5]-ruiseki[1]を計算すればよいです。
ruiseki[5]-ruiseki[1]=(plus[0]+plus[1]+plus[2]+plus[3]+plus[4]+plus[5])-(plus[0]+plus[1])
となるのでめちゃくちゃいい感じに消えてくれるわけですね。
実際の数字を当てはめると
35-3=(0+3+5+7+9+11)-(0+3)=32
こんな感じです。

累積和の計算は以下のようにできます。
ruiseki[i]=ruiseki[i-1]+plus[i]
i-1番目の累積和+plus[i]を繰り返していけば勝手にできてるわけですね。

# 入力の受け取り
Q=int(input())

# heapqを使う準備
import heapq

# リスト(袋)を用意
que=list()

# 加算する要素
plus=[0]*(Q+1)

# plusの累積和計算用
ruiseki=[0]*(Q+1)

for i in range(1,Q+1):
    # 入力の受け取り(要素数が操作1,2と3で違うからとりあえずリストで受け取る)
    query=list(map(int, input().split()))

    # 操作1
    if query[0]==1:
        X=query[1]
        # 今まで加算された数=累積和のi-1番目を引く
        minus=ruiseki[i-1]
        # queへ格納[Xi-今まで加算された数,i番目の操作でボールを入れた,Xiから引いた数]
        heapq.heappush(que,[X-minus,i,minus])
        # 袋の中のボールへ「0」を足したと考える
        plus[i]=0
        # 累積和の追加
        ruiseki[i]=ruiseki[i-1]+plus[i]

    # 操作2
    elif query[0]==2:
        X=query[1]
        # 袋の中のボールへ「X」を足した
        plus[i]=X
        # 累積和の追加
        ruiseki[i]=ruiseki[i-1]+plus[i]

    else:
        # num：取り出したボールに書いている数
        # indx：そのボールを入れた操作はindx番目
        # minus：ボールを入れるときに引かれた数はminus
        num,indx,minus=heapq.heappop(que)
        # 袋の中のボールへ「0」を足したと考える
        plus[i]=0
        # 累積和の追加
        ruiseki[i]=ruiseki[i-1]+plus[i]
        # ad：ボールを入れてから(indx番目の操作から)加算された数を累積和で計算(plus[i]~plus[indx+1]までの和)
        ad=ruiseki[i]-ruiseki[indx]
        # (取り出したボールに書いている数+操作1でマイナスされた数+操作2で加算された数)
        print(num+minus+ad)

【広告】

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

1～24問目まではサンプルとして無料公開しています

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。

【kindle】

【booth(pdf】