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

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

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

A - Signed Difficulty

今回のA問題は「やや難」です。
普段はもっと簡単なので今回解けなかった人も落ち込まずに競技プログラミングを続けてください。

入力を受け取り、X,Yに分けて、条件を判定し、出力します。

入力は最初一つの文字列として受け取り、
Y=後ろから1文字目(Y=XY[-1])
X=後ろから3文字目まで(最後の二文字まで)(X=XY[:-2])
とすればOKです。

あとはif文でYの条件を確認しますが、このときYが文字列のままだと大変なのでint(Y)として整数に変換します。
Yを変換したら問題文のとおりに条件分岐を作って出力します。
(Xと"-"を出力したいなど、文字列を結合したい場合はX+"-"というようにプラスを使えばOKです)

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

【提出】

# 文字として受け取り
XY=input()
# 最後の1文字をYとする(文字列)
Y=XY[-1]
# 文字列から整数へ変換
Y=int(Y)
# 最後の二文字までをXとする
X=XY[:-2]

# 0<=Y<=2ならば
if 0<=Y<=2:
    # X-を出力
    print(X+"-")

# 3<=Y<=6ならば
elif 3<=Y<=6:
    # Xを出力
    print(X)

# 7<=Y<=9ならば
elif 7<=Y<=9:
    # X+を出力
    print(X+"+")

B - Same Name

制約が2≤N≤1000なので、最大のケースでも組み合わせ数は1000 C 2=499500組しかありません。
pythonは2秒以内にだいたい10^6回くらいの計算はできますから、この組数なら全部確認しても間に合います。

全部の組を試す実装ですが、以下のように書けばうまくいきます。

for i in range(N):
    for j in range(i+1,N):
        if Myouzi[i]==Myouzi[j] and Namae[i]==Namae[j]:

i番目の名字名前とj番目の名字名前を比較します。
i=1,2,3,...と増えていきますがjはi+1からスタートしますので、
i=1,j=2
i=1,j=3
...
i=1,j=N-1
i=2,j=3
i=2,j=4
...
i=N-2,j=N-1
といい感じに組を全部作っていくことができます。

途中で同姓同名がいれば「Yes」を出力して終了。
そうでなければループが全て終了し、「No」を出力します。

【提出】

# Nの受け取り
N=int(input())
# 名字を格納するリスト
Myouzi=[]
# 名前を格納するリスト
Namae=[]

# S,Tの受け取り
for i in range(N):
    # S,Tを受け取る
    S,T=map(str,input().split())
    # 名字リストにSを追加
    Myouzi.append(S)
    # 名前リストにTを追加
    Namae.append(T)

# i=1~N-1まで
for i in range(N):
    # j=i+1~N-1まで
    for j in range(i+1,N):
        # i番目の名字名前とj番目の名字名前を比較
        # 名字が同じ　かつ　名前が同じなら
        if Myouzi[i]==Myouzi[j] and Namae[i]==Namae[j]:
            # Yesを出力
            print("Yes")
            # プログラムを終了
            exit()

# 同じ名字、名前が一組もなければここまでくる
# Noを出力
print("No")

C - Many Balls

逆から考えます。
N=14であれば最後の操作の直前は
13(最後がA)
または
7(最後がB)
になっているはずです。
このように考えて0になるまでさかのぼっていきます。

具体的には
・Nが偶数の場合
　答えの左端にBを追加
　Nを2で割る
・Nが奇数の場合
　答えの左端にAを追加
　Nから1を引く
これをN=0になるまで繰り返し、最後に答えの文字列を出力すればOKです。

【提出】

# 入力の受け取り
N=int(input())
# 答え(最初は空)
ans=""

# Nが0より大きい間
while 0<N:
    # Nが偶数なら
    if N%2==0:
        # ansの左端にBを追加
        ans="B"+ans
        # 2で割る
        N//=2
    # それ以外(Nが奇数なら)
    else:
        # ansの左端にAを追加
        ans="A"+ans
        # 1を引く
        N-=1

# 答えを出力
print(ans)

D - Pair of Balls

要するに筒の一番上に同じ色のボールがあるか？をひたすら確認していけばいいわけですが愚直にやるとTLEします。

以下の3つを管理します。
(1)筒の一番上にどの色のボールが何個あるか
(2)筒の一番上にあるボールについてある色のボールは何番目の筒にあるか
(3)筒の一番上に2つあるボールの色はどれか

(3)の情報からまずどのボールを捨てればよいかわかります。
(2)の情報からどの筒の一番上のボールを取り出すか→どの筒の一番上が更新されるかわかります。
(ボールを捨てた後に一番上のボール情報を更新する)
筒の一番上を更新すると同時に(1)の情報も更新します。
そこで一番上に2個となったボールがあれば(3)の情報を更新します。
あとは繰り返しです。

具体的な手順を説明します。
入力を受け取った後、まずそれぞれの筒の一番上のボールを順に確認します。
このとき
(2)筒の一番上にあるボールについてある色のボールは何番目の筒にあるか
(1)筒の一番上にどの色のボールが何個あるか
の情報を記録していきます。

全ての筒について一番上のボールを確認できたら(1)の情報から筒の一番上に2つあるボールの色番号を確認し、
(3)筒の一番上に2つあるボールの色はどれか
を更新します。
((3)の情報はリストではなくdequeで管理すると楽です。dequeが何かわからない人はこの解説の※dequeについてを見てください)

あとは以下を繰り返します
○(3)の情報より一番上に2つあるボールの色を確認
○(2)の情報より一番上に2つあるボールが何番目の筒にあるのか確認→ボールを捨てる
○次に一番上にくるボールのは何色か確認し、(1),(2)を更新
　筒の一番上に来たボールの色について、数が2になったら(3)へ格納

筒の一番上に2つある色がなくなったら終了です。
ひとつでもボールが残っている筒があればNo,全ての筒が空ならYesを出力します。

この問題は管理する情報が多く、コードを書いている途中でよくわからなくなるかもしれません。
変数名を工夫して何を表した変数、リストなのか、パット見でわかるようにすると余計なバグを減らせるでしょう。

※dequeについて
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
使い方は

from collections import deque
変数名=deque()

とするだけでOKです。
追加はリスト同様(変数名).append
先頭から要素を取り出すときは(変数名).popleft()
としてください。
詳しく知りたい人は以下のページを見てください。

【提出】

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

# 筒の情報
pipe=[]

for i in range(M):
    # Kを受け取り
    K=int(input())
    # リストで受け取る
    tmp_list=list(map(int, input().split()))
    # M本目の筒に情報を格納
    pipe.append(tmp_list)

# 色iのボールが何番目の筒の一番上にあるかを記録するリスト
# pipe_num[3]=[0,5]ならば色3のボールが0,5番目の筒の一番上にある
pipe_num=[[] for i in range(N+1)]

# 色iのボールが筒の一番上に何個あるか記録するリスト
cnt=[0]*(N+1)

# 筒の一番上を順に確認する
for i in range(M):
    # i本目の筒の一番上にあるボールの色
    on_color=pipe[i][-1]
    # pipe_numに「色on_colorのボールがi番目の筒の一番上にある」と記録
    pipe_num[on_color].append(i)
    # 色on_colorのボールが筒の一番上にある個数をプラス1
    cnt[on_color]+=1

# dequeをインポート
from collections import deque
# 一番上に2つあるボールの色番号を格納するキュー
set_que=deque()

# それぞれの色について一番上にいくつあるか確認
for i in range(1,N+1):
    # もし一番上に二個あるならば
    if cnt[i]==2:
        # キューにその色番号を追加
        set_que.append(i)

# キューが空になるまで
while 0<len(set_que):
    # キューの左端から一番上に二個あるボールの色番号を取得
    set_color=set_que.popleft()
    # set_color色のそれぞれのボール(ボール1,ボール2)が何番目の筒の一番上にあるかを取得
    ball1_pipe_num,ball2_pipe_num=pipe_num[set_color]

    # それぞれのボールがある筒の一番上を削除(ボールを取り出す)
    pipe[ball1_pipe_num].pop()
    pipe[ball2_pipe_num].pop()

    # もしボール1が入っていた筒が空でなければ
    # 筒の一番上の情報を更新する
    if 0<len(pipe[ball1_pipe_num]):
        # 次に一番上にくるボール
        next_ball1_col=pipe[ball1_pipe_num][-1]
        # next_ball1_col色のボールが一番上にある数を+1
        cnt[next_ball1_col]+=1
        # next_ball1_col色のボールがball1_pipe_num番目の筒の一番上にあると情報を更新
        pipe_num[next_ball1_col].append(ball1_pipe_num)
        # もし一番上にnext_ball1_col色のボールが二個あるならば
        if cnt[next_ball1_col]==2:
            # キューにnext_ball1_colを追加
            set_que.append(next_ball1_col)

    # もしボール2が入っていた筒が空でなければ
    # 筒の一番上の情報を更新する
    if 0<len(pipe[ball2_pipe_num]):
        # 次に一番上にくるボール
        next_ball2_col=pipe[ball2_pipe_num][-1]
        # next_ball2_col色のボールが一番上にある数を+1
        cnt[next_ball2_col]+=1
        # next_ball2_col色のボールがball2_pipe_num番目の筒の一番上にあると情報を更新
        pipe_num[next_ball2_col].append(ball2_pipe_num)
        # もし一番上にnext_ball2_col色のボールが二個あるならば
        if cnt[next_ball2_col]==2:
            # キューにnext_ball2_colを追加
            set_que.append(next_ball2_col)

# キューが空になったら
for i in range(M):
    # 長さが0より大きい筒が残っていたら
    if 0<len(pipe[i]):
        # Noを出力
        print("No")
        # 終了
        exit()
        
# 全ての筒の長さが0ならば(全てのボールが捨てられていたら)
# Yesを出力
print("Yes")

E - Amusement Park

要するにその場その場で一番満足度が高いものに乗り続ければ良いわけですが、Kが大きすぎるため愚直にやるとTLEします。

次の問題に置き換えます。
それぞれのiについて、1～Aiまでの番号が書かれたカードを用意する。
合計が一番大きくなるようK枚のカードを取った場合のカードの合計値を答えよ。

例として以下のような入力の場合を考えます。
4 9
8 4 7 1

N=4
K=9
A:8 4 7 1
この場合は以下のようなカードが用意されます。

当然上の方にあるカードから取っていった方が良いです。
A1の8,7,6,5,4
A2の4
A3の7,6,5
を取って合計52(8+7+6+5+4+4+7+6+5)が答えとなります。

ですがこれも愚直にカードをとっていくとTLEします。
そこでこのカード群に線を引きます。

この線は
「これより上のカードを全て取る」
線です。

青の線より上にはA1の8,7,6,5とA3の7,6,5で7枚のカードがあります。Kは9ですから、これらは全て取れます。
赤の先より上にはA1の8,7,6,5,4とA2の4とA3の7,6,5,4で10枚のカードがあります。Kは9ですからこれらは全て取れません。
この線を可能な限り低く引いて、
線の上にあるカードはすべて取る+残り取れる枚数は線のすぐ下にあるカードを取る
という戦略を取ります。

この例でいうと
青い線の上にあるカード：8+7+6+5+7+6+5=44(7枚)
青い線のすぐ下にあるカード：4
残り取れる枚数：9-7=2
残り取れる枚数分のカード合計：4*2=8
答え：44+8＝52
となります。

ちなみにカード全体の枚数がK以下ならば全てのカードを取れます。この計算は和の公式を使って簡単にできます。

【和の公式】
A~Bまでの和=(B-A+1)*(A+B)//2

線を一番低く引ける場所、すなわち線の上のカード枚数がK枚以下になるところの最小を探す必要があります。
これには二分探索を使います。

二分探索のやり方を説明します。わかりやすいように1~100の間で探索しましょう。
まず探索範囲1~100の中間地点の上に線が引けるか確認します。
((1+100)//2=50なので50の上に線が引けるか確認します)
確認はAの値を順に確かめていけばOKです。A1=53なら50の上に3枚のカードがある、A2=54なら50の上に4枚・・・という感じ。
・50の上に線が引けたら(50より上にあるカードの枚数がK以下なら)
　探索範囲を1～50とします。
・50の上に線が引けなかったら(50より上にあるカードの枚数がKより多いなら)
　探索範囲を50～100とします。
あとは繰り返しです。

コツは
探索範囲の左端は常に条件を満たさない(線が引けない)
探索範囲の右端は常に条件を満たす(線が引ける)
としておくことです。
(この方法は以下サイトに記載のやり方をお借りしています)

探索範囲両端の差が1(8~9など)になったら終了です。
右端が条件を満たすうちの最小、つまり一番低く線を引ける場所です。

あとは
線の上にあるカードはすべて取る+残り取れる枚数は線のすぐ下にあるカードを取る
を答えとして出力すれば終了です。
線の上にあるカードをすべて取ったときの合計値は和の公式を使って計算します。

実装では二分探索の「線を引けるか」判定する部分をまるごと関数にして、
xより上に線を
・引ける
　Trueを返す
・引けない
　Falseを返す
としてしまうと楽です。

【提出】

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

# もし全てのカードが取れるなら⇔Aの和<=Kならば
if sum(A)<=K:
    # 答えの格納変数
    ans=0
    # Aの要素を順にaへ
    for a in A:
        # 1~aまでの和をansへプラス
        ans+=a*(a+1)//2
    # ansを出力
    print(ans)
    # 終了
    exit()

# 二分探索
# xより上に線を引いてK枚カードが取れるか
def Nibutan(x):
    # カードを取る枚数をカウント
    cnt=0
    # Aの要素を順にaへ
    for a in A:
        # a-x+1枚のカードが取れる(マイナスになったら0とする)
        cnt+=max(a-x+1,0)
    # K枚取れるなら
    if cnt<=K:
        # Trueを返す
        return True
    # そうでないなら(K枚とれないなら)
    else:
        # Falseを返す
        return False

# 左端=1
left=1
# 右端=バカでかい数
right=10**20

# 1<右端-左端の間
while 1<right-left:
    # 真ん中=(左端+右端)//2
    center=(left+right)//2

    # centerより上に線を引いてK枚カードが取れる場合
    if Nibutan(center)==True:
        # 右端をcenterへ更新
        right=center
    # そうでないなら(centerより上に線を引いてK枚カードが取れない場合)
    else:
        # 左端をcenterへ更新
        left=center

# 探索終了⇔right-left=1
# rightが上に線を引いてK枚カードが取れる最小値

# 答え
ans=0
# Aの要素を順にaへ
for a in A:
    # もしaがrightより大きければ
    if right<=a:
        # rightより大きなカードをすべて取れる
        # a~rightまでの和を足す
        ans+=(a-right+1)*(a+right)//2
        # 取った枚数をKから引く
        K-=a-right+1

# 残り枚数(K)はright-1のカードを取る
ans+=(right-1)*K

# 答えを出力
print(ans)

【広告】

『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】