ここ最近「技術系の記事は書いておいた方が良い」とめちゃくちゃ色んな人に言われる。
色々書いてみたいけどそもそも全然記事を書いた経験がないので、身近なABCの感想をqiitaに垂れ流して記事を書く練習をしようというものです！！！
A問題
考察
- $N$人のうちもっとも若い人の番号を求め$base$とする。
- $array[(base+i)\mod N]$を順番に出力する。
コード
N = int(input())
S = []
A = []
base = -1
min_a = 10**20
for i in range(N):
s, a = input().split()
S.append(s)
a = int(a)
if a < min_a:
base = i
min_a = a
for i in range(N):
print(S[(base+i)%N])
B問題
考察
$10^3$以下までNを割り切ってから桁を復元する.
コード
N = int(input())
digits = 0
while N >= 10**3:
N //= 10
digits += 1
print(N*10**digits)
C問題
考察
$(X_i, Y_i)$と$(X_j, Y_j)$の距離が $D$ 以下の場合にのみ$i$と$j$に無向辺を張るように隣接グラフを作成する。
完成した隣接行列について幅優先探索を行うことで、人1から到達可能な人$i$を求める。
コード
from collections import deque
N, D = list(map(int,input().split()))
X = []
Y = []
for _ in range(N):
x, y = list(map(int,input().split()))
X.append(x)
Y.append(y)
# dist[i][j]: i と j の距離がD以下であるか
G = [[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
G[i][j] = (D**2 >= (X[i]-X[j])**2 + (Y[i]-Y[j])**2)
# 幅優先探索
visited = [False]*N
visited[0] = True
Q = deque([0])
while len(Q) > 0:
i = Q.popleft()
for j in range(N):
if not visited[j] and G[i][j]:
visited[j] = True
Q.append(j)
# 各 i にウイルスが到達したか
for i in range(N):
if visited[i]:
print("Yes")
else:
print("No")
D問題
考察
$y$軸並行な$A$本の直線と$x$軸平行な$B$本の直線で切り分けたケーキの区画を$(x_i, y_i)$とする。$(0 \leq x_i \leq A+1$ , $0 \leq y_i \leq B+1)$
各イチゴについて、どの区画に入るかを二部探索で決定する。
コード
from collections import defaultdict
from bisect import bisect_left
H, W = list(map(int, input().split()))
N = int(input())
P = []
Q = []
for _ in range(N):
p, q = list(map(int, input().split()))
P.append(p)
Q.append(q)
A = int(input())
cut_y = list(map(int, input().split()))
B = int(input())
cut_x = list(map(int, input().split()))
# block[(i, j)]: いちごが切り分けたケーキのどの区画に入るか
block = defaultdict(int)
for i in range(N):
j = bisect_left(cut_y, P[i])
k = bisect_left(cut_x, Q[i])
block[(j, k)] += 1
min_ = INF
max_ = -1
cnt = 0
for key in block:
cnt += 1
min_ = min(min_, block[key])
max_ = max(max_, block[key])
if cnt < (A+1)*(B+1):
min_ = 0
print(min_, max_)
E問題
考察
愚直な処理
各クエリについてノード間に辺を張り、「良いグラフ」かを各ノードで幅優先探索で判定すると$O(QK(N+M))$かかる。
計算量改善
各ノードを連結成分に分解し、それぞれの連結成分の番号を$g_i$とおく。$K$個の条件$(x_i, y_i) (i=1,2,\cdots K-1)$について、$x_i$の属する連結成分の番号を$g_{x_i}$、$y_i$の属する連結成分の番号を$g_{y_i}$としたとき$g_{x_i} \ne g_{y_i}$のとき「良いグラフ」でなくなる。連結成分の分解に$O(N+M)$かかり、良いグラフかどうかの条件判定には集合型を用いることで$O(1)$で判定できるので、全体の計算量としては、$O(N+M+Q)$である。
コード
from collections import defaultdict, deque
N, M = list(map(int, input().split()))
# グラフの作成
G = [set() for _ in range(N)]
for _ in range(M):
u, v = list(map(int, input().split()))
u -= 1; v -= 1
G[u].add(v)
G[v].add(u)
K = int(input())
cond = []
tmp = []
for _ in range(K):
x, y = list(map(int, input().split()))
x -= 1; y -= 1
cond.append((x, y))
tmp.append(x)
tmp.append(y)
# 幅優先探索
Q = deque()
visited = [False]*N
group_cnt = 0
# ノードがどの連結成分に所属するか
node2group = [-1]*N
for i in set(tmp):
if visited[i]:
continue
Q.append(i)
visited[i] = True
node2group[i] = group_cnt
while len(Q) > 0:
j = Q.popleft()
for k in G[j]:
if not visited[k]:
Q.append(k)
visited[k] = True
node2group[k] = group_cnt
group_cnt += 1
# 繋げてはいけない連結成分間を辞書で管理
not_connect = defaultdict(bool)
# 条件に関係ないノードはどの連結成分に含まれるか確認しない
for x, y in cond:
g1 = node2group[x]
g2 = node2group[y]
# g1 が常に小さくなるように swap
if g1 > g2 :
g1, g2 = g2, g1
not_connect[(g1, g2)] = True
q = int(input())
for _ in range(q):
p, q = list(map(int, input().split()))
p -= 1; q -= 1
g1 = node2group[p]
g2 = node2group[q]
if g1 > g2 :
g1, g2 = g2, g1
# g1 もしくは g2 が連結成分に属してない場合 Yes を出力
if g1 == -1 or g2 == -1:
print("Yes")
# g1 と g2 間を繋いでいけない場合 No を出力
elif not_connect[(g1, g2)]:
print("No")
else:
print("Yes")