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

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

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

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

A - Intersection　Dif:51

いくつかパターンを作って眺めてみましょう。

赤、青両方で塗られた長さというのは
・赤、青で塗られた範囲の左端のうち、より右にある方
　⇔L1,L2のうち大きい方
・赤、青で塗られた範囲の右端のうち、より左にある方
　⇔R1,R2のうち小さい方
によって決まります。

つまり
L1,L2のうち大きい方をLmax
R1,R2のうち小さい方をRmin
とすると答えは
Rmin-Lmax
となるわけです。

L1,L2のうち大きい方はmax(L1,L2)
R1,R2のうち小さい方はmin(R1,R2)
と書けば求まります。

ただし、(Rmin-Lmax)がマイナスになったら両方で塗られた部分はなし、すなわち答えは0になります。
これはifで確認します。

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

【提出】

# 入力の受け取り
L1,R1,L2,R2=map(int,input().split())

# L1,L2のうち大きい方
Lmax=max(L1, L2)
# R1,R2のうち小さい方
Rmin=min(R1, R2)

# (Rmin-Lmax)がマイナスなら
if Rmin-Lmax<0:
    # 0を出力
    print(0)
# そうでなければ
else:
    # (Rmin-Lmax)を出力
    print(Rmin-Lmax)

B - Tournament Result　Dif:74

片方が勝ちならばもう片方は負け
片方が負けならばもう片方は勝ち
片方が引き分けならばもう片方は引き分け
これらが成り立っているかを確認します。

つまり
Aij=「W」ならばAji=「L」
Aij=「L」ならばAji=「W」
Aij=「D」ならばAji=「D」
となっているかを全てのi,jの組について確認します。
一つでも正しくないものがあれば「incorret」を出力して終了します。

まず入力を二次元配列で受け取りましょう。
Aという空のリストを用意します。
Sを受け取ったら一文字ずつリストへ展開します。これはlist(S)と書けばOKです。
それをAへ追加すれば二次元配列が作れます。
これでAijの要素はA[i][j]と書くことで確認ができます。

# 表
A=[]

# N回
for i in range(N):
    # 入力の受け取り
    S=input()
    # 一文字ずつリストへ展開
    Slist=list(S)
    # Tableへ追加
    A.append(Slist)

続いてi=0,1,2,...についてそれぞれj=0,1,2,...とし、A[i][j]とA[j][i]を確認していきます。
以下のように書くことで(i,j)=(0,0),(0,1),(0,2),...(1,0),(1,1),(1,2),...(2,0),(2,1),(2,2),...と順に代入して処理ができます。

# i=0~(N-1)
for i in range(N):
    # j=0~(N-1)
    for j in range(N):

A[j][i]=「L」でない
という条件は
A[j][i]!="L"
と、「!=」で表します。

【提出】

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

# 表
A=[]

# N回
for i in range(N):
    # 入力の受け取り
    S=input()
    # 一文字ずつリストへ展開
    Slist=list(S)
    # Tableへ追加
    A.append(Slist)

# i=0~(N-1)
for i in range(N):
    # j=0~(N-1)
    for j in range(N):

        # i=jの場合
        if i==j:
            # 次のjへ
            continue

        # A[i][j]="W"　かつ　A[j][i]≠"L"　の場合
        if A[i][j]=="W" and A[j][i]!="L":
            # 「incorret」を出力
            print("incorrect")
            # 終了
            exit()
        # A[i][j]="L"　かつ　A[j][i]≠"W"　の場合
        if A[i][j]=="L" and A[j][i]!="W":
            # 「incorret」を出力
            print("incorrect")
            # 終了
            exit()
        # A[i][j]="D"　かつ　A[j][i]≠"D"　の場合
        if A[i][j]=="D" and A[j][i]!="D":
            # 「incorret」を出力
            print("incorrect")
            # 終了
            exit()

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

C - NewFolder(1)　Dif:179

連想配列を使えば簡単に解けます。
連想配列のキーをS、値を出現回数として、
・出現回数が0　→　何もつけずにSを出力
・出現回数が1以上　→　出現回数を後ろにつけてSを出力とすればOKです。

連想配列(defaultdict)を知らない人は以下を確認してください。

defaultdict(連想配列)について
連想配列は別名「辞書」とも言い、「キー」と対応する「値」を登録できるデータ構造です。
pythonでは標準で搭載されており、dict()と書くことで使えます。
しかし標準のものはデフォルトの値(初期値)が設定できず、存在しない「キー」にアクセスする可能性があるときの処理が面倒です。
defaultdictは標準の連想配列と同様に使えて、さらに初期値を設定できます。
値の割当が行われていない「キー」には自動的に初期値が割り振られます。
「使い方」
・インポート：from collections import defaultdict
・作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
・キー、値の登録【O(1)】：変数名[キー]=値
・値の参照【O(1)】：変数名[キー]

使用例

# インポート：from collections import defaultdict
from collections import defaultdict

# 作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
AsArray=defaultdict(int)

# キー、値の登録【O(1)】：変数名[キー]=値
# キー、値ともに数値、文字列、タプルを入れることが可能
# ただしリストをキーにすることはできない
AsArray[1]=10
AsArray["Men"]="Taro"
AsArray[(1,2)]=[3,4,5]
 
# 値の参照【O(1)】：変数名[キー]
print(AsArray[1])
print(AsArray["Men"])
print(AsArray[(1,2)])

# 値が割当されていないキーも参照可能(値はデフォルト値)
print(AsArray[99])

【提出】

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

# defaultdictをインポート
from collections import defaultdict

# Sの出現回数を記録する連想配列
SCount=defaultdict(int)

# N回
for i in range(N):
    # 入力の受け取り
    S=input()

    # Sの出現回数が0回ならば
    if SCount[S]==0:
        # 何もつけずに出力
        print(S)
    # Sの出現回数が1回以上ならば
    else:
        # 出現回数とかっこをつけて出力
        print(S+"("+str(SCount[S])+")")
    # 出現回数をプラス1
    SCount[S]+=1

D - Flipping and Bonus　Dif:801

DPで解きます。

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

DPの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。

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

入力例1を例にして考えましょう。
N M：6 3
X：2 7 1 8 2 8
C1 Y1：2 10
C2 Y2：3 1
C3 Y3：5 5

(1)表を作る
今回作る表は
「i回目までのコイントスを行い、カウンタの値がkである場合の(i回目までの)最大金額」
とします。表の名前はdpとします。

例えばdp[3][2]=18であれば
「3回目までのコイントスを行い、カウンタの値が2である場合の(3回目までの)最大金額」が18円であることを表します。

(2)すぐにわかるところを埋める
すぐにわかるのはi=0の行です。
i=0の行は0回目までのコイントスを行った結果(つまりコイントスをしていない)なので当然最大金額は0円です。よってdp[0][0]=0となります。

ところでdp[0][1]やdp[0][2]はどうなるでしょうか。
dp[0][1]ならば「0回目までのコイントスを行い、カウンタの値が1である場合の(0回目までの)最大金額」となるわけですがコイントスの回数よりカウンタの値が多くなることは絶対にありません。
よってここには何も埋めないでおきましょう。(実装では便宜上0を埋めています)
ここからどんどん表を埋めておきますが同様にコイントスの回数よりカウンタの値が大きい場合、すなわちdp[i][k]でi<kとなっている部分は何も埋めません。

(3)表の小さい方から答えにたどり着くまで埋める
次にi=1の行を考えます。

dp[1][0]は「1回目までのコイントスを行い、カウンタの値が0である場合の(1回目までの)最大金額」ですから、1回目のコイントスが裏だった場合に相当します。
裏である場合はお金を受け取れないのでdp[1][0]=0となります。

dp[1][1]は「1回目までのコイントスを行い、カウンタの値が1である場合の(1回目までの)最大金額」ですから、1回目のコイントスが表だった場合に相当します。
この入力ではカウンタ1のときにボーナスはないのでX1＝2円を受け取って終わりです。すなわちdp[1][1]=2となります。

i=2の行へ進みます。
dp[2][0]は「2回目までのコイントスを行い、カウンタの値が0である場合の(2回目までの)最大金額」です。
これはどういう状況かというと、
・1回目のコイントスが表で、2回目のコイントスが裏
・1回目のコイントスが裏で、2回目のコイントスが裏
この2つが考えられます。
前者の場合は2円、後者の場合は0円を持っているので最大金額は2円、すなわちdp[2][0]=2となります。

dp[2][1]は「2回目までのコイントスを行い、カウンタの値が1である場合の(2回目までの)最大金額」です。
カウンタの値が1になるというのはカウンタ0の状態から表を出す他方法がありません。つまり1回前である1回目の時点でカウンタが0で、そこから表が出てカウンタが1になったということです。
1回目の時点でカウンタが0である場合の最大金額はdp[1][0]=0です。
更に2回目では表が出たのでX2=7円を受け取ることができます。
以上を式で書くと以下のようになります。
dp[2][1]=dp[1][0]+X[2]
計算するとdp[2][1]=7となります。

dp[2][2]は「2回目までのコイントスを行い、カウンタの値が2である場合の(2回目までの)最大金額」です。
同様に考え、カウンタの値が2になる⇔カウンタ1の状態から表を出すことになります。1回前である1回目の時点でカウンタが1で、そこから表が出てカウンタが2になったということです。
1回目の時点でカウンタが1である場合の最大金額はdp[1][1]=2です。
2回目では表が出たのでX2=7円を受け取ることができます。
そしてカウンタが2になるとボーナスが入ります。カウンタ2のボーナスは10円です。
以上を式で書くと以下のようになります。
dp[2][2]=dp[1][1]+X[2]+B[2]
※B[2]はカウンタが2のときのボーナスを表します。
計算するとdp[2][2]=19となります。

これを一般化して考えましょう。
・dp[i][0]
i回目で裏を出せばi回目のカウンタは0になります。i回目は裏なのでお金を受け取ることはできません。
よってi回目の最大金額は(i-1)回目までで受け取れる最大金額に等しくなります。
dp[i][0]=max(dp[i-1][0]~dp[i-1][N])

・(1≤k)dp[i][k]
(i-1)回目時点でカウンタの値が(k-1)である状態で、i回目に表を出せばi回目のカウンタはkになります。
このときXi円のお金を受け取れます。
もしカウンタkのときにボーナスがあればそれも受け取れます。
カウンタkのボーナスをB[k]とすれば以下の式で表せます。
dp[i][k]=dp[i-1][k-1]+X[i]+B[k]
※k回目のカウンタにボーナスがない場合はB[k]=0としておけば実装が楽です
ただしカウンタの値がコイントスの回数を超えることはないため、k≤iとなることに注意してください。

まとめると
・dp[0][0]=0
・(1≤i)dp[i][0]=max(dp[i-1][0]~dp[i-1][N])
・(1≤i,1≤k≤i)dp[i][k]=dp[i-1][k-1]+X[i]+B[k]
となります。

(4)答えを出力する
表を全て埋めると以下のようになります。

i=6行目の最大値、dp[6][3]=48が答えです。

pythonでは間に合わないのでpypyで提出します。

【提出】

# pypyで提出

# 入力の受け取り
N,M=map(int,input().split())
# X[0]はてきとうな値で埋めておく
X=[0]+list(map(int,input().split()))
# ボーナスの値(ボーナスない箇所は0)
B=[0]*(N+1)

# M回
for i in range(M):
    # 入力の受け取り
    C,Y=map(int,input().split())
    # カウンタCでY円ボーナス
    B[C]=Y

# (1)表を作る
# 「i回目までのコイントスを行い、カウンタの値がkである場合の(i回目までの)最大金額」
dp=[[0]*(N+1) for i in range(N+1)]

# i=1~N
for i in range(1,N+1):
    # k=0~i
    for k in range(i+1):
        # k=0の場合
        if k==0:
            dp[i][k]=max(dp[i-1])
        # 1≤kの場合
        else:
            dp[i][k]=dp[i-1][k-1]+X[i]+B[k]

# 答え：N行目の最大値
print(max(dp[N]))

【広告】

『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