Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
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

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

Last updated at Posted at 2022-08-24

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

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

更新時はツイッターにて通知します。
https://twitter.com/AtCoder4

A - Apple　Dif:18

X円を払ってりんごを1個手に入れる。
Y円を払ってりんごを3個手に入れる。
両方のパターンを比較して安い方を確認しましょう。

1個ずつ買う場合は当然(X*N)円になります。
3個セットで買う場合は3個セットで買えるだけ買って、余りの分をバラ売りのX円で買う形になります。
すなわち((Nを3で割った商)*Y+(Nを3で割った余り)*X)円になります。

商を計算するときは「//」、余りを計算するときは「%」を使います。
A,Bの小さい方を確認するときはmin(A,B)となります。

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

【提出】

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

# 1個ずつ買う場合
A=X*N
# 3個セットで買う場合
# ((Nを3で割った商)*Y+(Nを3で割った余り)*X)円
B=(N//3)*Y+(N%3)*X

# A,Bの小さい方が答え
print(min(A,B))

B - Explore　Dif:152

部屋Nにたどり着けるかをシミュレーションします。
まずはボーナス部屋で増加する時間をリストに記録しておくと実装が楽です。
具体的には
X1 Y1：1 4
X2 Y2：3 9
X3 Y3：5 2
であれば
Bonus=[0,4,0,3,0,5]
というような形で記録します。※最初の要素は0番目、すなわちBonus[0]となることに注意してください。

後は部屋を移動しながら持ち時間Tを減らしたり増やしたりします。
途中で持ち時間が0以下になったら「No」を出力して終了です。

【提出】

# 入力の受け取り
N,M,T=map(int,input().split())
# A[0]を埋めるために適当な数字(0)を入れておく
A=[0]+list(map(int,input().split()))

# ボーナス部屋で増加する時間の記録リスト
Bonus=[0]*(N+1)
# M回
for i in range(M):
    # 入力の受け取り
    X,Y=map(int,input().split())
    # 部屋XでY増える
    Bonus[X]=Y

# i=1~(N-1)
for i in range(1,N):
    # 部屋(i+1)へ移動するためにA[i]時間消費する
    T-=A[i]

    # Tが0以下になったら
    if T<=0:
        # 「No」を出力
        print("No")
        # 終了
        exit()
        
    # (i+1)番目の部屋で増加する時間
    T+=Bonus[i+1]

# 「Yes」を出力
print("Yes")

C - Belt Conveyor　Dif:212

実際に移動してどこにたどり着くかをシミュレーションします。
次に進む場所が壁ならばシミュレーション終了し、答えを出力します。
一度通ったマスにもう一度到達した場合はループするので「-1」を出力します。通ったマスを二次元配列に記録しておきましょう。

二次元配列でシミュレーションする場合、左上の座標は(1,1)ではなく(0,0)となり、一つずれてしまうということに注意してください。

【提出】

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

# グリッド
G=[]
# H回
for i in range(H):
    # 入力の受け取り
    S=input()
    # 1文字ずつリストへ展開
    S=list(S)
    # グリッドに追加
    G.append(S)

# 通ったマスを記録する二次元配列
# 初期値は0
# 通ったマスは1にしていく
visited=[[0]*W for i in range(H)]

# 今の行(G)、列(R)
NowG,NowR=0,0

# 10^10回(大きな数なら何でもOK)
for i in range(10**10):

    # 今いるマスが訪問済みならば
    if visited[NowG][NowR]==1:
        # 「-1」を出力
        print(-1)
        # 終了
        exit()

    # 今いるマスを訪問済みにする
    visited[NowG][NowR]=1

    # 今いるマスが「U」ならば
    if G[NowG][NowR]=="U":
        # 今いるマスの行番号が1以上ならば(上に進んでも壁でないなら)
        if 1<=NowG:
            # 上に進む⇔行をマイナス1
            NowG-=1
        # そうでなければ(上マスが壁)
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()
    
    # 今いるマスが「R」ならば
    elif G[NowG][NowR]=="R":
        # 今いるマスの列番号が(W-2)以下ならば(右に進んでも壁でないなら)
        if NowR<=W-2:
            # 右に進む⇔列をプラス1
            NowR+=1
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()

    # 今いるマスが「D」ならば
    elif G[NowG][NowR]=="D":
        # 今いるマスの行番号が(H-2)以下ならば(下に進んでも壁でないなら)
        if NowG<=H-2:
            # 下に進む⇔行をプラス1
            NowG+=1
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()

    # 今いるマスが「L」ならば
    elif G[NowG][NowR]=="L":
        # 今いるマスの列番号が1以上ならば(左に進んでも壁でないなら)
        if 1<=NowR:
            # 左に進む⇔列をマイナス1
            NowR-=1
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()

D - Iroha and Haiku (New ABC Edition)　Dif:727

難しい問題を考えるときのテクニックの一つとして「制約を緩めてみる」というのがあります。
本問の場合、
Ax+A(x+1)+...+A(y-1)=P
という条件しかなければこれは「区間和がぴったりPになる区間はAに存在するか？」という問題になります。

尺取法で考えます。
尺取法は区間の左端、右端を条件に合わせて動かしながら区間の長さ等を計算するアルゴリズムです。

例を見ましょう。
A：1 2 3 1 2 3 4 5 6
P=6
まず
左=0
右=0
として、[左,右]=[0,0]の区間和を考えます。A[0~0]の区間和なので当然A[0]=1です。
区間和=1
まだP=6より小さいので、右を1つ進めます。

左=0
右=1
[左,右]=[0,1]の区間和を考えます。このとき[0,0]の区間和は計算済みで、これにA[1]が加えられるだけですから、先程計算したものにA[1]=2を追加するだけで良いです。
区間和=1+2=3
まだP=6より小さいので、右を1つ進めます。

左=0
右=2
[左,右]=[0,2]の区間和を考えます。同様に[0,1]の区間和は計算済みで、これにA[2]が加えられるだけですから、先程計算したものにA[2]=3を追加するだけで良いです。
区間和=3+3=6
P=6と合致しました。つまり区間和A[0~2]＝Pということがわかります。
さてこの時点で区間和はP以上になりましたから、これ以上右を進める必要はありません。なぜなら1≤Aiという条件より右を進めると区間和は確実に増加し、=Pにはならないからです。
今度は左を進めます。

左=1
右=2
[左,右]=[1,2]の区間和を考えます。[0,2]の区間和は計算済みで、今度はA[0]がなくなったわけですから、A[0]=1をマイナスします。
区間和=6-1=5
P=6より小さいので、右を1つ進めます。

この操作を繰り返すことで、Aの区間和=Pとなっている区間を確認できます。
計算量は左、右がそれぞれ0~(N-1)までを最大1回ずつ通るのでO(N)となります。
区間和がP=6となるのは以下の5つです。
[0, 2] [1, 3] [2, 4] [3, 5] [8, 8]
これをPlistとして二次元配列に記録しておきます。

例えばQ=5,R=4の場合、同様にしてQlist、Rlistを作ると以下のようになります。
Plist：[0, 2] [1, 3] [2, 4] [3, 5] [8, 8]
Qlist：[1, 2] [4, 5] [7, 7]
Rlist：[2, 3] [6, 6]

問題は
A[x~(y-1)]=P
A[y~(z-1)]=Q
A[z~(w-1)]=R
となるx,y,z,wを見つけろということでした。
A[x~(y-1)]=Pとなるために候補として考えられる(x,y)はPlistを見ながら考えると
(x,y)=(0,3),(1,4),(2,5),(3,6),(8,9)
ですね。(A[x~y]=PではなくA[x~(y-1)]=Pであることに注意してください。
同様にA[y~(z-1)]=Qとなる(y,z)の候補は
(y,z)=(1,3),(4,6),(7,8)
A[z~(w-1)]=Rとなる(z,w)の候補は
(z,w)=(2,4),(6,7)
です。
この中からうまく代入できるものを探します。
具体的には
(x,y)=(0,3)とした時、(y,z)として選べるものはあるか、(z,w)として選べるものはあるか
(x,y)=(1,4)とした時、(y,z)として選べるものはあるか、(z,w)として選べるものはあるか
...
と一個ずつ組み合わせを見ていきます。

結果として以下ならうまくいくことがわかります。
(x,y)=(1,4)
(y,z)=(4,6)
(z,w)=(6,7)
よって答えは「Yes」になります。

尺取法は区間の左をfor、右をwhileで動かすとうまくいくことが多いです。
うまくできないという人は一度【提出】をまるまる写して、その後なにも見ずに自分で実装できるか試してみましょう。

【提出】

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

# 区間和=Pとなる区間のリスト
Plist=[]
# 区間和(初期値はA[0])
S=A[0]

# 区間の右
r=0

# l(区間の左)=0~(N-1)
for l in range(N):

    # r<Nの間
    while r<N:
        # 区間和がPより小さい
        if S<P:
            # 右を進める
            r+=1
            # 右端を超えたら
            if r==N:
                # 終了
                break
            # A[r]を足す
            S+=A[r]
        # 区間和がP以上
        else:
            # ぴったりPになったら
            if S==P:
                # 区間を記録
                Plist.append([l,r])
            # 次の区間(左を進める)
            break
    
    # 左を進めるのでマイナス
    S-=A[l]


# 区間和=Qとなる区間のリスト
Qlist=[]

# Plistと同様に作る
S=A[0]
r=0
for l in range(N):
    while r<N:
        if S<Q:
            r+=1
            if r==N:
                break
            S+=A[r]
        else:
            if S==Q:
                Qlist.append([l,r])
            break    
    S-=A[l]

# 区間和=Rとなる区間のリスト
Rlist=[]

# Plistと同様に作る
S=A[0]
r=0
for l in range(N):
    while r<N:
        if S<R:
            r+=1
            if r==N:
                break
            S+=A[r]
        else:
            if S==R:
                Rlist.append([l,r])
            break    
    S-=A[l]

# Plist,Qlist,Rlistのどれかが空なら
if len(Plist)==0 or len(Qlist)==0 or len(Rlist)==0:
    # 「No」を出力
    print("No")
    # 終了
    exit()

# Qlistのi2番目を確認
i2=0
# Qlistのi3番目を確認
i3=0

# i1=0~(Plistの長さ-1)
for i1 in range(len(Plist)):
    # Plistのi1番目の区間の右
    Pr=Plist[i1][1]
    # Qlistのi2番目の区間の左
    Ql=Qlist[i2][0]

    # 「Qlistの区間の左」<「Plistの区間の右」+1である間
    while Ql<Pr+1:
        # Qlistの次の区間へ進む
        i2+=1
        # i2がQlistの長さを超えたら
        if i2==len(Qlist):
            # 「No」を出力
            print("No")
            # 終了
            exit()
        # Qlistのi2番目の区間の左
        Ql=Qlist[i2][0]

    # 「Qlistの区間の左」<「Plistの区間の右」+1になったら
    if Ql==Pr+1:
        # Qlistのi2番目の区間の右
        Qr=Qlist[i2][1]
        # Rlistのi3番目の区間の左
        Rl=Rlist[i3][0]

        # 「Rlistの区間の左」<「Qlistの区間の右」+1である間
        while Rl<Qr+1:
            # Rlistの次の区間へ進む
            i3+=1
            # i2がRlistの長さを超えたら
            if i3==len(Rlist):
                # 「No」を出力
                print("No")
                # 終了
                exit()
            # Rlistのi3番目の区間の左
            Rl=Rlist[i3][0]
        
        # 「Rlistの区間の左」<「Qlistの区間の右」+1になったら
        if Rl==Qr+1:
            # 「Yes」を出力
            print("Yes")
            # 終了
            exit()

# 「No」を出力
print("No")

【広告】

『AtCoder 最速で緑になる 基礎・典型50問詳細解説』

ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP

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

冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843

『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

4
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
4
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?