【ABC361】緑コーダーの競プロ参加記録 #27
今回はAtCoder Beginner Contest 361。使用言語はPythonです。
A問題 - Insert
コンテスト中の提出
https://atcoder.jp/contests/abc361/submissions/55254082
長さ$${N}$$の数列$${A}$$と整数$${K,X}$$が与えられる。
$${A}$$の$${K}$$番目の要素の後ろに$${X}$$を挿入した数列を出力してね。
問題タイトルの通り、 insert メソッドを利用することで解くことができます。
1-indexで$${K+1}$$番目の要素として$${X}$$を挿入するためには、0-indexで$${K}$$番目に insert します。
""" AC コード """
N, K, X = map(int, input().split())
A = list(map(int, input().split()))
A.insert(K, X)
print(*A)少し変わった解き方もあります。
""" A の先頭にスペースを空けておく """
N, K, X = map(int, input().split())
A = [0] + list(map(int, input().split()))
""" K 番目までの要素を1つ手前にずらす """
for i in range(1, K + 1):
A[i - 1] = A[i]
A[K] = X
print(*A)B問題 - Intersection of Cuboids
コンテスト中の提出
https://atcoder.jp/contests/abc361/submissions/55263076
2点$${(a, b, c), (d, e, f)}$$を結ぶ線分を対角線とする直方体を$${C(a,b,c,d,e,f)}$$とする。
$${C(a,b,c,d,e,f)}$$と$${C(g,h,i,j,k,l)}$$が重なっているかどうか判定してね。
ABC343-Eと少し似ています。（？？？）
また前回の記事のD問題と同じ文章を引用します。
区間$${[l_i, r_i]}$$と$${[l_j, r_j]}$$が共通部分をもつとき、共通部分に含まれる数$${a}$$の範囲は以下のようになります。
$${\max(l_i, l_j) \le a \le \min(r_i, r_j)}$$
（参考）ABC343 - E - 7x7x7
C(a, b, c, d, e, f) とは
「2点$${(a, b, c), (d, e, f)}$$を結ぶ線分を対角線とする直方体」は以下のように言い換えることができます。
$${x}$$軸方向について、$${a < x < d}$$の範囲に直方体がある。
$${y}$$軸方向について、$${b < y < e}$$の範囲に直方体がある。
$${z}$$軸方向について、$${c < z < f}$$の範囲に直方体がある。
何を判定すればよいのか？
上記より、「$${C(a,b,c,d,e,f)}$$と$${C(g,h,i,j,k,l)}$$が重なっている」とは、以下の3つを満たすことと同じになります。
$${a < x < d}$$と$${g < x < j}$$が共通部分をもつ。
$${b < y < e}$$と$${h < y < k}$$が共通部分をもつ。
$${c < z < f}$$と$${i < z < l}$$が共通部分をもつ。
一次元で考えてみる
たとえば、2つの区間$${3 < x < 10}$$と$${5 < x < 12}$$の共通部分について考えてみます。
$$
\begin{rcases}
3 < x < 10 \\
かつ \\
5 < x < 12
\end{rcases}
\rArr 5 < x < 10
$$
これは感覚的に分かりやすいですね。共通部分$${5 < x < 10}$$の長さ$${L_x}$$は$${L_x = 10 - 5 = 5}$$です。
プログラミングで扱えるような式に直すと次のようになります。
$$
\begin{rcases}
3 < x < 10 \\
かつ \\
5 < x < 12
\end{rcases}
\rArr \max(3, 5) < x < \min(10, 12)
$$
次に、共通部分がない場合はどうでしょうか。
$$
\begin{rcases}
3 < x < 10 \\
かつ \\
15 < x < 22
\end{rcases}
\rArr 15 < x < 10 (?)
$$
上と同じように$${15 < x < 10}$$の長さ$${L_x}$$を求めようとすると$${L_x= 10 - 15 = -5}$$です。負の長さは困るので$${L_x = 0}$$とみなします。
さて、$${a < x < d}$$と$${g < x < j}$$の共通部分について考えてみます。
$$
\begin{rcases}
a < x < d \\
かつ \\
d < x < j
\end{rcases}
\rArr \max(a, g) < x < \min(d, j)
$$
共通部分の長さ$${L_{x}}$$は$${s = \max(a, g), t = \min(d, j)}$$として、$${L_{x} = \max(0, t - s)}$$です。
$${y, z}$$軸も同様に$${L_{y}, L_{z}}$$を求めることで、2つの直方体が重なっている領域の体積$${V}$$が判明します。
$${V = L_x \times L_y \times L_z}$$であり、$${V>0}$$なら答えは 'Yes' です。
def length(a, d, g, j):
""" 区間 [a,d], [g,j] の共通部分の長さを求める """
s = max(a, g)
t = min(d, j)
return max(0, t - s)
""" 入力を受け取る """
a,b,c,d,e,f = map(int, input().split())
g,h,i,j,k,l = map(int, input().split())
""" x, y, z 軸それぞれで、共通部分の 長さ を調べる """
Lx = length(a, d, g, j)
Ly = length(b, e, h, k)
Lz = length(c, f, i, l)
""" 直方体の共通部分の 体積 を調べる """
V = Lx * Ly * Lz
if V > 0:
print('Yes')
else:
print('No')実際には、体積まで求める必要はありません。
共通部分の長さ$${L = 0}$$であるものがあれば、答えは 'No' です。
$${L = \max(0, t - s)}$$なので、$${t - s \le 0}$$を判定すればよいです。
""" 共通部分の長さが 0 以下なら NG """
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(3):
s = max(A[i], B[i])
t = min(A[i + 3], B[i + 3])
if t - s <= 0:
print('No')
exit()
print('Yes')ほぼABC343-Eの記事のコピペな内容になってしまいました。
C問題 - Make Them Narrow
コンテスト中の提出
https://atcoder.jp/contests/abc361/submissions/55277263
長さ$${N}$$の数列$${A}$$が与えられる。
$${A}$$から$${K}$$個の要素を取り除いた数列を$${B}$$とする。
$${\max(B) - \min(B)}$$の最小値を出力してね。
$${A}$$から1つ要素を取り除く操作をくり返して、最大値・最小値の差を少しずつ変化させていくことを考えてみます。
ある時点での$${A}$$から、最大値でも最小値でもない要素を取り除いても最大値・最小値に変化はありません。
このことから、常にある時点での最大値または最小値どちらかと一致する要素を取り除いた方がよさそうです。
そうすると、$${K}$$回の操作の後、最終的に$${A}$$の小さい順に$${l}$$個、大きい順に$${r}$$個の要素を取り除いたことになります。
上記をふまえると、ソートした後の$${A}$$について、左から$${l}$$個、右から$${r}$$個の要素を取り除けばよいと考えることができます。
$${l + r = K}$$であり、$${K < 2 \times 10^5}$$なので、$${(l,r)}$$を全探索できます。
このとき、最小値は$${A_{l+1}}$$、最大値は$${A_{N-r}}$$となります。
全探索した$${(l,r)}$$のうち、$${A_{N-r}-A_{l+1}}$$を最小にするものを採用すればよいです。
""" 入力を受け取る """
N, K = map(int, input().split())
A = list(map(int, input().split()))
""" A をソートして、A の左から l 個、右から r 個を取り除く """
A.sort()
ans = 10 ** 9
for l in range(K + 1):
r = K - l
ans = min(ans, A[N - r - 1] - A[l])
print(ans)D問題 - Go Stone Puzzle
コンテスト中の提出
https://atcoder.jp/contests/abc361/submissions/55292903
$${N+2}$$個のマスが一列に並んでいる。
マス$${1 \le i \le N}$$について、$${i}$$番目のマスには石$${S_i}$$が置かれている。マス$${N+1, N+2}$$は空きマス。
石の色は、$${S_i}$$ = 'W' なら白、$${S_i}$$ = 'B' なら黒。
操作: 2個並んでいる石を、空きマスに移動する。
石の並びを$${T}$$にするための最小の操作回数を出力してね。
$${N \le 14}$$であり、$${2^{N+2} \le 65536}$$程度なので配置パターンを全探索できそうな予感がします。
（実際には石と空きマスの並べ方は$${2^{N+2}}$$通りではありませんが。）
入力の時点では空きマスが含まれていないので、$${S,T}$$の後ろに2マス分空きマスとして '.' をくっつけておきます。
""" 入力を受け取る """
N = int(input())
S = input() + '..'
T = input() + '..'操作については、現在の文字列に対して移動させる2つの石を全探索し、空きマスと入れ替えて作られる新しい文字列をすべて調べるとよいです。
たとえば$${S=\text{'BWW..'}}$$だった場合、操作後は$${S=\text{'..WBW'}}$$にすることができます。
""" 石 (i, i + 1) を、空きマス (x, x + 1) と入れ替える """
x = curr.index(".")
for i in range(N + 1):
if curr[i] != '.' and curr[i + 1] != ".":
nxt = list(curr)
nxt[i], nxt[i + 1] = curr[x], curr[x + 1]
nxt[x], nxt[x + 1] = curr[i], curr[i + 1]
nxt = ''.join(nxt)配置を表す文字列を頂点、操作による文字列の遷移を辺とするとグラフ問題とみなせそうです。
操作の最小回数を求めたい、すなわち移動する辺の本数を最小化したいことから最短経路問題となり、BFSで解くことができます。
文字列を頂点とするので、リストではなく dict を使います。
遷移可能な文字列をすべて列挙しても$${T}$$を作れないこともあります。その場合、答えは -1 となります。
from collections import deque, defaultdict
def edges(curr):
""" 石 (i, i + 1) を、空きマス (x, x + 1) と入れ替える """
x = curr.index(".")
for i in range(N + 1):
if curr[i] != '.' and curr[i + 1] != ".":
nxt = list(curr)
nxt[i], nxt[i + 1] = curr[x], curr[x + 1]
nxt[x], nxt[x + 1] = curr[i], curr[i + 1]
yield ''.join(nxt)
""" 入力を受け取る """
N = int(input())
S = input() + '..'
T = input() + '..'
""" 石の配置パターンを頂点としたBFS """
inf = 1 << 60
res = defaultdict(lambda: inf)
res[S] = 0
dq = deque([S])
while dq:
curr = dq.popleft()
for nxt in edges(curr):
if res[nxt] == inf:
res[nxt] = res[curr] + 1
dq.append(nxt)
""" 答えを出力 """
if res[T] == inf:
print(-1)
else:
print(res[T])参考コードとしてシンプルなBFSっぽい見た目になるので yield を採用しています。
yield を使わない実装は以下のようになります。
""" そのまま実装 """
inf = 1 << 60
res = defaultdict(lambda: inf)
res[S] = 0
dq = deque([S])
while dq:
curr = dq.popleft()
x = curr.index(".")
""" 石 (i, i + 1) を、空きマス (x, x + 1) と入れ替える """
for i in range(N + 1):
if curr[i] != '.' and curr[i + 1] != ".":
nxt = list(curr)
nxt[i], nxt[i + 1] = curr[x], curr[x + 1]
nxt[x], nxt[x + 1] = curr[i], curr[i + 1]
nxt = ''.join(nxt)
if res[nxt] == inf:
res[nxt] = res[curr] + 1
dq.append(nxt)E問題 - Tree and Hamilton Path 2
upsolve
https://atcoder.jp/contests/abc361/submissions/55456331
$${N}$$頂点の木がある。
$${i}$$番目の辺は頂点$${A_i, B_i}$$を結び、コスト$${C_i}$$。
すべての頂点を訪れるための最小コストを出力してね。
いくつかの辺は往復する必要があります。
DFS の探索順にすべての頂点を訪れると、それぞれの辺を2回ずつ通るので、$${\displaystyle 2 \sum_{i=1}^{N-1}C_i}$$だけコストがかかります。
ここで、ある2頂点$${u, v}$$間の移動コストを$${d}$$としたとき、全ての辺を往復する経路に比べてトータルのコストを$${d}$$だけ減らすことができます。
この$${d}$$を最大化したとき、求めたい最小コストを得ることができ、そのような$${d}$$は木の直径になります。
木の直径は、以下の手順で求めることができます。
任意の頂点 (下記コードでは頂点$${1}$$) から最も遠い頂点$${u}$$を調べる。
頂点$${u}$$から最も遠い頂点$${v}$$を調べる。
木の直径は、頂点$${u}$$から頂点$${v}$$までの移動コスト。
""" DFS で実装 """
from sys import setrecursionlimit
setrecursionlimit(100100100)
def dfs(curr, prev, dp):
""" ある根から、各頂点までの距離を求める """
for nxt, cost in G[curr]:
if nxt != prev:
dp[nxt] = dp[curr] + cost
dfs(nxt, curr, dp)
""" 入力を受け取る """
N = int(input())
G = [[] for _ in range(N + 1)]
total = 0
for _ in range(N - 1):
a, b, c = map(int, input().split())
G[a].append((b, c))
G[b].append((a, c))
total += c
""" 木の直径 d を求める """
dp0 = [0] * (N + 1)
dp1 = [0] * (N + 1)
dfs(1, -1, dp0)
u = dp0.index(max(dp0))
dfs(u, -1, dp1)
d = max(dp1)
""" 答えは (コストの総和) * 2 - (木の直径) """
ans = total * 2 - d
print(ans)再帰実装の DFS を扱う場合、PyPy で提出すると TLE になります。
CPython であれば 1000 ms 程度で間に合います。
非再帰の BFS で実装すると PyPy で問題ありません。
""" BFS で実装 """
from collections import deque
def bfs(start):
""" ある根から、各頂点までの距離を求める """
inf = 1 << 60
dq = deque([start])
dist = [inf] * (N + 1)
dist[start] = 0
while dq:
curr = dq.popleft()
for nxt, cost in G[curr]:
if dist[nxt] == inf:
dist[nxt] = dist[curr] + cost
dq.append(nxt)
dist[0] = -1 # 1-indexなので余分な頂点 0 を処理
return dist
""" 入力を受け取る """
N = int(input())
G = [[] for _ in range(N + 1)]
total = 0
for _ in range(N - 1):
a, b, c = map(int, input().split())
G[a].append((b, c))
G[b].append((a, c))
total += c
""" 木の直径 d を求める """
dp0 = bfs(1)
u = dp0.index(max(dp0))
dp1 = bfs(u)
d = max(dp1)
""" 答えは (コストの総和) * 2 - (木の直径) """
ans = total * 2 - d
print(ans)「競プロ典型90問」にも木の直径を求める回があります。
あとがき
今回は ABCD 4完 49分で 2413位でした。
外出先からの参加でいつもと違う環境だったのでUnrated参加しました。
Ratedならレートが+5くらいしてそうな順位。
ではまた～。
【更新履歴】
2024/07/11 (19時頃)：記事投稿。
この記事が気に入ったらサポートをしてみませんか？