Go to Qiita Advent Calendar 2024 Top
LoginSignup
6
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@sano192

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

Last updated at Posted at 2022-02-22

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

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

A - Edge Checker

図を見れば分かる通り1個前の数字と1個後の数字が線で結ばれています。
しかし「1」については1個前が0でなく10になります。
以上をまとめて条件分岐にします。

・a=1
　・b=2または10→「Yes」
　・それ以外→「No」
・それ以外(aが1でない)
　・b=a+1→「Yes」
　・それ以外→「No」

「または」という条件は「or」を使います。

「Yes」「No」は文字列なので出力の際、"Yes","No"とダブルクオーテーションをつけてください。

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

【提出】

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

# a=1ならば
if a==1:
    # b=2または10ならば
    if b==2 or b==10:
        # 「Yes」を出力
        print("Yes")
    # そうでないなら
    else:
        # 「No」を出力
        print("No")
# それ以外(aが1でない)
else:
    # b=(a+1)ならば
    if b==a+1:
        # 「Yes」を出力
        print("Yes")
    # そうでないなら
    else:
        # 「No」を出力
        print("No")

B - Count Distinct Integers

「aには何種類の整数があるか？」を「aから重複を削除したら長さがいくらになるか？」と読み替えます。

pythonにはリストの他にセットというものがあり、セットには重複した要素が入りません。
よってaをリスト→セットに変換し、その長さを出力します。

リスト→セットへの変換は
set(リスト)
と書きます。

セットもリスト同様
len(セット)
で長さが確認できます。

【提出】

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

# リスト→セットへ変換
a_set=set(a)

# 長さを出力
print(len(a_set))

C - Jumping Takahashi

i回目のジャンプで到達できる場所を考えましょう。
1回目のジャンプではa1またはb2に到達できます。
2回目のジャンプでは「1回目のジャンプで到達できる場所」+a2または+b2に到達できます。
このように考えると「(i-1)回目のジャンプで到達できる場所」がわかっていれば
i回目のジャンプでは「(i-1)回目のジャンプで到達できる場所」+aiまたは+biに到達できます。

しかし1回ずつ到達できる場所をそのまま記録していくとN=100の場合に最後到達できる場所の数が2^100になってしまいます。
以下の2つを考慮して記録する場所を減らしましょう。
(1)重複する場所は記録しなくていい
　i回目のジャンプで到達できる場所がかぶってもそれを二重に記録する意味はありません。
　実装では重複しないようにセットを使って記録します。
(2)Xより大きい場所に到達しても記録しなくていい
　ジャンプは常に正の方向であり戻れないので、Xを超えた時点で記録する意味はありません。

N回ジャンプして到達できる場所の中にXがあれば「Yes」、なければ「No」となります。

【提出】

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

# i回目のジャンプで到達できる場所(distance)
dist=set()

# 最初は0にいる
dist.add(0)

# N回
for i in range(1,N+1):
    # 入力の受け取り
    a,b=map(int,input().split())

    # 新しい到達できる場所
    new_dist=set()

    # now=(i-1)回目のジャンプで到達できる場所
    for now in dist:
        # +aした場所がX以下なら
        if now+a<=X:
            # 新しい到達できる場所に記録
            new_dist.add(now+a)
        # +bした場所がX以下なら
        if now+b<=X:
            # 新しい到達できる場所に記録
            new_dist.add(now+b)

    # 到達できる場所を更新
    dist=new_dist

# Xがdistにあれば
if X in dist:
    # 「Yes」を出力
    print("Yes")
# そうでなければ(Xがdistになければ)
else:
    # 「No」出力
    print("No")

D - Strange Balls

実際に筒にボールを落としたり消したりしながらボールの数を確認します。
筒の名前はqueとしましょう。queの左側が筒の底、右側が上です。
(筒の一番上=queの右端はque[-1]で確認できます)

ボールを落とした時消えるかどうか判断するために以下の情報が必要です。
・今1番上にあるボールの数字(que[-1])
・同じ数字のボールがいくつ下に続いているか(count)
　これはボールを消した時に再計算しなくて済むよう、リストで記録します。
　例えば筒の中身が
　que=[5,3,3,4,4,4,2]だったら
　count=[1,1,2,1,2,3,1]
　となります。
　この後「2」のボールが来たときは筒の中身が[5,3,3,4,4,4,2,2]となり、末尾の「2」が消えて[5,3,3,4,4,4]となります。
　この時同時にcountも筒のボールを消した分消します。
　que=[5,3,3,4,4,4,2,2]→[5,3,3,4,4,4](2つ消えた)
　count=[1,1,2,1,2,3,1,2]→[1,1,2,1,2,3](2つ消えた)
　これで今1番上にあるのはque[-1]=4、そして「4」がcount[-1]=3個続いているということがわかるわけです。

更に答えを出すために以下も必要です
・今筒の中にあるボールの数
　これはボールを入れる度+1,消すたびに-1すればいいです。

【提出】

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

# 筒
que=[]
# 同じ数字のボールがいくつ下に続いているか
count=[]
# 今筒の中にあるボールの数
ans=0

# i=0~(N-1)
for i in range(N):
    # 筒にボールを落とす
    que.append(a[i])
    # 筒の中のボールが1個増える
    ans+=1

    # 筒に2つ以上ボールがある　かつ　1番上のボールと2番目のボールの数字が同じ
    if 2<=len(que) and que[-1]==que[-2]:
        # 同じ数字のボールが続いている個数を+1
        count.append(count[-1]+1)
        # (1番上のボールの数字)個続いたら
        if count[-1]==que[-1]:
            # (1番上のボールの数字)個消える(=取り出す)
            # ⇔(1番上のボールの数字)回取り出し
            for j in range(que[-1]):
                # 筒から取り出す
                que.pop()
                # countも消す
                count.pop()
                # ボールが1個減った
                ans-=1
    # そうでないなら
    else:
        # 2番目と1番目のボールは別の数字だから「1」を記録
        count.append(1) 
    
    # 答えを出力
    print(ans)

E - Ranges on Tree

問題文が何を言っているか意味不明ですね。
順番に読み解いていきましょう。

N頂点の根付き木が与えられます。頂点1が根です。
i=1,2,…,N−1について、i番目の辺は頂点uiと頂点viを結んでいます。

木があるそうです。
とりあえずこんなかんじにしましょう。
ABC240_E_1.png

i=1,2,…,Nについて、頂点iを根とする部分木に含まれる頂点全体からなる集合をSiで表します。
（各頂点は自身を根とする部分木に含まれます。すなわち、i∈Siです。)

各頂点についてSiを定義するようです。
Siは各頂点の部分木の頂点を全部ぶち込んだ集合(自分含む)とのことです。
つまりこんなかんじです。
ABC240_E_2.png

また、整数l,rについて、l以上r以下の整数全体からなる集合を[l,r]で表します。
すなわち、[l,r]={l,l+1,l+2,…,r}です。

突然よくわからない[l,r]が出てきました。どうやらこれは区間のようです。
例えば[1,5]={1,2,3,4,5}となります。

整数の2つ組をN個並べた列((L1,R1​),(L2​,R2​),…,(LN​,RN​))であって以下の条件を満たすものを考えます。
・1≤i≤Nを満たすすべての整数iについて、1≤Li​≤Ri​

Li,Riは1より大きく、かつLi​≤Riなので[左,右]=[Li,Ri]でそれをN個用意しますよってことですね。

i,j≤Nを満たすすべての整数の組(i,j)について次が成り立つ
Si​⊆Sj​ならば、[Li​,Ri​]⊆[Lj​,Rj​]

頂点iの部分木に頂点jの部分木が含まれるなら→[Li​,Ri​]⊆[Lj​,Rj​]([Lj​,Rj​]は[Li​,Ri​]を含む)
Si​⊆Sjというのは図でいうと例えばS3⊆S4とか、S5⊆S1があります。
雑に説明するとSjの下にある頂点iが全部Siということです。
そうであるなら[Li​,Ri​]⊆[Lj​,Rj​]とのことです。どうやら各頂点について[Li​,Ri​]を決めればよさそうですね。
もう一つの条件も見ましょう。

Si​∩Sj​=∅ならば、[Li​,Ri​]∩[Lj​,Rj​]=∅

頂点iと頂点jの部分木がかぶっていなければ→[Li​,Ri​]∩[Lj​,Rj​]=∅(共通部分がない)
Si​∩Sjというのは図でいうと例えばS3​∩S5=∅,S2​∩S4​=∅があります。それぞれ部分木にかぶっている要素がありませんね。

この条件を満たすように各頂点へ[Li​,Ri​]を割り振ってみましょう。

ABC240_E_3.png

全ての条件を満たしていることを確認してください。

ではどうやって[Li​,Ri​]を割り振るか考えましょう。
まず2つ目の条件「Si​∩Sj​=∅ならば、[Li​,Ri​]∩[Lj​,Rj​]=∅」から「葉」の部分、すなわち木の末端は共通部分があってはいけないことがわかります。
図で言うと頂点②,③,⑤が「葉」です。
「葉」は部分木が自分自身だけなので、もし共通範囲があると条件に反します。
なので「葉」それぞれは別々の区間を割り振ります。葉が3つあるなら[1,1],[2,2],[3,3]という区間を割り振ります。

次に「親」と「子」の関係を考えます。
「親」「子」は上のグラフを家系図だと思ってみればわかりやすいと思います。
頂点④は「親」で、③,⑤は④の「子」です。
頂点①は「親」で、②,④は①の「子」です。
きちんとした定義はややこしいので興味のある人だけ調べてみてください。「親」「子」の雰囲気だけわかったら問題は解けます。

1つ目の条件「Si​⊆Sj​ならば、[Li​,Ri​]⊆[Lj​,Rj​]」から「親」の区間は「子」の区間全てをカバーできる範囲、すなわち
「親」のLi=「子」のLiのうち最も小さいもの
「親」のRi=「子」のRiのうち最も大きいもの
でなければならないことがわかります。

例えば④の「子」は
③=[2,2]
⑤=[3,3]
となっています。
Liは「③と⑤のLiのうち小さい方」=2
Riは「③と⑤のRiのうち大きい方」=3
よって④には[2,3]を割り当てます。

①の「子」は
②=[1,1]
④=[2,3]
となっています。
Liは「②と④のLiのうち小さい方」=1
Riは「②と④のRiのうち大きい方」=3
よって①には[1,3]を割り当てます。

以上より
(1)「葉」に[1,1],[2,2],...を割り当てる
(2)「子」の「親」に[子の最小値,子の最大値]を割り当てる
という順序で決めていけばよいことがわかりました。下から上に向かっていくイメージです。

実装はDFSを使います。
「葉」の頂点から処理する必要があるため、各頂点に2回ずつ訪問するという方法を取ります。
・1回目の訪問では「子」の頂点をキューへ入れる
・2回目の訪問では「葉」なら区間の割当、「子」の情報から「親」の区間更新
という処理を行います。

手順は以下です。
(1)キューを用意する
　※キューに「今いる頂点、今いる頂点の親、訪問回数」を記録
(2)スタート地点=頂点①をキューへ入れる
　(①の親はいないから0にしておく。訪問回数は1回目)
(3)キューの「右端から」要素を取り出す
　・1回目の訪問ならば
　　(3_1)「今いる頂点」を2回目の訪問としてキューへ記録
　　(3_2)「今いる頂点から行ける頂点」のうち、「親」でないものをキューへ1回目の訪問として記録
　・2回目の訪問ならば
　　・「葉」であれば(頂点①でない　かつ　出ている辺の本数が1本)
　　　(3_3)区間の割当([1,1],[2,2],...)
　　(3_4)「子」の情報から「親」の区間更新
　
これで各頂点の区間を割り当て、答えを出力します。

【提出】

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

# 辺の情報
edge=[[] for i in range(N+1)]
for i in range(N-1):
    # 入力の受け取り
    u,v=map(int,input().split())
    edge[u].append(v)
    edge[v].append(u)
    # ①→②,③,④がつながっているなら
    # edge[1]=[2,3,4]

# 区間
LR=[[10**9,-1] for i in range(N+1)]

# (1)キューを用意する
# 「今いる頂点、今いる頂点の親、訪問回数」を記録
que=[[1,0,1]]

# 「葉」に割当する区間
leaf_count=1

# キューが空になるまで
while 0<len(que):
    # (3)キューの「右端から」要素を取り出す
    # 今いる頂点、今いる頂点の親、訪問回数
    now,parent,visit=que.pop()

    # ・1回目の訪問ならば
    if visit==1:
        # (3_1)「今いる頂点」を2回目の訪問としてキューへ記録
        que.append([now,parent,2])
        # to：「今いる頂点」から行ける頂点
        for to in edge[now]:
            # 親でなければ
            if to!=parent:
                # (3_2)「今いる頂点から行ける頂点」のうち、「親」でないものをキューへ1回目の訪問として記録
                que.append([to,now,1])
    
    # ・2回目の訪問ならば
    else:
        # ・「葉」であれば(頂点①でない　かつ　出ている辺の本数が1本)
        if now!=1 and len(edge[now])==1:
            # (3_3)区間の割当([1,1],[2,2],...)
            LR[now]=[leaf_count,leaf_count]
            # カウントを増やす
            leaf_count+=1
        # (3_4)「子」の情報から「親」の区間更新
        # 「親」Li=(現在のLi)と(子のLi)の小さい方
        LR[parent][0]=min(LR[parent][0],LR[now][0])
        # 「親」Ri=(現在のRi)と(子のRi)の大きい方
        LR[parent][1]=max(LR[parent][1],LR[now][1])

# i=1~N
for i in range(1,N+1):
    # 答えを出力
    print(*LR[i])

【広告】

『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

6
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?