ABC317 A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
A
Pは小さい順に並んでいるので、P1,P2,P3,...の順にHに足して、Xを超えるものが何番目か確認します。
Pをリストで受け取ってfor文で処理していきましょう。
for i in range(最後の数+1):
と書くことでi=0,1,2,...と順に代入して処理が出来ます。
注意するのはpythonでは最初の要素を0番目、次を1番目、...と数えることです。
問題で言うP1はリストでは0番目すなわちP[0]になり、P2はリストでは1番目すなわちP[1]になり、...というように一つ番号がずれるので、出力の際は+1する必要があります。
途中で終了する場合はexit()と書きます。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
N,H,X=map(int, input().split())
P=list(map(int, input().split()))
# i=0~(N-1)
for i in range(N):
# X≦H+P[i]ならば
if X<=H+P[i]:
# (i+1)を出力
print(i+1)
# 途中終了
exit()
B
小さい順に並べたとき、隣の数字が1個飛んでいたらそれが答えになります。
例えば1 2 4 5だったら3がないということがわかります。
(なくした整数が一意に定まるという条件から必ず飛んでいる数字があります)
よって一個ずつ隣の数との差を見ていけばOKです。
【提出】
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# 小さい順に並び替え
A.sort()
# i=0~(N-1)
for i in range(N):
# A[i]+1≠A[i+1]ならば
if A[i]+1!=A[i+1]:
# A[i]+1が答え
print(A[i]+1)
# 途中終了
exit()
C
DFS(深さ優先探索)を使います。
例えば以下のような場合
まず街①からスタートします。
街①から行けるのは街②、街③です。
街②へ進むと街①からの距離は1です。
更に街②からは街④と街⑤へ進めます。
街④へ進むと街①からの距離は6です。
ここで街④は行き止まりなので街②へ戻ります。
次は街②から街⑤へ行きます。街⑤へ進むと街①からの距離は4です。
街⑤は行き止まりで、街②から行ける街も全て進んだので街①へ戻ります。
街①から今度は街③へ進みます。街③へ進むと街①からの距離は4です。
街③からは街⑤へ行けます。街⑤へ進むと街①からの距離は6です。
このように進める街のうち最も奥まで行ったら戻って次の町へ行く、というのを繰り返すのがDFSです。
同様の手順をスタートする街を順に変えて行うことで全てのルートの距離を確認することが出来ます。
実装には再帰関数を使うことが多いです。
再帰関数は最初のうちは難しいですが、もはや緑コーダーになるには必須の技術となってしまったので、茶色コーダーの人も頑張って使えるようになりましょう。
書き方や動作の内容は以下の動画を見てもらうのがわかりやすいです。
(文章だけだとどうしても何をやっているかわかりづらいので・・・)
pythonでは間に合わないのでpypyで提出します。
【提出】
# pypyで提出
# 再帰回数上限を10^6へ変更(再帰関数を使うときはとりあえず書いておく)
import sys
sys.setrecursionlimit(10**6)
# 入力の受け取り
N,M=map(int, input().split())
# 繋がっている頂点の情報を受け取り
connect=[[] for i in range(N+1)]
# M回
for i in range(M):
# 入力の受け取り
A,B,C=map(int, input().split())
# A→Bへは長さC
connect[A].append([B,C])
# B→Aへは長さC
connect[B].append([A,C])
# 答え
ans=0
# DFS
# now：今いる街 dist：スタートから今いる街までの距離
def DFS(now,dist):
# ansを更新できるように
global ans
# 答えを更新
ans=max(dist,ans)
# 今いる街から行ける街(to)とその距離(cost)を順に代入
for to,cost in connect[now]:
# 次に行ける街にまだ訪問していなければ
if visited[to]==False:
# 訪問済みにする
visited[to]=True
# 次の街へ
DFS(to,dist+cost)
# 戻ってきたら訪問済みを取り消す
visited[to]=False
# start=1~N
for start in range(1,N+1):
# 訪問済みかを確認するリスト
visited=[False]*(N+1)
# スタート地点を訪問済みにする
visited[start]=True
# スタート地点から開始
DFS(start,0)
# 答えの出力
print(ans)
D
下記の例で考えます。
4
1 4 1
3 8 3
7 4 2
2 7 3
まず情報を整理しましょう。
各選挙区について、
・X<Yならば((Y-X)//2+1)人を鞍替えさせればZの議席が獲得できます
・Y<Xならば何もせずともZの議席が獲得できます。つまり0人を鞍替えさせればZの議席が獲得できます
1,2,4番目についてはX<Y、3番目についてはY<Xとなっています。
1番目：2人鞍替え→1議席獲得
2番目：3人鞍替え→3議席獲得
3番目：0人鞍替え→2議席獲得
4番目：3人鞍替え→3議席獲得
この人数を重さ、議席を価値と考えるとこれはそのままナップサック問題と呼ばれるDPの典型問題になります。逆に言うとナップサック問題を知らないとこの問題を解くのは無理です。
というわけでDPで解きます。
DPとは「ある状態までの答えがわかっていれば→その次の状態の答えも出せる」という手続きを何度も行って最終的な答えを出す方法です。
具体的な手順は以下です。
(1)表を作る
(2)すぐにわかるところを埋める
(3)表の小さい方から答えにたどり着くまで埋める
(4)答えを出力する
初めてナップサック問題を解く人はまず以下の解説動画を見ることをおすすめします。
(1)表を作る
今回作る表は「i番目までの選挙区を使って、最低x議席を獲得するのに必要な最小鞍替え人数」とします。
この表は最終的には以下のような形になります。
i=2,x=4のところは「2番目までの選挙区を使って、最低4議席を獲得するのに必要な最小鞍替え人数」となります。
2番目まで、すなわち1番目と2番目の選挙区のみであれば5人鞍替えさせることで両方の選挙区を獲得して4議席が手に入りますね、この表はそのような意味です。
(2)すぐにわかるところを埋める
まずi=1の行を見てみましょう。
「1番目までの選挙区を使って、最低x議席を獲得するのに必要な最小鞍替え人数」
1番目：2人鞍替え→1議席獲得
x=1の部分、つまり「1番目までの選挙区を使って、最低1議席を獲得するのに必要な最小鞍替え人数」は2人です。
「1番目までの選挙区を使って」なので2議席以上を獲得する方法はありません。よってそれ以外は全て「×」です。
※「×」は実装ではありえないくらい大きな数を入れておきます。
(3)表の小さい方から答えにたどり着くまで埋める
i=2の行を見てみます。
2番目：3人鞍替え→3議席獲得
・x=1
x=1の部分は「2番目までの選挙区を使って、最低1議席を獲得するのに必要な最小鞍替え人数」となります。
もし2番目の選挙区を使うなら3人の鞍替えが必要ですがすでに表には「2」が入っています。すなわち1番目の選挙区を使えば1議席獲得に2人で済むわけですから、ここは上の段をそのまま持ってきて「2」になります。
・x=2,3
i=1の行のx=2,3は何も入っていません。つまり2番目の選挙区を使わなければ2,3議席は取れません。
2番目の選挙区を使えば3人の鞍替えで3議席取れますから、これらは「3」になります。
・x=4
上段のマスi=1,x=1には「2」が入っています。これは1議席獲得に2人の鞍替えが必要であることを意味しています。
ここから2番目の選挙区を使い、更に3人鞍替えすれば+3議席が獲得できます。よって合計4議席が獲得できます。
よって上段のマスの「2」に+3して「5」が埋まります。
ここまでの話をまとめると
x=1～(i番目選挙区の獲得議席)
・i番目の選挙区を使わない場合→dp[i-1][x](上の数字をそのまま下に持ってくる)
・i番目の選挙区を使う場合→(i番目の鞍替え人数)
x=(i番目選挙区の獲得議席)+1～
・i番目の選挙区を使わない場合→dp[i-1][x](上の数字をそのまま下に持ってくる)
・i番目の選挙区を使う場合→dp[i-1][x-(i番目選挙区の獲得議席)]+(i番目選挙区の鞍替え人数)
これらの小さい方を埋めるという形になります。
ちょっとややこしいのでもう一個例を見ましょう。
i=3、x=4の箇所を埋めます。
3番目：0人鞍替え→2議席獲得
さきほど確認したことを思い出しながら代入してみます。
x=(i番目選挙区の獲得議席)+1～
・i番目の選挙区を使わない場合→dp[i-1][x](上の数字をそのまま下に持ってくる)
・i番目の選挙区を使う場合→dp[i-1][x-(i番目選挙区の獲得議席)]+(i番目選挙区の鞍替え人数)
↓
・3番目の選挙区を使わない場合→dp[2][4]=5
・3番目の選挙区を使う場合→dp[2][4-2]+0=3
これで3番目の選挙区を使う場合の方が小さくなり、3が埋まります。
(実際2,3番目の選挙区を使うと3人の鞍替えで議席5(x=4以上)が手に入りますね)
(4)答えを出力する
表が全て埋まると以下のようになります。
最後の行、i=4について、過半数の議席=5以上を得るために必要な議席数は「3」でこれが答えです。
pythonでは間に合わないのでpypyで提出します。
【提出】
# pypyで提出
# 入力の受け取り
N=int(input())
# i番目選挙区の獲得議席
V=[0]*(N+1)
# i番目選挙区の鞍替え人数
C=[0]*(N+1)
# Z=議席数の合計
Zsum=0
# i=1~N
for i in range(1,N+1):
# 入力の受け取り
X,Y,Z=map(int, input().split())
# X<Yの場合
if X<Y:
# (Y-X)//2+1人の鞍替えが必要
C[i]=(Y-X)//2+1
# Y<Xの場合
else:
# 鞍替えなし=0人の鞍替えが必要
C[i]=0
# 獲得議席数
V[i]=Z
# 合計にプラス
Zsum+=Z
# 表で獲得不可能な議席に埋める数(大きい数)
inf=10**20
# 表の作成
dp=[[inf]*(Zsum+1) for i in range(N+1)]
# i=1~N
for i in range(1,N+1):
# x=1~V[i]⇔i番目選挙区の獲得議席
for x in range(1,V[i]+1):
# i番目の選挙区を使わない：dp[i-1][x](上の段の数字)
# i番目の選挙区を使う：C[i]：鞍替え人数
dp[i][x]=min(dp[i-1][x],C[i])
# x=V[i]+1~Zsum
for x in range(V[i]+1,Zsum+1):
# i番目の選挙区を使わない：dp[i-1][x](上の段の数字)
# i番目の選挙区を使う：dp[i-1][x-V[i]]+C[i](dp[i-1][x-(i番目選挙区の獲得議席)]+(i番目選挙区の鞍替え人数)
dp[i][x]=min(dp[i-1][x],dp[i-1][x-V[i]]+C[i])
# 過半数獲得に必要な鞍替え人数の最小
print(dp[N][Zsum//2+1])
E
行けないマスを確認できてしまえば普通のBFSで解けそうです。で、実際それで解けます。
つまり目線の通るところ全てに通れないという印を書いていけば良いわけですが、最悪のケースで計算量はどれくらいになるか考えましょう。
最悪のケースは以下のような場合です。
各マスは4方向全ての視線にさらされていますが、各目線全てを処理したとしても4回同じマスを通るだけです。
よって計算量は全体で4HW=4*2000*2000=16*10^6となって実は大したことがありません。
実装では各マスについて
障害物がある：-1
目線が通っている：-2
と数字を割り振ってからBFSで最短距離を出しています。
また、0行目とH+1行目、0列目とW+1行目を作り、外周をぐるっと障害物、つまり壁で囲っています。
これは「番兵」と呼ばれるテクニックでなくても解けるのですが、あると実装がとても楽になります。
BFSの練習問題としては少々難しいです。
同じようにマス目をたどるBFS問題としてはABC232Dが比較的簡単です。BFSに慣れていない人は先にこちらで練習することを推奨します。
問題：https://atcoder.jp/contests/abc232/tasks/abc232_d
解説：https://qiita.com/sano192/items/3cb3ae52adae8829c94f#d---weak-takahashi
ちなみに公式解説にある言葉について。
人の向きは4種類ありますが、4種類全てを別々に実装すると実装量がかさばる上にバグの原因にもなるのでお勧めしません。
もちろんきれいなコードを書けるのが一番良いのですが、灰色、茶色コーダーの方はあまり気にしなくて良いと思います。最初からきれいなコードを書くのは難しいですから、まずは冗長でも汚くてもとりあえずACできるコードを書くことを目指す、で良いと思います。
時間とやる気があるなら一度ACしたコードを自分できれいにする練習をするのも良いです。参考までに【提出2】として【提出1】をきれいにしたコードを載せておきます。
pythonでは間に合わないのでpypyで提出します。
【提出1】
# pypyで提出
# 入力の受け取り
H,W=map(int, input().split())
# 到達出来ない場所に埋める数字
inf=10**20
# 元の情報の格納 0行目に壁を作っておく
GridS=[["#"]*(W+2)]
# H回
for r in range(H):
# 一行ずつ受け取り、最初と最後に「#」の番兵をくっつけておく
A=["#"]+list(input())+["#"]
# 追加
GridS.append(A)
# (H+1)行目に壁を作っておく
GridS.append(["#"]*(W+2))
# マス目の情報を格納する二次元配列
Grid=[[inf]*(W+2) for i in range(H+2)]
# r=0~(H+1)
for r in range(H+2):
# c=0=(W+1)
for c in range(W+2):
# 「S」の場合
if GridS[r][c]=="S":
# スタート位置を記録
SH=r
SW=c
# 「^」の場合
elif GridS[r][c]=="^":
# 人がいて通れない⇔-1を記録
Grid[r][c]=-1
elif GridS[r][c]==">":
Grid[r][c]=-1
elif GridS[r][c]=="<":
Grid[r][c]=-1
elif GridS[r][c]=="v":
Grid[r][c]=-1
elif GridS[r][c]=="#":
Grid[r][c]=-1
# 「G」の場合
elif GridS[r][c]=="G":
# ゴール位置を記録
GH=r
GW=c
# ここから視線の処理
# r=0~(H+1)
for r in range(H+2):
# c=0=(W+1)
for c in range(W+2):
# 「^」の時
if GridS[r][c]=="^":
# i=1~H
for i in range(1,H+1):
# 上マスが初期値のままなら
if Grid[r-i][c]==inf:
# 視線があって通れない⇔-2を記録
Grid[r-i][c]=-2
# -1⇔障害物または人ならば
elif Grid[r-i][c]==-1:
# 終了
break
elif GridS[r][c]==">":
for i in range(1,W+1):
if Grid[r][c+i]==inf:
Grid[r][c+i]=-2
elif Grid[r][c+i]==-1:
break
elif GridS[r][c]=="<":
for i in range(1,W+1):
if Grid[r][c-i]==inf:
Grid[r][c-i]=-2
elif Grid[r][c-i]==-1:
break
elif GridS[r][c]=="v":
for i in range(1,H+1):
if Grid[r+i][c]==inf:
Grid[r+i][c]=-2
elif Grid[r+i][c]==-1:
break
# BFS
# dequeをインポート
from collections import deque
# キューを用意
que=deque()
# キューへスタート地点を追加
que.append([SH,SW])
# 最初のマスに0と書く
Grid[SH][SW]=0
# キューが空になるまで
while 0<len(que):
# 今いるマスの行、列
nowH,nowW=que.popleft()
# 今いるマスに書いている数字
nowNum=Grid[nowH][nowW]
# 上マスが0以上(障害物または視線ではない) かつ nowNum+1より数字が大きい ならば
if 0<=Grid[nowH-1][nowW] and nowNum+1<Grid[nowH-1][nowW]:
# マスの数字を更新
Grid[nowH-1][nowW]=nowNum+1
# キューへ入れる
que.append([nowH-1,nowW])
if 0<=Grid[nowH+1][nowW] and nowNum+1<Grid[nowH+1][nowW]:
Grid[nowH+1][nowW]=nowNum+1
que.append([nowH+1,nowW])
if 0<=Grid[nowH][nowW+1] and nowNum+1<Grid[nowH][nowW+1]:
Grid[nowH][nowW+1]=nowNum+1
que.append([nowH,nowW+1])
if 0<=Grid[nowH][nowW-1] and nowNum+1<Grid[nowH][nowW-1]:
Grid[nowH][nowW-1]=nowNum+1
que.append([nowH,nowW-1])
# ゴールが初期値のままなら
if Grid[GH][GW]==inf:
# 「-1」を出力
print(-1)
# そうでなければ
else:
# マスに書いている数字を出力
print(Grid[GH][GW])
【提出2】
# pypyで提出
# 入力の受け取り
H,W=map(int, input().split())
# 到達出来ない場所に埋める数字
inf=10**20
# 元の情報の格納 0行目に壁を作っておく
GridS=[["#"]*(W+2)]
# H回
for r in range(H):
# 一行ずつ受け取り、最初と最後に「#」の番兵をくっつけておく
GridS.append(["#"]+list(input())+["#"])
# (H+1)行目に壁を作っておく
GridS.append(["#"]*(W+2))
# マス目の情報を格納する二次元配列
Grid=[[inf]*(W+2) for i in range(H+2)]
# r=0~(H+1)
for r in range(H+2):
# c=0=(W+1)
for c in range(W+2):
# 「S」の場合
if GridS[r][c]=="S":
# スタート位置を記録
SH,SW=r,c
elif GridS[r][c]=="G":
# ゴール位置を記録
GH,GW=r,c
# 「.」でない⇔「^><v#」のどれかの場合
elif GridS[r][c]!=".":
# 通れないとして-1を記録
Grid[r][c]=-1
# 視線の処理をする関数
def Sisen(r,c,Direct):
# 向きによって方向を指定
if Direct=="^":DH,DW=-1,0
elif Direct==">":DH,DW=0,1
elif Direct=="<":DH,DW=0,-1
elif Direct=="v":DH,DW=1,0
# i=1~
for i in range(1,inf):
# 視線の方向へ順に進む
# 障害物や人でない場合
if GridS[r+i*DH][c+i*DW]==".":
# 視線があって通れない⇔-2を記録
Grid[r+i*DH][c+i*DW]=-2
# そうでなければ
else:
# 終了
return 0
# r=0~(H+1)
for r in range(H+2):
# c=0=(W+1)
for c in range(W+2):
# 「^><v」の時
if GridS[r][c] in "^><v":
# 処理する
Sisen(r,c,GridS[r][c])
# BFS
# dequeをインポート
from collections import deque
# キューを用意してスタート地点を入れる
que=deque([[SH,SW]])
# 最初のマスに0と書く
Grid[SH][SW]=0
# キューが空になるまで
while que:
# 今いるマスの行、列
nowH,nowW=que.popleft()
# 今いるマスに書いている数字
nowNum=Grid[nowH][nowW]
# 4方向を指定
for DH,DW in ((-1,0),(0,1),(0,-1),(1,0)):
# 進んだ先が障害物でない かつ nowNum+1より数字が大きい ならば
if 0<=Grid[nowH+DH][nowW+DW] and nowNum+1<Grid[nowH+DH][nowW+DW]:
# マスの数字を更新
Grid[nowH+DH][nowW+DW]=nowNum+1
# キューへ入れる
que.append([nowH+DH,nowW+DW])
# ゴールが初期値のままなら
if Grid[GH][GW]==inf:
# 「-1」を出力
print(-1)
# そうでなければ
else:
# マスに書いている数字を出力
print(Grid[GH][GW])