ここ最近「技術系の記事は書いておいた方が良い」とめちゃくちゃ色んな人に言われる。
色々書いてみたいけどそもそも全然記事を書いた経験がないので、身近な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")