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

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

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

A - Good morning

・A<C→高橋くんのほうが早い
・C<A→青木くんのほうが早い
ということがわかります。

A=Cならば
・B≤D→高橋くんのほうが早い
・D<B→青木くんのほうが早い
となります。

AとCの比較、BとDの比較をifで行い、対応する結果を出力します。

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

【提出】

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

# A<Cならば
if A<C:
    # 「Takahashi」を出力
    print("Takahashi")

# C<Aならば
elif C<A:
    # 「Aoki」を出力
    print("Aoki")

# それ以外(A=C)
else:
    # B≤Dならば
    if B<=D:
        # 「Takahashi」を出力
        print("Takahashi")
    
    # そうでなければ(D<B)
    else:
        # 「Aoki」を出力
        print("Aoki")

B - Mex

0,1,2,...,2000について、順番にAに含まれるか確認していきます。
リストにxが含まれるか？　は
if x in (リスト):
と書きます。
含まれない場合はnotをつけて
if x not in (リスト):
となります。

【提出】

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

# x=0,1,2,...,2000
for x in range(2001):
    # xがAに含まれないならば
    if x not in A:
        # xを出力
        print(x)
        # 終了
        exit()

C - Choose Elements

DPで解きます。

DPとは「ある状態までの答えがわかっていれば→その次の状態の答えも出せる」という手続きを何度も行って最終的な答えを出す方法です。

DPの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。
https://www.youtube.com/watch?v=gVJ16ThsJYs

具体的な手順は以下です。
(1)表を作る
(2)すぐにわかるところを埋める
(3)表の小さい方から答えにたどり着くまで埋める
(4)答えを出力する

実装に合わせ、0インデックスで説明します。
すなわちA1=A[0],A2=A[1],...AN=A[N-1]とします。

例として以下のような入力を考えます。
N：5
K：3
A：1 6 3 7 2
B：2 3 9 5 5

(1)表を作る
各iについて「A[i]/B[i]をX[i]とできるか？」を表にします。
厳密に言うと「条件を満たすようなX[0]~X[i]までの数列を作る時、X[i]=A[i]/B[i]とすることは可能か？」となります。
表の名前はdpとします。

結論から先にいうとこの表は最後以下のようになります。

この○がついているところを適切な順番でたどるとXが作れます。
例えば
B[0]→B[1]→A[2]→B[3]→B[4]
の順にたどると
X：2 3 3 5 5
となります。

最後の列がA,Bともに「×」になっていればXは作れませんので、答えは「No」となります。

(2)すぐにわかるところを埋める
X[0]の部分はA[0],B[0]どちらでも良いので両方○になります。
よって
dp[A][0]=「○」
dp[B][0]=「○」
とします。

(3)表の小さい方から答えにたどり着くまで埋める
i=1の列を考えましょう。
まずdp[A][0]=「○」、dp[B][0]=「○」なのでX[0]にはA[0]=1またはB[0]=2が来ているはずです。
X[1]は|X[i]-X[i+1]|≤Kという条件より|X[0]-X[1]|≤3でなければなりません。

・X[0]=A[0]=1の場合
「A[1]を使えるか？」
　|X[0]-A[1]|=|A[0]-A[1]|=|1-6|=5となります。3<5なのでA[1]は使えません。
「B[1]を使えるか？」
　|X[0]-B[1]|=|A[0]-B[1]|=|1-3|=2となります。2≤3なのでB[1]は使えます。

・X[0]=B[0]=2の場合
「A[1]を使えるか？」
　|X[0]-A[1]|=|B[0]-A[1]|=|2-6|=4となります。3<4なのでA[1]は使えません。
「B[1]を使えるか？」
　|X[0]-B[1]|=|B[0]-B[1]|=|2-3|=1となります。1≤3なのでB[1]は使えます。

結局A[1]はどちらのパターンでも使えず、B[1]は使えるパターンがあるので
dp[A][1]=「×」
dp[B][1]=「○」
となります。

i=2の列を考えます。
dp[A][1]=「×」、dp[B][1]=「○」なのでX[1]には必ずB[1]=3が来ています

・X[1]=B[1]=3
「A[2]を使えるか？」
　|X[1]-A[2]|=|B[1]-A[2]|=|3-3|=0となります。0≤4なのでA[3]は使えます。
「B[2]を使えるか？」
　|X[1]-B[2]|=|B[1]-B[2]|=|3-9|=6となります。3<6なのでB[3]は使えません。

よって
dp[A][2]=「○」
dp[B][2]=「×」
となります。

これを一般に考えてみましょう。
dp[A/B][i+1]が「○」か「×」かを判断するにはdp[A/B][i]が○になっているか？差の絶対値はK以下か？を確認します。

i=0~(N-2)について
・dp[A][i]=「○」の場合
　|A[i]-A[i+1]|≤k→dp[A][i+1]=「○」
　|A[i]-B[i+1]|≤k→dp[B][i+1]=「○」
・dp[B][i]=「○」の場合
　|B[i]-A[i+1]|≤k→dp[A][i+1]=「○」
　|B[i]-B[i+1]|≤k→dp[B][i+1]=「○」

(4)答えを出力する
最後に答えを確認します。
dp[A][N-1]=「○」 または　dp[B][N-1]=「○」となっていれば「Yes」、両方「×」ならば「No」となります。

実装では表として二次元配列を作って埋めていきます。
dp[A][?],dp[B][?]というような書き方で解説をしていましたが実装ではA=0，B=1となるようにします。
例えばdp[A][2]はdp[0][2]と表現します。

「○」「×」はそれぞれ「True」「False」を入れます。最初は全て「False」にしておきます。

表の作り方は以下のように書きます。
dp=[[False]*N for i in range(2)]

二次元配列を作る時、dp[X][Y]としたいなら
配列名=[[初期値]*(Yの要素数) for i in range((Xの要素数)]
となる、と覚えておきましょう。

【提出】

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

# (1)表を作る
dp=[[False]*N for i in range(2)]

# (2)すぐにわかるところを埋める
# dp[A][0]=「○」,dp[B][0]=「○」
dp[0][0]=True
dp[1][0]=True

# (3)表の小さい方から答えにたどり着くまで埋める
# i=0~(N-2)
for i in range(N-1):

    # dp[A][i]=「○」ならば
    # ⇔X[i]=A[i]の場合
    if dp[0][i]==True:
        # |X[i]-A[i+1]|=|A[i]-A[i+1]|≤Kならば
        if abs(A[i]-A[i+1])<=K:
            # dp[A][i+1]=「○」
            dp[0][i+1]=True
        
        # |X[i]-B[i+1]|=|A[i]-B[i+1]|≤Kならば
        if abs(A[i]-B[i+1])<=K:
            # dp[B][i+1]=「○」
            dp[1][i+1]=True

    # dp[B][i]=「○」ならば
    # ⇔X[i]=B[i]の場合
    if dp[1][i]==True:
        # |X[i]-A[i+1]|=|B[i]-A[i+1]|≤Kならば
        if abs(B[i]-A[i+1])<=K:
            # dp[A][i+1]=「○」
            dp[0][i+1]=True
            
        # |X[i]-A[i+1]|=|B[i]-B[i+1]|≤Kならば
        if abs(B[i]-B[i+1])<=K:
            # dp[B][i+1]=「○」
            dp[1][i+1]=True

# (4)答えを出力する
# dp[A][N-1]=「○」 または　dp[B][N-1]=「○」ならば
if dp[0][N-1]==True or dp[1][N-1]==True:
    # 「Yes」を出力
    print("Yes")
# どちらも「×」ならば
else:
    # 「No」を出力
    print("No")

D - Polynomial division

要するにC/Aの係数を計算しろという問題です。

まずN=1,M=2として方程式を考えてみましょう。

なんとなく法則がありそうですね。

一般のN,Mについて、Bは大きい方から以下のように計算できます。

これをそのまま実装すればOKです。
A[N-1]B[M-(i-1)]+A[N-2]B[M-(i-2)]+...+A[N-k]B[M-(i-k)]+...A[N-i]B[M]
の部分については=xとして個別に計算しています。
N-k<0になった部分は計算しないようにします。
(例えばN=1であればA[N-2]は存在しないのでbreakで飛ばします)

print(*B)とすることでBを[]なしで出力できます。

【提出】

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

# Bを作る
B=[0]*(M+1)

# i=0~M
for i in range(M+1):

    # x=A[N-1]B[M-(i-1)]+A[N-2]B[M-(i-2)]+...+A[N-k]B[M-(i-k)]+...A[N-i]B[M]
    x=0
    # k=1~i
    for k in range(1,i+1):
        # A[N-k]が存在すれば
        if 0<=N-k:
            x+=A[N-k]*B[M-(i-k)]
        # 存在しなければ
        else:
            # 次のiへ
            break
    # 計算
    B[M-i]=(C[M+N-i]-x)//A[N]
    
# 答えの出力
print(*B)

【広告】

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

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

【booth(pdf)】
https://sano192.booth.pm/items/3179185

1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

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

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

サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756

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

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV

【booth(pdf)】
https://booth.pm/ja/items/3698647

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/

【booth(pdf)】
https://sano192.booth.pm/items/3698668

『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

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

サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733

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

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

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

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

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW

【booth(pdf】
https://sano192.booth.pm/items/3785312