A - Water Station
解法1 切り上げ、切り捨て
高橋君よりも前にある給水所と後ろにある給水所の地点を求めて、Nに近いものを出力すればよいです。
N = int(input())
x = N//5*5
y = -(-N//5)*5
if N-x > y-N:
print(y)
else:
print(x)
解法2 全探索
21か所の給水所に関して高橋君との距離を調べて、一番近いものを出力すればよいです。
N=int(input())
print(min(range(0,101,5),key=lambda x:abs(x-N)))
B - ABCDEFG
解法1 埋め込み
答えとしてあり得る組み合わせをすべて埋め込みます。
p,q = input().split()
x = {"A":{"A":0,"B":3,"C":4,"D":8,"E":9,"F":14,"G":23},
"B":{"A":3,"B":0,"C":1,"D":5,"E":6,"F":11,"G":20},
"C":{"A":4,"B":1,"C":0,"D":4,"E":5,"F":10,"G":19},
"D":{"A":8,"B":5,"C":4,"D":0,"E":1,"F":6,"G":15},
"E":{"A":9,"B":6,"C":5,"D":1,"E":0,"F":5,"G":14},
"F":{"A":14,"B":11,"C":10,"D":6,"E":5,"F":0,"G":9},
"G":{"A":23,"B":20,"C":19,"D":15,"E":14,"F":9,"G":0}
}
print(x[p][q])
大変ですね。そこで、すべてを書かなくてもいい方法を考えてみましょう。
解法2 累積和
ある二点間の距離というのは、それぞれのAからの距離の差の絶対値と等しいことがわかります。よって、Aからの距離をそれぞれの点について求めておけば良いです。
p,q = input().split()
x = "ABCDEFGH"
y = [0,3,4,8,9,14,23]
i,j = y[x.index(p)],y[x.index(q)]
print(abs(i-j))
文字を数列のindexに変換する部分はord関数を使うことでも記述可能です。
p,q = input().split()
y = [0,3,4,8,9,14,23]
i,j = y[ord(p)-ord("A")],y[ord(q)-ord("A")]
print(abs(i-j))
解法3 オーバーキル
もしもあなたがダイクストラ法などでグラフ上の最短経路問題を解くためのライブラリを持っている場合は、これを貼ることでもACが取れます。半分冗談みたいな話ですが、しっかりとスニペットに登録してすぐに使える状態になっている場合はこちらの方がより早く直感的に書くことができるかもしれません。
import heapq
class Weighted_Graph():
def __init__(self, N):
self.N = N
self.graph = [dict() for _ in range(N)]
def unite(self,x,y,C):
self.graph[x][y] = C
self.graph[y][x] = C
return True
def dijkstra(self,s):
queue = [(0,s)]
costs = [float('inf')]*self.N
costs[s] = 0
while queue:
cost,i = heapq.heappop(queue)
if cost > costs[i]:
continue
for j in self.graph[i]:
temp = costs[i] + self.graph[i][j]
if temp < costs[j]:
costs[j] = temp
heapq.heappush(queue,(temp,j))
return costs
p,q = map(lambda x:ord(x)-ord("A"),input().split())
g = Weighted_Graph(7)
g.unite(0,1,3)
g.unite(1,2,1)
g.unite(2,3,4)
g.unite(3,4,1)
g.unite(4,5,5)
g.unite(5,6,9)
print(g.dijkstra(p)[q])
import networkx as nx
G = nx.Graph()
G.add_nodes_from("ABCDEFGH")
G.add_edge("A", "B", weight=3)
G.add_edge("B", "C", weight=1)
G.add_edge("C", "D", weight=4)
G.add_edge("D", "E", weight=1)
G.add_edge("E", "F", weight=5)
G.add_edge("F", "G", weight=9)
p,q = input().split()
print(nx.dijkstra_path_length(G, p,q))
C - Snuke the Cookie Picker
解法1 元の部分長方形を求める方法
問題文中のa,b,c,dを求めることができれば、どこが部分長方形であるかを求めることができます。
cookieの置いてあるマスの座標(i,j)を考えると
・aはiの最小値
・bはiの最大値
・cはjの最小値
・dはjの最大値
であることがわかります。これで、元の長方形がわかったので、あとはこの長方形の中にあるのにクッキーが置かれていない場所を探せばよいです。
H,W = map(int,input().split())
a = 501
b = -1
c = 501
d = -1
S = [input() for i in range(H)]
for i in range(H):
for j in range(W):
if S[i][j] == "#":
a = min(a,i)
b = max(b,i)
c = min(c,j)
d = max(d,j)
for i in range(H):
for j in range(W):
if S[i][j] == "." and a <= i <= b and c <= j <= d:
print(i+1,j+1)
exit()
解法2 周囲にあるクッキーの数を考える解法
すぬけくんが食べてしまったクッキーの周辺8マスがどのようになるかを考えてみましょう。すると、
... ... ...
.s# #s# #s.
.## ### ##.
.## ### ##.
.s# #s# #s.
.## ### ##.
.## ### ##.
.s# #s# #s.
... ... ...
の、9パターンの内のどれかになることがわかります。
一方で初めからクッキーが置かれていなかったマスについても考えてみましょう。
... ... ... ... ...
.x. .x. .x. .x. .x.
..# .## ### ##. #..
... ...
.x# #x.
..# #..
..# ... #..
.x# .x. #x.
..# ... #..
..# #..
.x# #x.
... ...
..# .## ### ##. #..
.x. .x. .x. .x. .x.
... ... ... ... ...
の、17パターンのどれかであることがわかります。
ここで、両方のパターンのsまたはxの上下左右4マスにクッキーが置かれているマスは何個あるかを調べます。すぬけ君が食べたマスに関しては、すべてのマスで2個以上上下左右にクッキーが置かれているのに対して、元からクッキーが置かれていなかったマスは多くても上下左右に合計1つのクッキーしか置かれていないことがわかります。
よって、.が書かれているマスの内、上下左右のクッキーの個数が2個以上であるマスが求めるべき答えです。
H,W = map(int,input().split())
S = [input() for i in range(H)]
for i in range(H):
for j in range(W):
if S[i][j] == "." and sum(0 <= i+di < H and 0 <= j+dj < W and S[i+di][j+dj]=="#" for di,dj in ((1,0),(0,1),(-1,0),(0,-1)))>=2:
print(i+1,j+1)
解法3 行ごと、列ごとに合計を取る方法
入力例3を例にして、考えてみましょう。
行ごと、列ごとのクッキーの数の合計を取ります。
..#### 4
..##.# 3
..#### 4
..#### 4
..#### 4
...... 0
005455
このようにしてみると、すぬけ君が食べたクッキーを含む行と列は、他のクッキーを含む行と列に比べて合計値が1低い値になることがわかります。よって、すべての行、列に関してクッキーの数の合計値を出し、それぞれで最大値をとりその最大値-1となっている行、列を求めることですぬけくんが食べたクッキーの位置を発見することができます。
H,W = map(int,input().split())
S = [input() for i in range(H)]
x = [sum(S[i][j]=="#" for j in range(W))for i in range(H)]
y = [sum(S[i][j]=="#" for i in range(H))for j in range(W)]
print(x.index(max(x)-1)+1,y.index(max(y)-1)+1)
D - Sleep Log
解法1 累積和と二分探索
f(x)を、睡眠記録を付け始めてからx分後ちょうどまでに高橋君が寝ていた時間とします。
このとき、各クエリの答えはf(r)-f(l)となることがわかります。これ以降はf(x)の実装方法について考えます。
睡眠記録の数列Aのそれぞれの時刻によって区切られている区間がN-1個あります。まずはxがどの区間に含まれているかを二分探索を用いることで求めます。
もしも、その区間が"高橋君が起きている区間"であった場合はその区間の一個前の区間までの睡眠時間の合計が答えです。
その区間が"高橋君が寝ている区間"の場合、その区間の一個前の区間までの睡眠時間の合計にさらにその区間の開始時刻とxの差を足したものが答えです。
この、一個前の区間までの睡眠時間の合計は愚直にやるとO(N) かかりますが、累積和を用いることでO(1)で計算が可能になります。二分探索がO(logN)であるため、f(x)の一回当たりの計算量はO(logN)です。
from itertools import accumulate
from bisect import bisect
def f(x):
i = bisect(A,x)-1
res = cumsum[i]
if i%2 == 1:
res += x-A[i]
return res
N = int(input())
A = list(map(int,input().split()))
cumsum = [0] + list(accumulate((A[i+1]-A[i] if i%2 else 0 for i in range(N-1))))
Q = int(input())
for _ in range(Q):
l,r = map(int,input().split())
print(f(r)-f(l))
解法2 クエリ先読み,イベントソート
解法1と考え方は同じです。高橋君が起きる、寝る、各クエリのl,rの時間でイベントソートして、昇順にみていくことでf(x)を求めることができます。下記のコードではstartにf(l)相当の数値、ansにf(r)-f(l)相当の数値を入れています。
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
events = []
start = [0]*Q
ans = [0]*Q
sleep = False
for i in range(N):
if i%2 == 0:
events.append((A[i],1,-1))#起きる
else:
events.append((A[i],2,-1))#寝る
for i in range(Q):
l,r = map(int,input().split())
events.append((l,3,i))
events.append((r,4,i))
events.sort(key = lambda x:x[0])
nowsleep = False
sleepstart = 0
sleeptimesum = 0
for time,key,i in events:
if key == 1:
nowsleep = False
sleeptimesum += time-sleepstart
elif key == 2:
nowsleep = True
sleepstart = time
elif key == 3:
start[i] = sleeptimesum
if nowsleep:
start[i] += time-sleepstart
else:
ans[i] = sleeptimesum
if nowsleep:
ans[i] += time-sleepstart
ans[i] -= start[i]
for i in range(Q):
print(ans[i])
解法3 Mo's Algorithm
Moで書く必要は、ないと思います...
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
LR = []
comp = set(A)
sA = set(A)
for i in range(Q):
l,r = map(int,input().split())
comp.add(l)
comp.add(r)
LR.append((l,r))
tmp = sorted(list(comp))
vtoc = {tmp[i]:i for i in range(len(tmp))}
ctov = {i:tmp[i] for i in range(len(tmp))}
block = int((3**0.5 *len(tmp))/((2*Q)**0.5))
Qli = [[] for i in range(len(tmp)//block+1)]
for i in range(Q):
l,r = LR[i]
l,r = vtoc[l],vtoc[r]
Qli[l//block].append((r,l,i))
sleepadd = [0]*len(tmp)
now = 0
j = 0
for i in range(1,N):
if i % 2 == 0:
while tmp[j+1] != A[i]:
sleepadd[j] = tmp[j+1] - tmp[j]
j += 1
sleepadd[j] = tmp[j+1] - tmp[j]
j += 1
else:
while tmp[j+1] != A[i]:
sleepadd[j] = 0
j += 1
sleepadd[j] = 0
j += 1
now = 0
now_l = 0
now_r = 0
ans = 0
answers = [0]*Q
f = 0
for l in Qli:
if len(l)==0:
continue
for x in sorted(l,reverse = f):
r,l,i = x
while now_r > r:
now_r = now_r -1
ans -= sleepadd[now_r]
while now_r < r:
ans += sleepadd[now_r]
now_r = now_r +1
while now_l < l:
ans -= sleepadd[now_l]
now_l = now_l+1
while now_l > l:
now_l = now_l-1
ans += sleepadd[now_l]
answers[i] = ans
f^=1
print(*answers)
E - Art Gallery on Graph
解法1 heapqを用いて探索する
各頂点についてその頂点にたどり着くことが可能な警備員の内、最も到着時の体力が高い人の体力をもつ。
優先度付きキューを用いて、大きい順からこの値を決めていくことで、すべての頂点にこの値を割り振ることができます。
import sys
import heapq
input = sys.stdin.readline
N,M,K = map(int,input().split())
G = [[] for i in range(N)]
for _ in range(M):
a,b = map(int,input().split())
a-=1
b-=1
G[a].append(b)
G[b].append(a)
keibi = [-1]*N
q = []
for i in range(K):
p,h = map(int,input().split())
p-=1
keibi[p] =h
q.append((-h,p))
heapq.heapify(q)
while q:
h,p = heapq.heappop(q)
h = -h
if keibi[p] != h:
continue
for i in G[p]:
if keibi[i] < h-1:
keibi[i] = h-1
if h-1 != 0:
heapq.heappush(q,(-(h-1),i))
ans = []
for i in range(N):
if keibi[i] != -1:
ans.append(i+1)
print(len(ans))
print(*ans)
解法2 超頂点とダイクストラ法
超頂点を用意し、警備員がいる頂点に対して重さ(X-体力)の辺を張る。ここで、Xはある程度大きい値とする。
もともとある辺は重さ1として超頂点を始点としてダイクストラをして、最短経路がX以下であるものの数を調べればよいです
import heapq
class Weighted_Graph():
def __init__(self, N):
self.N = N
self.graph = [dict() for _ in range(N)]
def unite(self,x,y,C):
self.graph[x][y] = C
self.graph[y][x] = C
return True
def dijkstra(self,s):
queue = [(0,s)]
costs = [float('inf')]*self.N
costs[s] = 0
while queue:
cost,i = heapq.heappop(queue)
if cost > costs[i]:
continue
for j in self.graph[i]:
temp = costs[i] + self.graph[i][j]
if temp < costs[j]:
costs[j] = temp
heapq.heappush(queue,(temp,j))
return costs
N,M,K = map(int,input().split())
g = Weighted_Graph(N+1)
X = 500000
for i in range(M):
a,b = map(int,input().split())
g.unite(a,b,1)
for i in range(K):
p,h = map(int,input().split())
g.unite(0,p,X-h)
res = g.dijkstra(0)
ans = []
for i in range(1,N+1):
if res[i] <= X:
ans.append(i)
print(len(ans))
print(*ans)
F - Dungeon Explore
解法1 再帰DFS
グラグの全域木を考えます。全域木の辺の数は(N-1)本です。頂点1からDFSをして、頂点1へと戻ってくるとき、この全域木を構成する辺をそれぞれ2回ずつ通ることがわかります。よって、全域木のすべての頂点をめぐって頂点1に帰ってくるには2*(N-1)回の移動ですむことがわかり、これは2*Nよりも小さいです。
def DFS(x):
if x == N:
input()
exit()
k,*v = map(int,input().split())
for i in reversed(v):
if i not in alr:
alr.add(i)
print(i)
DFS(i)
print(x)
input()
N,M = map(int,input().split())
alr = set([1])
DFS(1)
解法2 非再帰DFS
非再帰でも書けます。
N,M = map(int,input().split())
stack = [~1,1]
p = [-1]*(N+1)
p[1] = 1
f = False
while stack:
i = stack.pop()
if i >= 0:
if not f:
f = True
else:
print(i)
if i == N:
input()
exit()
k,*v = map(int,input().split())
for j in v:
if p[j] == -1:
p[j] = i
stack.append(~j)
stack.append(j)
else:
print(p[~i])
input()