先週のABCでなんと入茶することができました！ そして緑コーダになるための方法を適当にググっていると良い感じのブログを見つけたので、その方のやり方を真似てみることにしました！
この方がまずはe869120さんの【分野別 初中級者が解くべき過去問精選 100 問】を解くのが良いと書いていたので、ゴリゴリと解いていくことに決めました！【全探索：ビット全探索】までの問題を全部終わらせた後に、どこにも解き方をまとめていないことに気づいたので、順列全探索から自分なりの解き方、自力で解けなかった時は他の優秀な方の解き方を自分なりにまとめていきたいと思っています！もし同じ問題に取り組むあなたの助けになれたら幸いです！
145 Average Length
from itertools import permutations
import math
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
num = list(range(n))
ptn = list(permutations(num))
cnt = 0
for p in ptn:
for i in range(len(p)-1):
fir = p[i]
sec = p[i+1]
x1,y1 = points[fir]
x2,y2 = points[sec]
cnt += math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
print(cnt/(len(ptn)))
この問題は問題文に書かれていることをやっていくだけで解けるB問題みたいなやつです。ミスが起きやすいのはfirとsecのところです。最初のわいみたいに間違えてfirの値をi、secの値をi+1にするみたいなバカみたいなことはしないようにしましょう。順列全探索用のライブラリpermutationsによってindex番号の順番が変わっているので、pから取り出してあげないといけません。
150 Count Order
from itertools import permutations
n = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
num = list(range(1,n+1))
ptn = list(permutations(num))
for i in range(len(ptn)):
if ptn[i] == P:
a = i+1
if ptn[i] == Q:
b = i+1
print(abs(a-b))
この問題はまず、permutationsで作られる配列はtuple型なので、同じかどうかを判定するためにPとQの配列はtuple型である必要があります。なのでtuple型でPとQの値を受け取っています。そのあとは文字通り順列全探索をして、同じ配列ならaの値をi+1にします(iはindex番号なので0から始まるから)、そして同様の処理をbに対しても行っていきます。 最後に問題文通りの引き算をすればACできます！
ALDS_13_A - 8 クイーン問題
正直手も足も出ませんでした...成長して解けるようになります...それと誰か良い解説教えてください...
ALDS_4_B - 二分探索
n = int(input())
S = set(map(int, input().split()))
q = int(input())
T = set(map(int, input().split()))
cnt = 0
for t in T:
if t in S:
cnt += 1
print(cnt)
この問題は二分探索を使わなくても、set型に置き換えれば、リスト型よりも高速でtの数字がSに入っているのかを探してくれるので間に合います。しかし、これは二分探索を使って解くのが目的の問題なので、二部探索を使ったバージョンも載せておきます
def judge(s,e,t):
while s <= e:
mid = (s+e)//2
if S[mid] == t:
return True
elif S[mid] < t:
s = mid+1
else:
e = mid-1
return False
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for t in T:
start = 0
end = len(S)-1
if judge(start,end,t):
cnt += 1
print(cnt)
judgeの部分はテンプレートのコピペみたいなもんです。
分かりやすく二分探索を解説しているサイト
JOI 2009 本選 2 - ピザ
import bisect
d = int(input())
n = int(input())
m = int(input())
stores = [0]
stores.append(d)
for _ in range(n-1):
p = int(input())
stores.append(p)
stores.sort()
cnt = 0
for i in range(m):
h = int(input())
idx = bisect.bisect_right(stores,h)
cnt += min(abs(h-stores[idx-1]),abs(h-stores[idx]))
print(cnt)
この問題は二分探索を効率よく行えるようにしてくれるライブラリbisectを使って解くと簡単に解けます。まず必要な情報を受け取っていきます。次に、店舗の場所を格納したリストを作りましょう。0とdの位置には絶対に店舗が入っているので、あらかじめぶち込んでおきましょう。次に、店舗の位置の情報を受け取ってリストを完成させましょう。次に、二部探索を使うにはリストの順序を整えておかないといけないのでsortをしておきましょう！ついに二分探索の時間です！
まずは宅配位置を受け取って、bisect_rightを使って、宅配位置を挟む二つの店舗の情報を受け取りましょう。そして最後に、二つの店舗のうちどちらがより近いかをminメソッドを使って導き出して、cntに加えてACです！
77 Snuke Festival
import bisect
n = int(input())
A = sorted(list(map(int, input().split())))
B = list(map(int, input().split()))
C = sorted(list(map(int, input().split())))
cnt = 0
for b in B:
lower = bisect.bisect_left(A,b)
higher = bisect.bisect_right(C,b)
cnt += lower*(n-higher)
print(cnt)
この問題も上の問題同様bisectを使うことで効率よくACできます。まずは必要な情報を受け取って、AとCにだけsortをします。これは、Bの値をベースにfor文を回すこと計算量をAとCをベースにしているときより減らせるからです。そして、bの上に乗ることのできるパーツの数をlowerに格納します。bisect_leftを使うのはAから選ばれるパーツはbの値より小さく無いといけないから。そしてhigherにはCの中でbより小さいパーツの数を入れます。bisect_rightを使うのは、最終的に求めたいのはCの中でbより値の大きい値なので、bisect_leftを使うと間違いが生じてしまうからです。そしてcntに加えるペア数はbより小さいAのパーツの数*bより大きいCのパーツの数(全体数から、bより小さい数はbより大きい数と同じになる)。そしてcntの値を最後に出力してあげればOKです。
23 射撃王
解説をよく読んでもわからなかった...成長して戻ってくる...誰か教えてください
ムーアの法則
解説をよく読んでもわからなかった...成長して戻ってくる...誰か教えてください
ダーツ
import bisect
n,k = map(int, input().split())
points = [0]+[int(input()) for _ in range(n)]
pairs = []
for i in range(n+1):
for j in range(i,n+1):
pairs.append(points[i]+points[j])
pairs.sort()
ans = 0
for pair in pairs:
if pair > k:
break
idx = bisect.bisect_left(pairs,k+1-pair)-1
if idx < 0:
idx += 1
ans = max(ans, pair+pairs[idx])
print(ans)
この問題はまず必要な情報を受け取ってから、それぞれのポイントを格納するためのリストを作ります。(投げないケースも考えて0を加えておく)。そして2回投げた後の得点の組み合わせをfor文を回して洗い出してpairsリストに格納していきます。(この問題では4投を2回に分割して解いていきます) その後にsortをしてから二部探索を始めていきます。まず問題上pairの時点でkより大きくなってしまったら失格+sortをしているので、それより後のpairの要素が全て失格になることがわかるのでbreakでfor文を抜けちゃってOKです。その後にbisectを使って、kに達するまでの数をk+1-pairで洗い出して、その数がリストの中のどこに入るかを見つけて、2回目に選ぶべきpairを求められます。そして、全てのペア分の最大値を比べ続けて出力をすればACできます。
深さ優先探索
import sys
sys.setrecursionlimit(10**6)
def dfs(i):
global cnt
cnt += 1
In[i]=cnt
visited[i]=True
for choice in connected[i]:
if not visited[choice-1]:
dfs(choice-1)
cnt += 1
Out[i] = cnt
n = int(input())
connected = []
for i in range(n):
u,k,*v = map(int, input().split())
connected.append(v)
In = [0]*n
Out = [0]*n
visited = [False]*n
cnt = 0
for i in range(n):
if visited[i]:
continue
dfs(i)
for i in range(n):
print(i+1,In[i],Out[i])
この問題はザ深さ優先探索って感じの問題です。まず、どことどこが隣接してるかの情報をconnectedに格納していきましょう。そして、それぞれの数字が始まるときと終わった時の時間を記録するためにInリストとOutリストを作っておきましょう。そして一度行っている場所のInに始まりの時間を何回も打ってしまうとWAになってしまうので、visitedですでに行ったことのある場所を記録しておきましょう。そして、いよいよdfsを始める準備ができました。まずfor分を回していきます(孤立している番号のことを考慮して) 正直、大半の番号がどれかしらの番号に隣接しているのでやる必要がないことがほとんどなので、すでに隣接する番号によって到達されていた場合にはcontinueでスキップしてあげましょう。もしまだ一度の辿り着かれていないのならdfsを回しましょう。dfsの中ではまず、時間を進めないといけないのでcntに1を再起関数がよばれるごとに追加をしていきます。そして開始時間としてinに数字を入れてあげて、visitedの値をtrueにしてあげます。その後に最初のiに隣接する番号をfor文で全て洗い出して、隣接する番号でdfs関数をもう一度呼び出してあげればオッケーです。全てのfor文が終わったらcntに1を追加して特定の番号の再起が終わった時間をoutに追加してあげればオッケーです。最後にfor文をうまいこと使って、出力例の出力していけばACを取れます。
AOJ 1160 - 島はいくつある？
import sys
sys.setrecursionlimit(10**6)
def dfs(y,x):
field[y][x] = 0
for dx in range(-1,2):
for dy in range(-1,2):
ny = y + dy
nx = x + dx
if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == 1:
dfs(ny,nx)
return
while True:
w, h = map(int,input().split())
if w == 0 and h == 0:
break
field = [list(map(int,input().split())) for _ in range(h)]
ans = 0
for i in range(h):
for j in range(w):
if field[i][j] == 1:
dfs(i,j)
ans += 1
print(ans)
この問題は全探索＋dfsみたいなイメージで解いていきました。dfsのイメージとしては隣接する陸が見つかった方にdfsを進めていく感じです。まずはfieldの情報を受け取っていきましょう。そしてfieldの情報を全探索のやり方で、回して行って、fieldに1が出てきたところからdfsを開始します。dfsの中では、まず最初に現在地の値を0にしておきます。0にしておかないと、次のfor文の0と0の時に、同じ位置でdfsがまた再起されてしまい無限ループに陥ってしまうからです。dfsの中の二重ループの中では周りの8方向を確認すればいいので、-1から1の範囲でfor文をそれぞれ回していきます。そして、もしfor文で新しく求めようとしている場所の位置がマップの範囲内かつ、そこにも陸があるのならば新しいyとxの値でdfsを再起していきます。dfsに一度でも入ると、そこには島が1つあるということになるのでansに1を加えましょう。全てのループが終わったらansの値を出力してACできます。
138 Ki
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(cur,pre):
for c in connected[cur]:
if c == pre:
continue
cnts[c] += cnts[cur]
dfs(c,cur)
n,q = map(int, input().split())
connected = [[]for _ in range(n)]
for i in range(n-1):
a,b = map(int, input().split())
connected[a-1].append(b-1)
connected[b-1].append(a-1)
cnts = [0]*n
for i in range(q):
p,x = map(int, input().split())
cnts[p-1] += x
dfs(0,-1)
print(*cnts)
この問題は有名な木問題です。解くのは初めてなのですが楽しかったです。まずは他のdfsと同じように下準備から始めていきます。今回はどの頂点とどの頂点が繋がっているかを記録しておきましょう。aがbの親じゃないケースに備えて双方に繋がりを記録しておきましょう。そのあとは最後に出力するカウンターの値を記録するためにcntsを作っておきましょう。次はfor文を回して初期の情報をcntsに記録していきましょう。q回分、開始位置pと入るポイントの数xを受け取って、開始位置には絶対にポイントが入るのでxを追加しましょう。次からdfsが始まります。dfsは引数に現在の位置と前回の位置を求めています。最初のdfsには前回の位置は存在しないので、存在しない頂点の数-1をぶち込んでおきましょう。次にdfsの内部では、現在の頂点と繋がっている全てのポイントをfor文で洗い出して、もしそれが現在位置と同じならスキップして、違うのなら現在地のcntsの値を足してあげればオッケーです。(上から下に流れていくイメージだから)最後にcntsの値を*を使って一斉に出力してACです！
JOI 2009 予選 4 - 薄氷渡り
import sys
sys.setrecursionlimit(10**6)
def dfs(field_damy,y,x,tmp):
global cnt
field_damy[y][x] = 0
if tmp > cnt:
cnt = tmp
if 0<=y+1<m and field_damy[y+1][x] == 1:
dfs(field_damy,y+1,x,tmp+1)
if 0<=y-1<m and field_damy[y-1][x] == 1:
dfs(field_damy,y-1,x,tmp+1)
if 0<=x+1<n and field_damy[y][x+1] == 1:
dfs(field_damy,y,x+1,tmp+1)
if 0<=x-1<n and field_damy[y][x-1] == 1:
dfs(field_damy,y,x-1,tmp+1)
field_damy[y][x] = 1
n = int(input())
m = int(input())
field = [list(map(int, input().split())) for _ in range(m)]
cnt = 0
for i in range(m):
for j in range(n):
if field[i][j] == 1:
field_damy = [field_line[::] for field_line in field]
tmp = 0
dfs(field_damy,i,j,tmp+1)
cnt = max(cnt, tmp)
print(cnt)
この問題は楽しい問題でした。まずは他のdfsと同じように、情報を使いやすい形で受け取ります。そして、最大値を格納するためのcnt変数をつくってdfsを始める位置を見つけるためにfor文を回していきます。1が見つかったら、field変数と全く同じ要素を持つfield_damy変数を作り出して(fieldの値はfor文を回しているので変えたくないから)、試したdfsの結果を格納するtmp変数を作ってからdfsを開始していきます。dfsの中ではまず、現在地の番号を0にして現在の最大値と比べていきます。そして、上下左右のどこかに氷があったら、その位置でdfsを再起します。チェックが終わったら、上で0にした氷を1に戻してあげましょう。