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

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

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

A - Blood Pressure

入力を受け取り、問題文のとおりに計算して出力すればOKです。
※入力例1の場合、出力例1が「110」なのに自分で書いたコードが「110.0」を出力して不安になった人がいるかもしれませんが、「110」と「110.0」は同じものとみなされるので問題ありません。

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

【提出】

# 入力を受け取る
A,B=map(int, input().split())
# Cを計算する
C=(A-B)/3+B
# Cを出力する
print(C)

B - Cycle Hit

問題文の通り、H,2B,3B,HR がそれぞれ1つずつあるか確認しましょう。
入力を受け取り、どれにあたるかを変数で管理します。(あったら変数=1にします)
受け取り終わったら全部が1になっているか確認します。
※「2B」があるか確認する変数名は2Bとしたいところですが変数名の最初を数字にすることはできないため、しかたなくB2にしています。B3も同様です。

【提出】

# それぞれ存在するか確認する変数(存在しない=0,存在する=1)
H=0
B2=0
B3=0
HR=0

# 一行ずつ受け取り
for i in range(4):
    # 入力を受け取る
    S=input()
    # 入力が一致したものを1へ変更
    if S=="H":H=1
    if S=="2B":B2=1
    if S=="3B":B3=1
    if S=="HR":HR=1

# 全部1ならば
if H==1 and B2==1 and B3==1 and HR==1:
    # Yesを出力
    print("Yes")
# そうでないならば
else:
    # Noを出力
    print("No")

C - chokudai

DPを使って解きます。

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

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

(1)表を作る
今回は二次元の表を作ります。
具体的には「Sのi文字目までを使って、chokudaiのj文字目までを作る方法の数」とします。

具体例を見ましょう。
入力例1を使って説明します。
S=chchokudai
表は以下のようになります。

i=0,j=0については0文字目という意味ですので何もありません。ここでは「×」(バツ)としておきます。
(chokudaiのcは1文字目とします)

(2)すぐにわかるところを埋める
j=0の列はどういう意味でしょうか。
表は「Sのi文字目までを使って、chokudaiのj文字目までを作る方法の数」ですからj=0ということは
「Sのi文字目までを使って、chokudaiの0文字目までを作る方法の数」
となります。
chokudaiの0文字目は何もありませんから、なにも使わないという方法が1個ある、つまり全て1とします。

次にi=0の行を考えます。
表は「Sのi文字目までを使って、chokudaiのj文字目までを作る方法の数」ですからi=0ということは
「Sの0文字目までを使って、chokudaiのj文字目までを作る方法の数」
となります。
Sを1文字も使えないならば作りようがないので0です。
ゆえにi=0の場合は0です。(ただしi=0,j=0の場合は1です)

表を埋めると以下のようになります。

(3)表の小さい方から答えにたどり着くまで埋める
「Sのi文字目までを使って、chokudaiのj文字目までを作る方法の数」を求めたいです。
ここで表における今埋めようとしている場所の上、左部分は全て埋まっているとします。

・Sのi文字目≠chokudaiのj文字目の場合
　Sのi文字目は使えないので
　「Sのi-1文字目までを使って、chokudaiのj文字目までを作る方法の数」=「Sのi-1文字目までを使って、chokudaiのj文字目までを作る方法の数」
　となります。

・Sのi文字目=chokudaiのj文字目の場合
　Sのi文字目を使わない場合=「Sのi-1文字目までを使って、chokudaiのj文字目までを作る方法の数」
　Sのi文字目を使う場合=「Sのi-1文字目までを使って、chokudaiのj-1文字目までを作る方法の数」
　となります。

以上を踏まえ、dp[i][j]=「Sのi文字目までを使って、chokudaiのj文字目までを作る方法の数」とした時、以下の式が成り立ちます。
・j=0
　dp[i][j]=1
・i=0,1≤j≤8
　dp[i][j]=0
・i=0,1≤j≤8
　Sのi文字目≠chokudaiのj文字目の場合
　　dp[i][j]=dp[i-1][j]
　Sのi文字目=chokudaiのj文字目の場合
　　dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
　
大体の人が何を言っているかわからないと思うので具体例で説明します。
今途中まで表が埋まっているとします。

i=4,j=2、すなわち
「Sの4文字目までを使って、chokudaiの2文字目まで(=ch)を作る方法の数」
を考えます。

・Sの4文字目を使わない場合
Sの3文字目まででchokudaiの2文字目まで(=ch)を作った方法はそのまま使えます。
つまりi=3,j=2の値(dp[3][2])→1通りは作れます。
(Sの4文字目を使って、ではなくSの4文字目までを使って、というところに注意してください。3文字目までだけを使っても構わないということです)

・Sの4文字目を使う場合
Sの4文字目はhなので、chokudaiの1文字目まで(=c)を作ったものにhをくっつければchokudaiの2文字目まで(=ch)を作ることができます。
つまり「Sの3文字目までを使って、chokudaiの1文字目(=c)までを作る方法の数」でcを作ったものにhをくっつければ良いわけです。
ゆえにi=3,j=1の値(dp[3][1])→2通りをプラスします。

まとめると
Sの4文字目=chokudaiの2文字目であるから
dp[4][2]=dp[3][2]+dp[3][1]=3
(dp[i][j]=dp[i-1][j]+dp[i-1][j-1])
となります。

もうひとつ例を見ましょう
i=5,j=2、すなわち
「Sの5文字目までを使って、chokudaiの2文字目まで(=ch)を作る方法の数」
を考えます。

・Sの5文字目を使わない場合
Sの4文字目まででchokudaiの2文字目まで(=ch)を作った方法はそのまま使えます。
つまりi=4,j=2の値(dp[4][2])→3通りは作れます。
(Sの5文字目を使って、ではなくSの5文字目までを使って、というところに注意してください。4文字目までだけを使っても構わないということです)

・Sの5文字目を使う場合(使えない)
Sの5文字目はoなので、chokudaiの2文字目と違います。ゆえにchokudaiの1文字目まで(=c)を作ったものにoをくっつけて・・・というやり方は使えません。
5文字目は使えないので0通りです。

まとめると
Sの4文字目≠chokudaiの2文字目であるから
dp[5][2]=dp[4][2]=3
(dp[i][j]=dp[i-1][j])

表をすべて埋めると以下のようになります。

(4)答えを出力する
答えは「Sの10文字目までを使って、chokudaiの8文字目まで(=chokudai)を作る方法の数」
ですから、dp[10(Sの文字数)][8]=3となります。

【提出】

# 入力の受け取り
S=input()
# 文字数=N
N=len(S)
# Sの0文字目を?にする
S="?"+S
# T=?chokudai(?は0文字目)
T="?chokudai"
# 余りの定義
mod=10**9+7
# dp表を作る
dp=[[0]*9 for i in range(N+1)]

# Sのi文字目までを使う
for i in range(N+1):
    # chokudaiのj文字目までを作る
    for j in range(9):
        # j=0(chokudaiの0文字目までを作る→1通り)
        if j==0:
            # 1通り
            dp[i][j]=1
        # j=1~8
        else:
            # i=0(Sの0文字目までを使う→使える文字なし)
            if i==0:
                # 作りようがないから0
                dp[i][j]=0
            # i=1～N
            else:
                # もしSのi文字目とchokudaiのj文字目が違うなら
                if S[i]!=T[j]:
                    # Sのi-1文字目までを使ってchokudaiのj文字目を作る場合と同じ数
                    dp[i][j]=dp[i-1][j]
                # もしSのi文字目とchokudaiのj文字目が同じなら
                else:
                    # dp[i-1][j]：Sのi-1文字目までを使ってchokudaiのj文字目を作る場合(Sのi文字目を使わない)
                    # dp[i-1][j-1]：Sのi-1文字目までを使ってchokudaiのj-1文字目を作る場合(Sのi文字目を使う)
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
    # 余りを取る
    dp[i][j]%=mod

# SのN文字目までを使ってchokudaiの8文字目までを作る方法の数
print(dp[N][8])

D - Number of Shortest paths

BFS(幅優先探索)を使います。

BFSの細かい実装方法については動画で詳しく説明しているのでそちらも御覧ください。

各頂点についてBFSで回りながら
・訪問済みか？
・最短距離はいくらか？
・そこにいたるまでの経路数はいくらか？
を管理、更新していきます。

具体的には以下の手順です。
スタート地点1について
○訪問済みにします
○距離を0とします
○経路数を1とします

キューに1を入れます。

(1)キューの左端を取り出します(今いる場所)
(2)今いる場所から行ける場所を確認します。
　・行ける場所が未訪問ならば(初めて来たならば)
　　○行ける場所の経路数=今いる場所の経路数　と更新
　　○行ける場所の距離=今いる場所までの距離+1
　　○行ける場所を訪問済みにする
　　○キューに行ける場所を追加

　・行ける場所が訪問済みならば
　　・行ける場所に書いている距離=今いる場所の距離+1ならば(最短経路ならば)
　　　○行ける場所の経路数に今いる場所の経路数を足す

(1)(2)をキューが空になるまで繰り返します。

・行ける場所が訪問済みならば・・・の部分が分かりづらいと思いますので例で説明します。
(入力例1)
今1,2,3は訪問済みで、次に2→4への探索を行おうとしているとします。
c：経路数
d：距離
赤チェック：訪問済み

4は未訪問なので
　　行ける場所の経路数=今いる場所の経路数　と更新(今いる場所2の経路数=1に更新)
　　行ける場所の距離=今いる場所までの距離+1(今いる場所2の距離+1=2に更新)
　　行ける場所を訪問済みにする(赤チェック)
　　キューに行ける場所を追加(4追加)
として、以下のようになります。

さらに3→4への探索を行う場合、今度は4は訪問済みです。(赤チェックがついています)
　・行ける場所が訪問済みならば
　　・行ける場所に書いている距離=今いる場所の距離+1ならば(最短経路ならば)
　　　(今いる場所3の距離+1=2→4に書いている距離と同じ)
　　　行ける場所の経路数に今いる場所の経路数を足す(3に書いている経路数1+4に書いている経路数1=2)
よって以下のように更新されます。

簡単にいうと、一度行ったことがある場所に再度たどり着いたら、
距離からそのルートは最短経路か確認→最短経路なら経路の数をプラス
ということを繰り返しています。

実装における deque や while 0<len(que) や for to in connect[now]: の部分がよくわからないという人は上記動画で確認してください。

【提出】

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

# 道路の情報を格納する変数
connect=[[] for i in range(N+1)]
# つながっている道路の情報を受け取って格納
for i in range(M):
    A,B=map(int, input().split())
    connect[A].append(B)
    connect[B].append(A)

# あまりの定義
mod=10**9+7

# 訪問済みか記録するリスト　Falseなら未訪問、Trueなら訪問済み
visited=[False]*(N+1)
# 1を訪問済みにする
visited[1]=True

# 1からの距離を記録するリスト
dist=[0]*(N+1)

# そこに至るまでの経路数を記録するリスト
count=[0]*(N+1)
# 1に行く方法は1通り
count[1]=1

# キューを用意
from collections import deque
que=deque()
# キューに1を入れる
que.append(1)

# キューが空になるまで
while 0<len(que):
    # now＝今いる場所　をキューから取り出す
    now=que.popleft()
    # nowから行ける場所を順にtoへ格納
    for to in connect[now]:
        # もしtoが未訪問ならば(初めてきたならば)
        if visited[to]==False:
            # toに到達する経路の数=nowに到達する経路の数
            count[to]=count[now]
            # あまりを取る
            count[to]%=mod
            # 距離を今いる場所までの距離+1とする
            dist[to]=dist[now]+1
            # 訪問済みにする
            visited[to]=True
            # キューに入れる
            que.append(to)
        # toが訪問済みならば
        else:
            # toまでの距離=今いる場所の距離+1(最短経路ならば)
            if dist[to]==dist[now]+1:
                # toに到達する経路の数にnowに到達する経路の数をプラス
                count[to]+=count[now]
                # あまりを取る
                count[to]%=mod

# Nが未訪問であれば
if visited[N]==False:
    # たどり着けないため0を出力
    print(0)
# そうでないならば(Nが訪問済みならば)
else:
    # count[N]を出力
    print(count[N])

【広告】

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