丸紅プログラミングコンテスト2024(AtCoder Regular Contest 183)A,B,C,D問題メモ
問題文
正整数 $N,K$ が与えられます.
$1$ 以上 $N$ 以下の整数がそれぞれ $K$ 回ずつ登場する長さ $NK$ の整数列を good な整数列と呼ぶことにします.
good な整数列の個数を $S$ とおきます.
辞書順で $\operatorname{floor}((S+1)/2)$ 番目の good な整数列を求めてください.
なお,$\operatorname{floor}(x)$ は $x$ を超えない最大の整数を表します.
制約
$1 \leq N \leq 500$
$1 \leq K \leq 500$
入力される値はすべて整数
解法
あれこれ考えるより、実際に愚直に求めるプログラムを実装して簡単な例から法則を見つけ出す方が速い。
$N$ の偶奇で分かれる。
偶数(たとえば6)の時、先頭の1文字が $1~3$ と $4~6$ のgoodな整数列の個数は等しい。
よって、先頭の1文字が $3$ のgoodな整数列の辞書順最後のものが答えとなる。
N=6 K=3
↓
3 6 6 6 5 5 5 4 4 4 3 3 2 2 2 1 1 1
奇数(たとえば5)の時、先頭の1文字が $1~2$ と $4~5$ のgoodな整数列の個数は等しい。
というわけで先頭1文字目は真ん中の $3$ である。
その中で、2文字目が $1~2$ と $4~5$ のgoodな整数列の個数は等しい。
2文字目も $3$ となる。
連鎖的に考えていくと、先頭 $K$ 文字は $3$(つまり、$\frac{N+1}{2}$)となる。
その後は、$3$ を除いた $1,2,4,5$ で偶数の時と同じことが言えて、「先頭が $2$ の辞書順最後」を後に繋げればよい。
N=5 K=3
↓
3 3 3 2 5 5 5 4 4 4 2 2 1 1 1
Python3
from itertools import permutations
def bruteforce(n, k):
a = []
for i in range(1, n + 1):
a.extend([i] * k)
print(a)
aaa = set(permutations(a))
aaa = sorted(aaa)
for i, a in enumerate(aaa):
print(i, a)
s = len(aaa)
print((s + 1) // 2 - 1)
print(aaa[(s + 1) // 2 - 1])
n, k = map(int, input().split())
# bruteforce(n, k)
if n == 1:
ans = [n] * k
print(*ans)
exit()
m = (n + 1) // 2
if n % 2 == 0:
ans = [m]
for i in range(n, 0, -1):
if i == m:
ans.extend([i] * (k - 1))
else:
ans.extend([i] * k)
else:
ans = [m] * k
ans.append(m - 1)
for i in range(n, 0, -1):
if i == m:
pass
elif i == m - 1:
ans.extend([i] * (k - 1))
else:
ans.extend([i] * k)
print(*ans)
B - Near Assignment
問題文
長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N),B=(B_1,B_2,\cdots,B_N)$ 及び整数 $K$ が与えられます.
あなたは次の操作を $0$ 回以上行うことができます.
整数 $i,j$ ($1 \leq i,j \leq N$) を選ぶ.ただしここで $|i-j| \leq K$ を満たす必要がある.
そして $A_i$ の値を $A_j$ に変更する.
$A$ を $B$ に一致させることが可能かどうか判定してください.
$1$ つの入力につきテストケースは $T$ 個あります.
制約
解法
公式解説を読んでの自分用のメモ。
行える操作の候補数が多すぎて、簡単なケースでも「このケースは不可能っぽく見えるが、本当に不可能か?」を確認するのが
手作業でも、愚直なプログラムを実装するのでも難しい。
操作を逆から考えると上手くいく。
「どうしたらこれで上手くいくと着想できるか?」といわれると難しい。(一応、よくある解法としてセオリーの1つではあるが)
簡単に判定可能なケース
はじめから $A=B$ の場合はもちろんOK。
操作で $A$ にない値を作り出すことはできないので、$B$ に $A$ に無い値が含まれる場合はNG。
また、$K=1$ の場合は、数字を飛び越えることができないので別に扱う。
この場合、並び順を変えない限り、各要素の連続する個数を自由に変えられる。(0個にすることも含め)
よって、ランレングス圧縮して、$B$ が $A$ の部分列であればよい。
一般のケース
上記以外の場合、「最後の操作」を考える。
操作では $A_i$ を $A_j$ に上書きするため、当然、操作直後は $A_i=A_j$ となっている。
これが $B$ と一致するので、$B$ では $K$ 以下離れた2つの要素が同じである箇所が、少なくとも1つなければならない。
K = 2
A 1 2 3 4 5
B 5 5 1 2 1 ← ○: 1か5を最後に操作したと解釈できる
A 1 2 3 4 5
B 5 1 3 2 1 ← ×: 最後に操作したと解釈できる要素がない。NG
最後の操作の直前では、$A_i$ の値は何であったと仮定してもよい。これをワイルドカード * とする。
K = 2
A 1 2 3 4 5
B 5 5 1 2 1
5 5 * 2 1 最後の操作の直前の一例
操作を逆順に考え、$B$ を $A$ に合致させることを目指す。
たとえば * が $2$ であったとすると、最後の操作と同様に $K$ 以下離れた同じ値の一方を * にできる。
5 5 * 2 1 最後の操作の直前の一例。
5 5 2 2 1 ...であったと仮定し、
5 5 2 * 1 とできる
これは、結果的に「* を $K$ 以下離れた値とスワップした」と解釈できる。
よって、$K \ge 2$ であれば、スワップを繰り返して好きな値を好きな位置に持っていくことができる。
A 1 2 3 4 5
5 5 2 * 1 K=2で1を左端に持っていく例
5 5 2 1 *
5 5 * 1 2
5 5 1 * 2
5 * 1 5 2
5 1 * 5 2
* 1 5 5 2
1 * 5 5 2
$B$ に無い値(または個数が足りない値)は、* を1個消費してその値に変えなければならない。
ただ、$B$ に無い値があるということは、$B$ ではその分だけ、別の値が重複しているということになる。
同じ値を端に固めれば、* を作り出すことができる。
A 1 2 3 4 5 6 7 8 9
B 1 9 1 8 1 7 1 6 1
↓
1 1 1 1 * 9 8 7 6
↓
1 * * * * 9 8 7 6
これで、$K \ge 2$ の場合は、最初の取っかかりさえあれば可能だということが分かった。
距離 $K$ 以内に同じ値がある箇所が1箇所でもあればOK、なければNGとなる。
Python3
from collections import defaultdict
from operator import itemgetter
from more_itertools.more import run_length
def solve(n, k, aaa, bbb):
if k == 1:
rla = list(map(itemgetter(0), run_length.encode(aaa)))
rlb = list(map(itemgetter(0), run_length.encode(bbb)))
m = len(rlb)
j = 0
for a in rla:
if rlb[j] == a:
j += 1
if j == m:
return True
return False
if aaa == bbb:
return True
if set(bbb) - set(aaa):
return False
last_appear = defaultdict(lambda: -1000_000_000)
for i, b in enumerate(bbb):
la = last_appear[b]
if i - la <= k:
return True
last_appear[b] = i
return False
t = int(input())
buf = []
for _ in range(t):
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
if solve(n, k, aaa, bbb):
buf.append('Yes')
else:
buf.append('No')
print('\n'.join(buf))
C - Not Argmax
問題文
$(1,2,\cdots,N)$ の順列 $P=(P_1,P_2,\cdots,P_N)$ であって,次の $M$ 個の条件をすべて満たすものの個数を $998244353$ で割ったあまりを求めてください.
制約
解法
区間DP。
本番中にも区間DPの可能性は考えていたが、
「$DP[l,r]$ を求めるのに、$DP[l,m]$ と $DP[m,r]$ を統合した結果と、
$DP[l,m+1]$ と $DP[m+1,r]$ を統合した結果を足したら重複しちゃうな」
など謎の勘違いで行き詰まっていた。
区間DP
$M$ 個の「条件」は、一般名詞と混同しないよう「禁止条件」と表現する。
また、禁止条件で指定された $[L_i,R_i]$ の区間は「禁止区間」と表現し、区間DPで考慮中の「区間」と区別する。
$\mathrm{DP}[l,r]$ を求めるにあたり、
区切る場所 $m$ を様々に変えた結果の重複を防ぐためには、何かしら、排反事象で場合分けする必要がある。
今回の場合、分ける位置 $m$ を「区間内の最大値を置く場所」と考えると上手くいく。
以下、禁止条件は、$[l,r)$ に内包されるもののみを考慮の対象とする。
まず、禁止条件のうち、$X_i=m$ であるようなものがある場合、
$m$ に最大値を置いたら、当然、内包される禁止区間 $[L_i,R_i]$ の中でも最大値になる。
したがって、$m$ には区間最大値は置けない。
以下、$X_i=m$ となる禁止条件が無いとする。無いなら、$m$ に最大値を置ける。
その時の $[l,r)$ の他の値の決め方を求めたい。
禁止区間中に $m$ を含む禁止条件は、もう満たされている。
なぜなら、$m$ が最大値となったため、$X_i \ (\neq m)$ は最大値であり得なくなったから。
残りの禁止条件は、区間 $[l,m)$ または $[m+1,r)$ に内包され、それぞれのDPで既に考慮されている。
この2区間は、左右独立に決められる。
ただし、「相対的な大きさ」を左右で統合するにあたり、${}_{r-l-1}\mathrm{C}_{m-l}$ を掛け合わせる必要がある。
これで求められる。$\displaystyle \mathrm{DP}[l,r] = \sum_{m=l}^{r-1} f(l,r,m)$ となる。
$X_i=m$ である禁止区間の存在判定
上記の区間DPでネックとなるのが、「考慮中の区間 $[l,r)$ に内包された禁止条件で、$X_i=m$ であるものがあるか?」を、
各 $(l,r,m)$ につき高速に判定しなければならない点である。
区間DPの時点で、$l,r,m$ の探索に $O(N^3)$ かかり
($\frac{1}{6}$ ほどの定数倍がかかるが、$N=500$ として約 $2 \times 10^7$)、
ほぼ $O(1)$ で判定できなければ間に合わない。
ここで、区間 $(l,r)$ や禁止区間 $(L_i,R_i)$ を2次元座標に落とすと、
$(l,r)$ に内包される禁止条件というのは、右下の範囲になる。
R ^
| |
r |----+----
| |ここ
-+----|----> L
l
$N \times N$ の2次元配列に bitset を使って
禁止条件 $L_i,R_i,X_i$ に対して、$(L_i,R_i)$ に $X_i$ 番目のbitを立てる
全ての禁止条件を立て終わった後、右下から、bitwise-or で累積和を取る
としておくと、全ての $(l,r)$ につき、そこに内包される禁止条件で指定されている $X_i$ の集合がわかる。
500bitを表現するのに64bit整数を9個ほど使うので定数倍は重くなるが、
$l,r$ が小さい間はbitsetの最大桁もそんなに大きくならないことなどから、なんとか間に合う。
Python3
def precompute_factorials(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f = f * m % MOD
factorials.append(f)
f = pow(f, MOD - 2, MOD)
finvs = [1] * (n + 1)
finvs[n] = f
for m in range(n, 1, -1):
f = f * m % MOD
finvs[m - 1] = f
return factorials, finvs
MOD = 998244353
n, m = map(int, input().split())
banned = [[0] * (n + 1) for _ in range(n)]
for _ in range(m):
l, r, x = map(int, input().split())
l -= 1
x -= 1
banned[l][r] |= 1 << x
facts, finvs = precompute_factorials(n, MOD)
for i in range(n - 1, 0, -1):
for j in range(n + 1):
banned[i - 1][j] |= banned[i][j]
for j in range(n):
for i in range(n):
banned[i][j + 1] |= banned[i][j]
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
if banned[i][i + 1] == 0:
dp[i][i + 1] = 1
dp[i][i] = 1
dp[n][n] = 1
for w in range(2, n + 1):
comb = []
for i in range(w):
comb.append(facts[w - 1] * finvs[i] * finvs[w - 1 - i] % MOD)
for l in range(n - w + 1):
r = l + w
bitset = banned[l][r]
tmp = 0
for m in range(l, r):
if bitset >> m & 1:
continue
tmp += dp[l][m] * dp[m + 1][r] * comb[m - l]
tmp %= MOD
dp[l][r] = tmp
ans = dp[0][n]
print(ans)
D - Keep Perfectly Matched
問題文
$1$ から $N$ までの番号のついた $N$ 頂点からなる木があります.
$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結ぶ辺です.
ここで $N$ は偶数で,さらにこの木は完全マッチングを持ちます.
あなたは以下の操作を $N/2$ 回行います.
葉 (次数がちょうど $1$ の頂点) を $2$ つ選び,木から削除する.
ただしここで,削除したあとの木も完全マッチングを持つ必要がある.
なお,この問題では頂点が $0$ 個の場合も木と呼ぶことにする.
各操作について,そのスコアを「選んだ $2$ つの頂点の間の距離 (その $2$ つの頂点を結ぶ単純パス上の辺の個数) 」とします.
スコアの合計を最大化するような手順を $1$ つ示してください.
なお,この問題の制約下で $N/2$ 回の操作を完了する手順が常に存在することが証明できます.
制約
$2 \leq N \leq 250000$
$N$ は偶数
$1 \leq A_i \lt B_i \leq N$ ($1 \leq i \leq N-1$)
$A_i=i \times 2 -1,B_i=i \times 2$ ($1 \leq i \leq N/2$)
与えられるグラフは木である
解法
距離の最大化
木から頂点を2つずつ取って距離の総和を最大化、という問題は最近のABCでも類題がある。
一応ネタバレ注意
木の重心を必ず通るような2点を選んでいけばよい。
言い換えると、重心 $c$ を根として、$c$ の相異なる2つの子の部分木から、葉を1個ずつ取ってきてペアにすればよい。
(同じ部分木内の2つをペアにする、ということをしなければよい)
完全マッチングの保ち方
今回は「完全マッチングを保つ」という制約もあるため、どれでも好きな頂点を選ぶわけにはいかない。
1つの方法として、2点を結ぶパスが「マッチングに使われる辺と使われない辺が交互になる」ようなペアを取ると、
ペアを削除しても完全マッチングが保たれる。
この時、他の枝のマッチングはこのパス上の頂点のマッチングには影響しない。
◎==○--○==○--○==○--○==◎
○==○--' `--○==○
↓
○==○--○==○--○==○
○==○--' `--○==○
ペア $(u,v)$ を「根の相異なる2つの子の部分木から、その間のパスがマッチング使用/不使用辺を交互に使うように選ぶ」という観点で考えると、
ペアの1つ $u$ はその時点で根とマッチングしている子頂点(下記例①を根として②)の部分木から選ぶ必要がある。
①
⇙↓↘ ⇒:マッチングに使われている辺
② ③ ⑦ →:それ以外の辺
: ⇙↘ :
④ ⑤
: :
もう1つ $v$ は、他のどの子の部分木でもよい。
ただし、$u,v$ いずれも、根からその頂点まで辿る時に
①→③→⑤のようにマッチングに使われない辺を2回連続で辿ることはダメ。
「子とマッチングしている頂点」からは必ずマッチングしている頂点(③に対する④)を優先して辿る必要がある。
これが保たれるようにするには、根の各子頂点(②③⑦)の部分木に対し、以下のように使用順を決めるとよい。
この帰りがけ順が、その部分木内で「マッチングに使われない辺を2回連続で通らない」ように頂点を選ぶ順番の1つの例となる。
ペアの構築方法
木の重心を根と見なし、根とマッチングしている子の部分木を $m$、それ以外の子の部分木を $C=(c_1,c_2,...)$ とする。
$m,c_1,c_2,...$ のそれぞれからオイラーツアーの帰りがけ順で、その中の使用順を決めておく。
以下を $\frac{N}{2}-1$ 回繰り返せばよい。
この時、最後まで部分木が2つ以上残るように、部分木サイズが大きい子から使用していく。
$C$ から1つ選ぶ際、頂点数が大きい方から取り出せる優先度付きキューを使うとよい。
最後に、$m$ に1つだけ残った頂点と根をペアとしたものを追加して、答えとなる。
Python3
from collections import defaultdict
from heapq import heapify, heappop, heappush
from typing import Iterable, List, Set, Optional, Dict, Tuple
def get_centroid(n: int, links: List[Iterable[int]], s: int, removed: Optional[Set[int]] = None) \
-> Tuple[List[int], Dict[int, int]]:
"""
木の重心を見つける。
重心は1つまたは2つあるため、リストで返す。また、s を根とした際の部分木のサイズも返す。
繰り返し重心分解する場合にも適用可能。
removedには既に重心として確定された頂点集合を与え、そこにある頂点は探索されないようになる。
n には木全体ではなく、探索範囲の頂点数を与える。(1回前に探索した部分木のサイズから計算できる)
:param n: 木の(探索範囲の)頂点数
:param links: 隣接リスト
:param s: 探索開始頂点
:param removed: 探索しない頂点集合
:return:
"""
if removed is None:
removed = set()
parents = {s: -1}
subtree_sizes = {s: n}
status = defaultdict(int)
q = [s]
limit = n // 2
centroid = []
while q:
u = q[-1]
if status[u] == 0:
status[u] = 1
for v in links[u]:
if parents[u] == v:
continue
if v in removed:
continue
parents[v] = u
q.append(v)
else:
status[u] = 2
q.pop()
my = 1
is_centroid = True
for v in links[u]:
if status[v] != 2:
continue
if v in removed:
continue
scv = subtree_sizes[v]
my += scv
if scv > limit:
is_centroid = False
subtree_sizes[u] = my
if n - my > limit:
is_centroid = False
if is_centroid:
centroid.append(u)
return centroid, subtree_sizes
def get_subtree_sizes(n, links, s):
""" s を根とした部分木サイズを構築する。ついでに links から親頂点を削除する """
subtree_sizes = [-1] * n
depths = [-1] * n
depths[s] = 0
q = [s]
while q:
u = q[-1]
dv = depths[u] + 1
if subtree_sizes[u] == -1:
subtree_sizes[u] = -2
p = -1
for v in links[u]:
if subtree_sizes[v] == -1:
q.append(v)
depths[v] = dv
else:
p = v
if p != -1:
links[u].remove(p)
else:
q.pop()
tmp = 1
for v in links[u]:
if subtree_sizes[v] >= 0:
tmp += subtree_sizes[v]
subtree_sizes[u] = tmp
return subtree_sizes, depths
def build_post_order(links: List[List[int]], s: int):
"""
s からオイラーツアーし、帰りがけ順の頂点列を構築する。
links[u] = [v1, v2, ...] は、隣接頂点をリストで持つ。この順に訪れる。
links には、親頂点は入っていない前提とする。
"""
result = []
visited = set()
q = [s]
while q:
u = q[-1]
if u not in visited:
q.extend(reversed(links[u]))
visited.add(u)
else:
q.pop()
result.append(u)
return result
def solve(n, links):
centroids, _ = get_centroid(n, links, 0)
cen = centroids[0]
# 部分木サイズ・深さを計算、linksから親頂点を除く
subtree_sizes, depths = get_subtree_sizes(n, links, cen)
# 奇数サイズの子が1番目に来るように、linksの並び順を加工
links2 = []
for i in range(n):
links2.append(sorted(links[i], key=lambda v: subtree_sizes[v] % 2, reverse=True))
links = links2
root_children = links[cen]
rtch_cnt = len(root_children)
odd_queue = []
even_queue = []
post_orders = []
for i in range(rtch_cnt):
ch = root_children[i]
post_order = build_post_order(links, ch)
post_order.reverse() # pop で取り出すため逆順にする
post_orders.append(post_order)
if depths[post_order[-1]] % 2 == 0:
even_queue.append((-len(post_order), i))
else:
odd_queue.append((-len(post_order), i))
heapify(even_queue)
heapify(odd_queue)
ans = []
for _ in range(n // 2 - 1):
_, i = heappop(even_queue)
_, j = heappop(odd_queue)
poi = post_orders[i]
poj = post_orders[j]
u = poi.pop()
v = poj.pop()
ans.append(f'{u + 1} {v + 1}')
if poi:
if depths[poi[-1]] % 2 == 0:
heappush(even_queue, (-len(poi), i))
else:
heappush(odd_queue, (-len(poi), i))
if poj:
if depths[poj[-1]] % 2 == 0:
heappush(even_queue, (-len(poj), j))
else:
heappush(odd_queue, (-len(poj), j))
_, i = odd_queue[0]
poi = post_orders[i]
v = poi.pop()
ans.append(f'{v + 1} {cen + 1}')
return ans
n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
links[u].add(v)
links[v].add(u)
ans = solve(n, links)
print('\n'.join(ans))