LoginSignup
2
1

More than 1 year has passed since last update.

@sano192

大和証券プログラミングコンテスト2022 Autumn(ABC277) A～E問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Last updated at Posted at 2022-11-22

大和証券プログラミングコンテスト2022 Autumn(AtCoder Beginner Contest277) A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

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

大和証券様について

新卒採用情報

キャリア採用情報

A Dif:17

(リスト).index(X)
と書くことで「Xが何番目にあるか」を確認することができます。
pythonは0インデックスであることに注意しましょう。
すなわち左端を0番目、次を1番目、...と数えるので、答えを出力するときは+1する必要があります。

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

【提出】

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

# Xが何番目にあるか確認して出力
# +1して番号をずらす
print(A.index(X)+1)

B Dif:60

「No」を出力するのは以下の3パターンです。
・Siの0文字目がH,D,C,Sでない
・Siの1文字目がA,2,3,4,5,6,7,8,9,T,J,Q,Kでない
・Siと同じ要素がある

リスト、または文字列にある要素が含まれるというのは
if (要素) in (リストまたは文字列):
で判定できます。逆に含まれないを判定したい場合はnotをつけて
if (要素) not in (リストまたは文字列):
となります。

Siを受け取ったら
・0文字目に「HDCS」が含まれて いない か
・1文字目に「A23456789TJQK」が含まれて いない か
をチェックします。これらどちらかになっていれば「No」です。

さらにそこまでに出てきたSiを記録したリストSlistを用意しておき
・SiがSlistに含まれるか
をチェックします。含まれていれば同じ要素があるということなので「No」です。

チェックが終わったらSiをSlistへ追加します。

N回のチェックが全て通ったら「Yes」を出力します。

【提出】

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

# Sの記録をするリスト
Slist=[]

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

    # Sの0文字目が「HDCS」に含まれないなら
    if S[0] not in "HDCS":
        # 「No」を出力
        print("No")
        # 終了
        exit()
    # Sの1文字目が「A23456789TJQK」に含まれないなら
    if S[1] not in "A23456789TJQK":
        # 「No」を出力
        print("No")
        # 終了
        exit()
    
    # SがSlistに含まれていれば
    if S in Slist:    
        # 「No」を出力
        print("No")
        # 終了
        exit()

    # SをSlistへ追加
    Slist.append(S)
    
# 「Yes」を出力
print("Yes")

C Dif:540

BFSを使います。
BFSは幅優先探索(breadth first search)の略称で、グラフを探索するアルゴリズムです。

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

まずはしごで繋がっている階をグラフで表してみます。
「入力例1の場合」
4
1 4
4 3
4 10
8 3

ABC277C1.png

これで頂点1から繋がっている頂点のうち、最も数字の大きい頂点を探すわけです。

まず繋がっている頂点の情報を格納するconnectという連想配列を作ります。
※制約が大きいのでリストで作るとMLE(メモリ制限超過)します。
頂点1から頂点2,3,4に行けるならconnect[1]=[2,3,4]となるように記録します。

更に訪問済みかどうかを記録するvisitedという連想配列を作ります。
visited[1]=0なら頂点1は未訪問、=1なら訪問済みという形です。

ここからBFSを始めます。
(1)キューに頂点1(スタート地点)を追加、頂点1を訪問済みにする
(2)キューから頂点を取り出す
(3)それまでに到達した最も大きい頂点の番号より今いる頂点の番号が大きければ答えを更新
(4)今いる頂点から行ける頂点が未訪問なら訪問済みにして、キューへ追加
(5)キューが空になるまで(2)～(4)を繰り返す

defaultdict(連想配列)、dequeについてわからない人は以下を御覧ください。

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])

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

【使用例】

# インポート：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

詳しく知りたい人は以下のページを見てください。

【提出】

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

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

# 繋がっている頂点の記録(初期値は空のリスト)
connect=defaultdict(list)

# N回
for i in range(N):
    # 入力の受け取り
    A,B=map(int,input().split())
    # AとBが繋がっている
    connect[A].append(B)
    # BとAが繋がっている
    connect[B].append(A)

# キューを用意
que=deque()

# 訪問済みかどうかのチェック(初期値は0)
# 未訪問なら0、訪問済みなら1
visited=defaultdict(int)

# (1)キューに頂点1(スタート地点)を追加、頂点1を訪問済みにする
# スタート地点の1を追加
que.append(1)
# 1を訪問済みにする
visited[1]=1

# 答え
ans=1

# (5)キューが空になるまで(2)～(4)を繰り返す
while 0<len(que):
    # (2)キューから頂点を取り出す
    # 今いる頂点(階数)
    now=que.popleft()

    # (3)それまでに到達した最も大きい頂点の番号より今いる頂点の番号が大きければ答えを更新
    ans=max(ans,now)

    # (4)今いる頂点から行ける頂点が未訪問なら訪問済みにして、キューへ追加
    # to：今いる頂点から行ける頂点
    for to in connect[now]:
        # 行ける頂点が未訪問なら
        if visited[to]==0:
            # 訪問済みにする
            visited[to]=1
            # キューへ追加
            que.append(to)

# 答えの出力
print(ans)

D Dif:873

入力例1で考えます。
9 7
3 0 2 5 5 3 0 6 3

なにはともあれソートしましょう。数列が出てきたとき、ソートしても答えが変わらないならとりあえずソートです。

A：0 0 2 3 3 3 5 5 6

同じ数字は続けて置くことができます。更に2,3や5,6など繋がっている数字も出せます。
(例えば最初に2を出すと、2の次に3を3枚続けて出せます)
これを踏まえて繋がっている数字のグループに分けます。
[0,0],[2,3,3,3],[5,5,6]
更に(X+1) mod Mの数も出せるという条件から、6の次には6+1 mod 7=0も出せます。よって[0,0]と[5,5,6]を同じグループにします。
[2,3,3,3],[5,5,6,0,0]
このグループが出せる手札です。
Aの合計は27で、
[2,3,3,3]の合計は11⇔全て出すと27-11=16
[5,5,6,0,0]の合計は16⇔全て出すと27-16=11
よってより小さい方、[5,5,6,0,0]を出して11が答えになります。

実装ではまずAの各要素からグループを作り、
グループの最も小さい要素が0　かつ　グループの最も大きい要素+1=M
ならば同じグループにします。
リスト[-1]と書くと最も右にある要素を参照できます。

【提出】

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

# Aをソート
A.sort()

# グループ分け
G=[[A[0]]]

# i=1~N
for i in range(1,N):
    # グループの右端の要素=A[i] または グループの右端の要素+1=A[i]
    if G[-1][-1]==A[i] or G[-1][-1]+1==A[i]:
        # 同じグループに追加
        G[-1].append(A[i])
    # そうでない
    else:
        # 新しいグループを追加
        G.append([A[i]])

# グループの要素が2個以上 かつ グループの最も小さい要素が0 かつ グループの最も大きい要素+1=M
if 2<=len(G) and G[0][0]==0 and G[-1][-1]+1==M:
    # 連結したグループ
    k=G[0]+G[-1]
    # 0の入っているグループを消す
    G.pop(0)
    # 最も大きい要素(M-1)の入っているグループを消す
    G.pop()
    # 連結したグループを追加
    G.append(k)
    
# Aの合計
Asum=sum(A)

# 答え
ans=10**15

# g：グループの各要素を格納
for g in G:
    # Aの合計-(グループの合計)を計算
    # より小さければ答えを更新
    ans=min(ans,Asum-sum(g))

# 答えの出力
print(ans)

E Dif:1183

ダイクストラ法で解きます。

ai=1の頂点が通行可能であることを「状態1」、ai=0の頂点が通行可能であることを「状態0」と表します。

まずそれぞれの頂点を「状態1」と「状態0」それぞれの場合で2つずつ作ります。

入力例1で考えましょう。
5 5 2
1 3 0
2 3 1
5 4 1
2 1 1
1 4 0
3 4
ABC277E1.png

黒いものは「状態1」の頂点、赤いものは「状態0」の頂点を表します。
スイッチがついているのは頂点3,4で、スイッチを押すことで状態が違う頂点へ移動できるので黒の頂点3,4と赤の頂点3,4は繋がっているわけです。
次に各辺に移動にかかるコスト(すなわち移動回数としてカウントされる値)を書き込みます。

頂点間の移動はコスト1、スイッチを押したときの状態の変化(黒⇔赤)はコスト0となります。
ABC277E2.png

あとは頂点1(黒)からの最短距離、すなわちその頂点へ移動するまでの最小移動回数を書き込みます。
ABC277E3.png

頂点5(黒)は5、(赤)は到達不能です。到達したときの状態はどちらでもよいので答えは5となります。
両方に到達可能なら小さい方を出力します。

実装ではダイクストラ法で最短距離を書き込んでいきます。
「状態1」の頂点(黒)は頂点1,2,3,...
「状態0」の頂点(赤)は頂点1000001(=頂点1の状態0),1000002(=頂点2の状態0),1000003(=頂点3の状態0),...と、10^6を足した形で表すと実装が楽にできます。
例えば
u,v,a=2,3,1ならば頂点2と頂点3がコスト1で移動できる
u,v,a=1,3,0ならば頂点1000001と頂点1000003がコスト1で移動できる
と記録します。

スイッチを切り替えできるsの要素については黒の頂点と赤の頂点をコスト0で移動できると記録します。
例えば
si=3ならば頂点3と頂点1000003がコスト0で移動できる
と記録します。

ダイクストラ法の基本的なアイデアは以下です。
移動距離確定していない頂点のうち、最も数字が小さいものを確定させる
↓
確定した頂点から行ける頂点に移動距離を書き込んでいく
※最も数字が小さい頂点というのはどう頑張ってもそれ以上小さい移動回数で到達できないから確定してよいということです

より詳細には以下の動画がわかりやすいです。

最も小さい移動距離の頂点を探すときはheap queueを使うことで計算量を小さくできます。
heapには(距離,頂点番号)の順で格納しましょう。こうすることで先頭の要素(=距離)が小さい順に頂点を取り出せます。

heapについて
heapはリストから最小値をO(logN)で取り出せるデータ構造です。
import：import heapq
リストのheap化 O(N)：heapify(リスト)
要素の追加 O(logN)：heappush(リスト,要素)
最小値の参照 O(1)：リスト[0]
最小値の取り出し O(logN)：heappop(リスト)
【使用例】

# インポート
import heapq

# リストを用意
que=list()

# リストのheap化 O(N)：heapify(リスト)
heapq.heapify(que)

# 要素の追加 O(logN)：heappush(リスト,要素)
heapq.heappush(que, 6)
heapq.heappush(que, 1)

# 最小値の参照 O(1)：リスト[0]
print(que[0])

# 最小値の取り出し O(logN)：heappop(リスト)
min_x=heapq.heappop(que)

詳しく知りたい人は以下のページを見てください。

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

【提出】

# pypyで提出

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

# 繋がっている頂点とコスト(移動回数へのカウント)を記録
edge=[[] for i in range(10**6+N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    u,v,a=map(int,input().split())
    # a=1の場合
    if a==1:
        # 頂点v(黒)⇔頂点u(黒)へコスト1で移動できる
        edge[u].append([v,1])
        edge[v].append([u,1])
    # それ以外(a=0)の場合
    else:
        # 10^6を足す
        u+=10**6
        v+=10**6
        # 頂点v(赤)⇔頂点u(赤)へコスト1で移動できる
        edge[u].append([v,1])
        edge[v].append([u,1])

# 0<Kならば
if 0<K:
    # sの受け取り
    s=list(map(int,input().split()))
    # i=0~(K-1)
    for i in range(K):
        # 頂点s[i](黒)⇔頂点s[i](赤)へコスト0で移動できる
        edge[s[i]].append([s[i]+10**6,0])
        edge[s[i]+10**6].append([s[i],0])

# heapqをインポート
import heapq

# キューへスタート地点(頂点1(黒))を追加
# (距離(頂点1からの移動回数),頂点番号)の順に記録する
que=[[0,1]]

# 到達不能距離(距離の初期値)
inf=10**6

# 頂点1からの距離
dist=[inf]*(10**6+N+1)

# 距離が確定しているかのフラグ
# confirmed[3]=1ならば頂点3の距離は確定、=0なら確定していない
confirmed=[0]*(10**6+N+1)

# 頂点1の距離は0
dist[1]=0

# キューが空になるまで
while 0<len(que):

    # 今いる頂点の距離,今いる頂点番号を取り出し
    NowDist,NowPlace=heapq.heappop(que)

    # 今いる頂点の距離が確定しているなら
    if confirmed[NowPlace]==1:
        # 次へ
        continue

    # 確定させる
    confirmed[NowPlace]=1

    # 今いる頂点から行ける頂点とコスト
    for ToPlace,cost in edge[NowPlace]:
        # 今いる頂点の距離+コスト<行ける頂点の距離ならば
        if NowDist+cost<dist[ToPlace]:
            # 距離を更新
            dist[ToPlace]=NowDist+cost
            # キューへ追加
            heapq.heappush(que,[NowDist+cost,ToPlace])

# 頂点N(黒)と頂点N(赤)の距離が更新されていなければ
if dist[N]==inf and dist[N+10**6]==inf:
    # 「-1」を出力
    print(-1)
# そうでなければ
else:
    # 頂点N(黒)と頂点N(赤)の距離のうち小さい方を出力
    print(min(dist[N],dist[N+10**6]))

【広告】

『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

2
1
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
2
1