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

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

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

https://qiita.com/sano192/items/54accd04df62242b70f0

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

# A Dif:13

https://atcoder.jp/contests/abc276/tasks/abc276_a

Sを1文字ずつ確認して、"a"があるかを確認していきます。
pythonではS[i]と書くことでSのi文字目を確認できます。
注意点としては左端が0文字目、次が1文字目、...となることです。例えばS="abcdef"ならS[0]="a",S[1]="b",...となります。

i=0,1,2,...について、S[i]="a"となっているか見ていきます。
for i in range(Sの文字数)
と書くことでi=0,1,2,...,(Sの文字数-1)と順に代入しながら処理ができます。
Sの文字数はlen(S)で確認できます。

S[i]="a"になっていれば答えとして(i+1)を記録します。(先頭が0文字目であるため、プラス1してずらします)
もし"a"が2つ以上あってもi=0,1,2,...の順に確認し、"a"が見つかったら答えを更新する、としていくことで最も右側にある"a"の位置を記録できます。

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

https://qiita.com/sano192/items/6361ed72106cb6dd5843#1-%E5%85%A5%E5%8A%9B%E3%81%A8%E5%87%BA%E5%8A%9B-abc205-a-dif6

**【提出】**

```python:
# 入力の受け取り
S=input()

# 答え
ans=-1

# i=0~(Sの文字数-1)
for i in range(len(S)):
    # S[i]="a"(Sのi文字目)ならば
    if S[i]=="a":
        # 答えに(i+1)を記録
        ans=i+1

# 答えの出力
print(ans)
```

# B Dif:143

https://atcoder.jp/contests/abc276/tasks/abc276_b

入力を二次元配列へ受け取ります。結ばれている都市の情報をconnectという二次元配列へ記録します。
例えば都市1と都市2,4,5が結ばれているなら
connect[1]=[2,4,5]
となるようにしたいです。

まず(N+1)個の空のリストが入ったリストconnectを作ります。
以下のように書きましょう。

```python:
connect=[[] for i in range(N+1)]
```

これで空のリスト([])が(N+1)個入ったリストができました。

A,Bを受け取って記録してきます。
AはBと繋がっている、BとAもつながっているので以下のようにそれぞれのリストに記録していきます。

```python:
A,B=map(int,input().split())
connect[A].append(B)
connect[B].append(A)
```

あとはconnect[1],connect[2],...をソートして長さと要素を出力すればOKです。

**【提出】**

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

# 繋がっている都市の記録
connect=[[] for i in range(N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int,input().split())
    # 記録
    connect[A].append(B)
    connect[B].append(A)

# i=1~N
for i in range(1,N+1):
    # ソート
    connect[i].sort()
    # 長さと、要素をつなげる
    ans=[len(connect[i])]+connect[i]
    # 出力(「*」をつけるとカッコなしで出力できる)
    print(*ans)
```

# C Dif:389

https://atcoder.jp/contests/abc276/tasks/abc276_c

適当に順列を作って眺めてみます。
N=4なら以下のようになります。
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

辞書順で1個前に戻すので、基本的にはできるだけ後ろ側を辞書順で前になるようにごちゃごちゃ並び替えしたいです。
後ろ2つが(4,1)になっていれば(1,4)にすればいいし、(3,2)になっていれば(2,3)にすればいいわけです。
後ろ2つが(1,4)になっていれば今度は3つ目まで見ます。(3,1,4)になっていれば(1,4,3)とします。これは3つの中で最も左の数3より小さく最も近い1を先頭に置いて、その後ろに残った3,4を大きい順に並べるということです。
後ろ2つが(1,2)になっていても同様に3つ目まで見ます。(4,1,2)になっていれば(2,4,1)にします。最も左の数4より小さく最も近い2を先頭に置いて、その後ろに残った1,4を大きい順に並べるということです。

一般に考えると、後ろから順に、ある要素から後ろが単調増加になっているかを確認していきます。
単調増加でなくなった要素はその要素より右にあるより小さい要素のうち、最も近いものと入れ替えて、残りを大きい順に並べます。

入力例2を見てみましょう。
9 8 6 5 10 3 1 2 4 7

(1,2,4,7)までは単調増加ですが、(3,1,2,4,7)は単調増加でなくなりました。
まず3より右にある3より小さい要素のうち、最も近いもの(=2)と入れ替えます。
9 8 6 5 10 2 1 3 4 7
さらに残った(1,3,4,7)を大きい順に並び替えます。
9 8 6 5 10 2 7 4 3 1

**【提出】**

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

# i=(N-2)~0 -1ずつ
for i in range(N-2,-1,-1):
    # 単調増加でないなら
    if A[i]>A[i+1]:
        
        # A[i]より小さく、差が最も小さいものを探す
        # d：A[i]との差
        # d=1,2,...,N
        for d in range(1,N):
            # k=(i+1)~(N-1)
            for k in range(i+1,N):
                # A[i]-A[k]=dならば
                if A[i]-A[k]==d:
                    # A[i]とA[k]を入れ替える
                    A[i],A[k]=A[k],A[i]
                    # x=A[0]~A[i]
                    x=A[:i+1]
                    # y=A[i+1]~A[N-1]
                    y=A[i+1:]
                    # 大きい順に並び替え
                    y.sort(reverse=True)
                    # つなげて出力(「*」をつけるとカッコなしで出力できる)
                    print(*x+y)
                    # 終了
                    exit()
```

# D Dif:645

https://atcoder.jp/contests/abc276/tasks/abc276_d

aの要素を2^x\*3^y\*zという形で表します(zは2でも3でも割れない数)
aiをai/2で置き換えるというのはすなわちxをマイナス1するということです。
aiをai/3で置き換えるというのはすなわちyをマイナス1するということです。
どうやってもzの部分は変えられません。

このように考えると
・zは全ての要素で同じでなければならない
・x,yは最も小さい要素に合わせればいい
ということがわかります。

例えば以下の例を考えます。
a：30 60 90 180
それぞれx,y,zを考えます。
30=2^1\*3^1\*5→(x,y,z)=(1,1,5)
60=2^2\*3^1\*5→(x,y,z)=(2,1,5)
90=2^1\*3^2\*5→(x,y,z)=(1,2,5)
180=2^2\*3^2\*5→(x,y,z)=(2,2,5)

まずzは全て5なのでOKです。
x,yの最小値はともに1です。
30⇔(x,y,z)=(1,1,5)：x,yともに最小値なので操作不要
60⇔(x,y,z)=(2,1,5)：xを1にするため操作1回
90⇔(x,y,z)=(1,2,5)：xを1にするため操作1回
180⇔(x,y,z)=(2,2,5)：xを1,yを1にするため操作2回

よって合計4回の操作が必要とわかります。

**【提出】**

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

# ai=2^x*3^y*z (x,y,z)の記録
xyz=[]

# i=0~(N-1)
for i in range(N):
    # xのカウント
    x=0
    # A[i]が2で割り切れる限り
    # ⇔2で割った余りが0
    while A[i]%2==0:
        # xをカウント
        x+=1
        # 2で割る
        A[i]//=2

    # yのカウント
    y=0
    # A[i]が3で割り切れる限り
    # ⇔3で割った余りが0
    while A[i]%3==0:
        # yをカウント
        y+=1
        # 3で割る
        A[i]//=3

    # 記録
    xyz.append([x,y,A[i]])

# zが同一か確認
# i=1~(N-1)
for i in range(1,N):
    # a0のz≠aiのz　ならば
    if xyz[0][2]!=xyz[i][2]:
        # 「-1」を出力
        print(-1)
        # 終了
        exit()

# xの最小
xmin=9999
# yの最小
ymin=9999

# i=0~(N-1)
for i in range(N):
    # より小さければ更新
    xmin=min(xmin,xyz[i][0])
    ymin=min(ymin,xyz[i][1])

# 答え
ans=0

# i=0~(N-1)
for i in range(N):
    # 操作回数=xと(xの最小)との差
    ans+=xyz[i][0]-xmin
    # 操作回数=yと(yの最小)との差
    ans+=xyz[i][1]-ymin

# 答えの出力
print(ans)
```

# E Dif:1058

https://atcoder.jp/contests/abc276/tasks/abc276_e

:::note info
本問はBFSの中でも比較的難しい問題です。
BFSを解いたことがない人はまずABC232Dに挑戦することをおすすめします。

ABC232D：https://atcoder.jp/contests/abc232/tasks/abc232_d
解説：https://qiita.com/sano192/items/3cb3ae52adae8829c94f#d---weak-takahashi
:::

Sから2つ移動した箇所を考えましょう。緑の部分です。
![ABC276E1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/700383/0edf4960-ebdb-1b39-e4b2-83609aed9a74.png)
ここからSへ戻る場合、どう頑張っても2回移動が必要です。すなわち合計で4回以上はかかります。

よって2回移動した場所をスタート地点として、そこからSへたどり着けるかを考えればOKです。
ただし1回目の移動で通ったマスは通れないので、そこは通ったマスとして記録します。

より具体的には
1回目：上→2回目：上
1回目：上→2回目：左
1回目：上→2回目：右
1回目：下→2回目：下
1回目：下→2回目：左
1回目：下→2回目：右
1回目：左→2回目：左
1回目：左→2回目：上
1回目：左→2回目：下
1回目：右→2回目：右
1回目：右→2回目：上
1回目：右→2回目：下
この12通りをスタート地点とします。

スタート地点からSへたどり着けるかはBFSで確認します。
BFSは幅優先探索(breadth first search)の略称で、グラフを探索するアルゴリズムです。

:::note info
**BFSの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。**
<iframe width="560" height="315" src="https://www.youtube.com/embed/WyJvs9hL9Yc" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
:::


(1)各マスが訪問済みかを確認する二次元配列Visitedを用意する(未訪問なら0,訪問済みなら1)
(2)1回目、2回目の移動で到達した地点を訪問済みにする
(3)キューにスタート地点(2回目の移動で到達した地点)を入れる
(4)キューから座標を取り出す(今いる座標)
(5)今いる座標の上下左右が壁または障害物でなく、かつ未訪問ならばキューに追加し、訪問済みにする
(6)キューが空になるまで(4)~(5)を繰り返す。

キューがわからない人は「dequeについて」を読んで下さい。

>**dequeについて**
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
インポート：from collections import deque
作成：変数名=deque()
先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
末尾(右端)に要素追加【O(1)】：変数名.append(要素)
先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()

【使用例】

```python:
# インポート：from collections import deque
from collections import deque

# 作成：変数名=deque()
que=deque()

# 先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
que.appendleft(1)

# 末尾(右端)に要素追加【O(1)】：変数名.append(要素)
que.append(3)

# 先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
x=que.popleft()

# 末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
y=que.pop
```
>詳しく知りたい人は以下のページを見てください。

https://note.nkmk.me/python-collections-deque/

**【提出】**

```python:
# dequeのインポート
from collections import deque

# BFS 1回目の移動(H1,W1) 2回目の移動(H2,W2)
def BFS(H1,W1,H2,W2):
    # 1回目、2回目の移動で到達するマスが壁でない(マス目の範囲内)なら
    if 0<=H1<H and 0<=H2<H and 0<=W1<W and 0<=W2<W:
        # 1回目、2回目の移動で到達するマスが障害物でない(「.」)なら
        if Grid[H1][W1]=="." and Grid[H2][W2]==".":

            # キューを用意
            que=deque()
            # (1)各マスが訪問済みかを確認する二次元配列Visitedを用意する(未訪問なら0,訪問済みなら1)
            Visited=[[0]*W for i in range(H)]
            # (2)1回目、2回目の移動で到達した地点を訪問済みにする
            Visited[H1][W1]=1
            Visited[H2][W2]=1
            # (3)キューにスタート地点(2回目の移動で到達した地点)を入れる
            que.append((H2,W2))

            # (6)キューが空になるまで(4)~(5)を繰り返す
            while que:
                # (4)キューから座標を取り出す(今いる座標)
                NowH,NowW=que.popleft()
                # (5)今いる座標の上下左右が壁または障害物でなく、かつ未訪問ならばキューに追加し、訪問済みにする
                # 上
                if 0<=NowH-1<H and 0<=NowW<W and (Grid[NowH-1][NowW]=="." or Grid[NowH-1][NowW]=="S")and Visited[NowH-1][NowW]==0:
                    # キューへ追加
                    que.append((NowH-1,NowW))
                    # 訪問済みにする
                    Visited[NowH-1][NowW]=1        
                # 下
                if 0<=NowH+1<H and 0<=NowW<W and (Grid[NowH+1][NowW]=="." or Grid[NowH+1][NowW]=="S") and Visited[NowH+1][NowW]==0:
                    que.append((NowH+1,NowW))
                    Visited[NowH+1][NowW]=1        
                # 左
                if 0<=NowH<H and 0<=NowW-1<W and (Grid[NowH][NowW-1]=="." or Grid[NowH][NowW-1]=="S")and Visited[NowH][NowW-1]==0:
                    que.append((NowH,NowW-1))
                    Visited[NowH][NowW-1]=1
                # 右
                if 0<=NowH<H and 0<=NowW+1<W and (Grid[NowH][NowW+1]=="." or Grid[NowH][NowW+1]=="S")and Visited[NowH][NowW+1]==0:
                    que.append((NowH,NowW+1))
                    Visited[NowH][NowW+1]=1        

            # Sが訪問済みならば
            if Visited[Sh][Sw]==1:
                # 「Yes」を出力
                print("Yes")
                # 終了
                exit()

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

# マス目の情報
Grid=[]

# i=0~(H-1)
for i in range(H):
    # Sを受け取り
    S=input()
    # リストに展開して追加
    Grid.append(list(S))

# h=0~(H-1)
for h in range(H):
    # w=0~(W-1)
    for w in range(W):
        # (h,w)がSなら
        if Grid[h][w]=="S":
            # 記録
            Sh,Sw=h,w

# 1回目：上→2回目：上
BFS(Sh-1,Sw,Sh-1-1,Sw)
# 1回目：上→2回目：左
BFS(Sh-1,Sw,Sh-1,Sw-1)
# 1回目：上→2回目：右
BFS(Sh-1,Sw,Sh-1,Sw+1)

# 1回目：下→2回目：下
BFS(Sh+1,Sw,Sh+1+1,Sw)
# 1回目：下→2回目：左
BFS(Sh+1,Sw,Sh+1,Sw-1)
# 1回目：下→2回目：右
BFS(Sh+1,Sw,Sh+1,Sw+1)

# 1回目：左→2回目：左
BFS(Sh,Sw-1,Sh,Sw-1-1)
# 1回目：左→2回目：上
BFS(Sh,Sw-1,Sh-1,Sw-1)
# 1回目：左→2回目：下
BFS(Sh,Sw-1,Sh+1,Sw-1)

# 1回目：右→2回目：右
BFS(Sh,Sw+1,Sh,Sw+1+1)
# 1回目：右→2回目：上
BFS(Sh,Sw+1,Sh+1,Sw+1)
# 1回目：右→2回目：下
BFS(Sh,Sw+1,Sh-1,Sw+1)

# 「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対象)**

<iframe width="560" height="315" src="https://www.youtube.com/embed/J_uaNYRuuZU" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

**【kindle】**
https://www.amazon.co.jp/dp/B09XLM42MW

**【booth(pdf】**
https://sano192.booth.pm/items/3785312