ABC276(AtCoder Beginner Contest276) A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
更新時はツイッターにて通知します。
https://twitter.com/AtCoder4
A Dif:13
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"の位置を記録できます。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
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
入力を二次元配列へ受け取ります。結ばれている都市の情報をconnectという二次元配列へ記録します。
例えば都市1と都市2,4,5が結ばれているなら
connect[1]=[2,4,5]
となるようにしたいです。
まず(N+1)個の空のリストが入ったリストconnectを作ります。
以下のように書きましょう。
connect=[[] for i in range(N+1)]
これで空のリスト([])が(N+1)個入ったリストができました。
A,Bを受け取って記録してきます。
AはBと繋がっている、BとAもつながっているので以下のようにそれぞれのリストに記録していきます。
A,B=map(int,input().split())
connect[A].append(B)
connect[B].append(A)
あとはconnect[1],connect[2],...をソートして長さと要素を出力すればOKです。
【提出】
# 入力の受け取り
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
適当に順列を作って眺めてみます。
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
【提出】
# 入力の受け取り
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
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回の操作が必要とわかります。
【提出】
# 入力の受け取り
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
本問はBFSの中でも比較的難しい問題です。
BFSを解いたことがない人はまずABC232Dに挑戦することをおすすめします。
ABC232D：https://atcoder.jp/contests/abc232/tasks/abc232_d
解説：https://qiita.com/sano192/items/3cb3ae52adae8829c94f#d---weak-takahashi
Sから2つ移動した箇所を考えましょう。緑の部分です。
ここから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)の略称で、グラフを探索するアルゴリズムです。
BFSの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。
(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()
【使用例】
# インポート：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
詳しく知りたい人は以下のページを見てください。
【提出】
# 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対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb
【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW
【booth(pdf】
https://sano192.booth.pm/items/3785312