目指せ水色コーダー！！！！！！
ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。
こちらの記事の初中級者が解くべき過去問精選 100 問
をPythonで解いていきます！
@e869120さんに感謝！！！！！！
###過去記事リンク
全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
全探索：順列全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】
二分探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】
深さ優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】
幅優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】
#「Part7」〜幅優先探索(BFS)編〜
以下の6問を解いていきます！
#####幅優先探索
28 ALDS_11_C - 幅優先探索 基本問題です。
29 AtCoder Beginner Contest 007 C - 幅優先探索 重み無しグラフの最短経路問題は、幅優先探索で解けます。
30 JOI 2011 予選 5 - チーズ
31 JOI 2012 予選 5 - イルミネーション 少し実装が重いですが、頑張れば解けます。
32 AOJ 1166 - 迷図と命ず 実装が少し重いです。
33 AtCoder Beginner Contest 088 D - Grid Repainting これが解ければ、幅優先探索に慣れたと思って良いです。
#BFSの前提知識
・以下の2点を前提として、記事を書いていきます！
①DFSがある程度理解できていること
BFSの実装方法はDFSの実装方法とほぼ同じです!
(スタックの代わりにキューを使うだけ！)
まずは、DFSを理解しましょう！
深さ優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】
②BFSについて
けんちょんさんの記事
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
を読んで、BFSについて雰囲気理解する！
（重みなし）グラフの最短経路問題にも活躍するのがBFS！！！
①②の前提があれば、あとは実際に手を動かせば身につきます！！！
BFSの実装方法はDFS同様に
家政婦は見た！(seen)と「キュー」に入れるだけ
です！
(何言ってるかわからない人は過去記事参照！)
BFSはスタックでしたが、DFSはキューに入れて、
キューから取り出す時は、popleft()です！
min_distを変数として作っておきましょう〜
案外簡単に実装できました！！！
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
u,k,*v = x
for y in v:
graph[u].append(y)
seen = [0]*(n+1) #1_indexed
min_dist = [-1]*(n+1) #1_indexed
queue = collections.deque() #頂点NOを入れておく
def bfs():
seen[1] = 1
queue.append(1)
min_dist[1] = 0
while queue:
q_NO = queue.popleft()
q_dist = min_dist[q_NO]
if not graph[q_NO]:
continue
g = graph[q_NO]
for _ in range(len(g)):
g_NO = g.popleft()
if seen[g_NO]:
continue
seen[g_NO] = 1
queue.append(g_NO)
min_dist[g_NO] = q_dist+1
bfs()
for i,ans in enumerate(min_dist[1:],1):
print(i,ans)
#29 AtCoder Beginner Contest 007 C
Difficulty:1003
典型的な最短経路問題ですね！
DFSのグリッドブラフ問題とほぼ一緒ですね〜
この問題もすらすら実装できました！
import collections,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
R,C = LI()
sy,sx = [i-1 for i in LI()]
gy,gx = [i-1 for i in LI()]
c = [S() for _ in range(R)]
drdc = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*C for _ in range(R)]
seen = [[0]*C for _ in range(R)]
queue = collections.deque() #位置[行,列]を入れておく
def bfs():
seen[sy][sx] = 1
queue.append([sy,sx])
min_dist[sy][sx] = 0
while queue:
qr,qc = queue.popleft()
for dr,dc in drdc:
nr,nc = qr+dr,qc+dc
if c[nr][nc]=='#' or seen[nr][nc]:
continue
if [nr,nc]==[gy,gx]:
return min_dist[qr][qc]+1
seen[nr][nc] = 1
queue.append([nr,nc])
min_dist[nr][nc] = min_dist[qr][qc]+1
print(bfs())
#30 JOI 2011 予選 5 - チーズ
こちらも問題が少し複雑になっただけで、考え方は前の問題と全く同じですね〜
この問題も難なくとけました〜
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W,N = LI()
area = [S() for _ in range(H)]
ans = 0
S_factory_point = [[-1,-1] for _ in range(N+1)] #1_indexed
for h,w in itertools.product(range(H),range(W)):
if area[h][w]=='S':
S_factory_point[0] = [h,w]
if area[h][w] in list(map(str,list(range(1,N+1)))):
S_factory_point[int(area[h][w])] = [h,w]
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
def bfs(sh,sw,target_factory_NO):
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() #位置[行,列]を入れておく
seen[sh][sw] = 1
queue.append([sh,sw])
min_dist[sh][sw] = 0
while queue:
qh,qw = queue.popleft()
for dh,dw in dhdw:
nh,nw = qh+dh,qw+dw
if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or area[nh][nw]=='X':
continue
if [nh,nw]==S_factory_point[target_factory_NO]:
return min_dist[qh][qw]+1
seen[nh][nw] = 1
queue.append([nh,nw])
min_dist[nh][nw] = min_dist[qh][qw]+1
for i in range(N):
sh,sw = S_factory_point[i]
ans += bfs(sh,sw,i+1)
print(ans)
#31 JOI 2012 予選 5 - イルミネーション
初見で解けませんでした！！！
これは地図の外側からぬりつぶすという発想が思いつかなかった！
これまでのグリッドグラフ問題は左・右・上・下の4方向だけだったけど、
今回の問題は六角形なので6方向！
解説をみて確かに4方向と同じ考えができて、壁にぶつかる=壁面と考えられる！
あと、解説を見た後に実装してみても入出力例と答えが合わなかった・・・
原因は、上下1行の余白ではなく上下2行(偶数行)の余白が必要だったこと！
（奇数行と偶数行が整合性取れなくなるわけですね・・・）
難しかったけど、いい問題でした！！！勉強になりました！！！
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
W,H = LI()
sub_area = [[0]+LI()+[0] for _ in range(H)]
area = [[0]*(W+2)]+[[0]*(W+2)]+sub_area+[[0]*(W+2)]+[[0]*(W+2)]
dhdw_even = [[-1,0],[-1,1],[0,-1],[0,1],[1,0],[1,1]]
dhdw_odd = [[-1,-1],[-1,0],[0,-1],[0,1],[1,-1],[1,0]]
seen = [[0]*(W+2) for _ in range(H+4)]
queue = collections.deque() #位置[行,列]を入れておく
def bfs():
ans = 0
seen[0][0] = 1
queue.append([0,0])
while queue:
qh,qw = queue.popleft()
for dh,dw in dhdw_even if qh%2==0 else dhdw_odd:
nh,nw = qh+dh,qw+dw
if not(0<=nh<=(H+4)-1) or not(0<=nw<=(W+2)-1) or seen[nh][nw]:
continue
if area[nh][nw]==1:
ans += 1
continue
seen[nh][nw] = 1
queue.append([nh,nw])
return ans
print(bfs())
こちらも初見で解けませんでした！！！
これは具体的にノートとペンを用意しながら頑張ったけどきつかった！
諦めて、できる人のコードを見ました！
まず、
上か下なら横に動かないので、縦壁は無視して考えることができる！
（左右も同様に、横壁は無視して考えることができる！）
あとは、
上や左の時と、下や右の時で、壁があるかのチェックする条件が違う！
上の時は、nhのインデックスで壁があるかのチェックを行うが、
下の時は、nh-1（もともとの場所！）のインデックスで壁があるかのチェックを行う！
(左右も同様に、右の時は、nw-1（もともとの場所！）のインデックスで壁があるかのチェックを行う！)
難しかった！
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
w,h = LI()
if w==h==0:
break
hwall,wwall = [],[]
for i in range(2*h-1):
hwall.append(LI()) if i%2==0 else wwall.append(LI())
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*w for _ in range(h)]
seen = [[0]*w for _ in range(h)]
queue = collections.deque() #位置[行,列]を入れておく
def bfs():
seen[0][0] = 1
queue.append([0,0])
min_dist[0][0] = 1
while queue:
qh,qw = queue.popleft()
for dh,dw in dhdw:
nh,nw = qh+dh,qw+dw
if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw]:
continue
if (dh==-1 and wwall[nh][nw]==1) or (dh==1 and wwall[nh-1][nw]==1):
continue
if (dw==-1 and hwall[nh][nw]==1) or (dw==1 and hwall[nh][nw-1]==1):
continue
if [nh,nw]==[h-1,w-1]:
return min_dist[qh][qw]+1
seen[nh][nw] = 1
queue.append([nh,nw])
min_dist[nh][nw] = min_dist[qh][qw]+1
print(bfs() or 0)
補足
print(bfs() or 0)
このorは、戻り値がNoneとかなら、 0を返してくれます！
(つまり、return min_dist[qh][qw]+1が帰ってこなかった！
= 右下までたどり着けなかった場合に0を返します！)
ちなみに、BFSとは関係ないどうでも良いところではまったw
デバッグ中、コードは正しいつもりなのに、無限ループしてしまう・・・
原因は、
最後の方のseen[nh][nw] = 1が
seen[nh][nw]==1と==になっていたことでした・・・
しょうもないけど、この原因みつけるのにかなりの時間潰したw
（if文の条件の書き方が間違ってるんじゃないかと疑ったりしてたら、時間がどんどん過ぎていった）
コードも長いので、バグが起きた時にどこが原因か突き詰めるにも時間がかかってくる！
でも難しい問題はもっとコードの量も多くなるだろうから、
こんなところではくじけない！！！
#33 AtCoder Beginner Contest 088 D - Grid Repainting
Difficulty:997
これは解法を思いついた！
あとは実装するだけ！
import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
if s[i][j]=='#':
black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() #位置[行,列]を入れておく
def bfs():
seen[0][0] = 1
queue.append([0,0])
min_dist[0][0] = 1
while queue:
qh,qw = queue.popleft()
for dh,dw in dhdw:
nh,nw = qh+dh,qw+dw
if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='#':
continue
if [nh,nw]==[H-1,W-1]:
return min_dist[qh][qw]+1
seen[nh][nw] = 1
queue.append([nh,nw])
min_dist[nh][nw] = min_dist[qh][qw]+1
else:
return -1
min_dist = bfs()
print(H*W-black_count-min_dist if min_dist!=-1 else -1)
次回は、以下の12問を解いていきます！
動的計画法：ナップザック DP
34 ALDS_10_A - フィボナッチ数 超基本。「DP とは何か」を感じることができます。
35 DPL_1_B - 0,1ナップザック問題 基本問題です。
36 DPL_1_C - ナップザック問題 基本問題です。
37 DPL_1_A - コイン問題 基本問題です。
38 ALDS_10_C - 最長共通部分列 基本問題です。
(ここから先は、どのような DP で解けるのかは書きませんが、全部ナップザック DP またはその亜種で解くことができます。)
39 JOI 2011 予選 4 - 1 年生
40 JOI 2012 予選 4 - パスタ
41 JOI 2013 予選 4 - 暑い日々
42 JOI 2015 予選 4 - シルクロード
43 パ研杯2019 D - パ研軍旗
44 AOJ 1167 - ポロック予想
45 AOJ 2199 - 差分パルス符号変調
Part7/22
おわり！
次(Part8/22)へ
緑色を達成してある程度満足してしまい、かつその後数回レートが上がらなくてモチベが0になってしまいましたw
続きを誰か頼みます