AtCoder Regular Contest 175 A,C,D,E問題メモ

def solve_l(n, ppp, s):
    taken = [0] * n
    result = 1
    for p in ppp:
        if s[p] == 'R' and taken[(p + 1) % n] == 0:
            return 0
        if s[p] == '?' and taken[(p + 1) % n] == 1:
            result *= 2
            result %= 998244353
        taken[p] = 1
    return result


def solve_r(n, ppp, s):
    taken = [0] * n
    result = 1
    for p in ppp:
        if s[p] == 'L' and taken[p] == 0:
            return 0
        if s[p] == '?' and taken[p] == 1:
            result *= 2
            result %= 998244353
        taken[(p + 1) % n] = 1
    return result


n = int(input())
ppp = map(int, input().split())
ppp = [p - 1 for p in ppp]
s = input()

ans = 0
if s[ppp[0]] == 'L' or s[ppp[0]] == '?':
    ans += solve_l(n, ppp, s)
if s[ppp[0]] == 'R' or s[ppp[0]] == '?':
    ans += solve_r(n, ppp, s)
ans %= 998244353
print(ans)

def solve(n, lrs):
    peaks = []
    a = 0
    b = 1 << 60
    is_up = -1
    last_max_ai = -1
    last_min_bi = -1

    for i, (l, r) in enumerate(lrs):
        # print(f'{i=} {l=} {r=} {a=} {b=} {last_max_ai=} {last_min_bi=} {peaks=}')
        if b < l:
            if is_up == 1:
                pass
            else:
                peaks.append((last_min_bi, a, b, 1))
                is_up = 1
                last_max_ai = i
                last_min_bi = i
            a = l
            b = r
            last_max_ai = i
        elif r < a:
            if is_up == 0:
                pass
            else:
                peaks.append((last_max_ai, a, b, 0))
                is_up = 0
                last_max_ai = i
                last_min_bi = i
            a = l
            b = r
            last_min_bi = i
        else:
            if a <= l:
                a = l
                last_max_ai = i
            if b >= r:
                b = r
                last_min_bi = i

    if is_up == -1:
        return [a] * n

    if is_up == 1:
        peaks.append((last_max_ai, a, b, 0))
    else:
        peaks.append((last_min_bi, a, b, 1))

    ans = []
    if peaks[0][3] == 0:
        ans.extend([peaks[0][1]] * peaks[0][0])
    else:
        ans.extend([peaks[0][2]] * peaks[0][0])
    for i in range(len(peaks) - 1):
        i1, a1, b1, u1 = peaks[i]
        i2, a2, b2, u2 = peaks[i + 1]
        if u1 == 1:
            t = b1
            for j in range(i1, i2):
                t = max(t, lrs[j][0])
                ans.append(t)
        else:
            t = b2
            tmp = []
            for j in range(i2 - 1, i1 - 1, -1):
                t = max(t, lrs[j][0])
                tmp.append(t)
            tmp.reverse()
            ans.extend(tmp)
    k = n - peaks[-1][0]
    if peaks[-1][3] == 0:
        ans.extend([peaks[-1][1]] * k)
    else:
        ans.extend([peaks[-1][2]] * k)

    return ans


n = int(input())
lrs = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, lrs)
print(*ans)

def solve(n, lrs):
    ans = []
    tmp = 0
    for l, r in lrs:
        if tmp > r:
            tmp = r
            ans.append(tmp)
        else:
            tmp = max(tmp, l)
            ans.append(tmp)

    return ans


def adjust_start_end(ans1, ans2, lrs):
    ans = [min(a1, a2) for a1, a2 in zip(ans1, ans2)]

    l0, r0 = lrs[0]
    for i, (l, r) in enumerate(lrs):
        if r0 < l:
            ans[:i] = [r0] * i
            break
        if l0 > r:
            ans[:i] = ans2[:i]
            break
        l0 = max(l0, l)
        r0 = min(r0, r)
    else:
        return [l0] * n

    l0, r0 = lrs[-1]
    for i, (l, r) in enumerate(reversed(lrs), start=1):
        if l > r0:
            ans[-i + 1:] = [r0] * (i - 1)
            break
        if r < l0:
            ans[-i + 1:] = ans1[-i + 1:]
            break
        l0 = max(l0, l)
        r0 = min(r0, r)

    return ans


n = int(input())
lrs = [tuple(map(int, input().split())) for _ in range(n)]

ans1 = solve(n, lrs)
ans2 = solve(n, reversed(lrs))
ans2.reverse()
ans = adjust_start_end(ans1, ans2, lrs)

print(*ans)

• 命題
  • $W_v$ を「頂点 $v$ の部分木の頂点数」とする。
  • 頂点数 $N$ の任意の木において、以下が成立する。
    • $(W_1,W_2,...,W_N)$ からいくつかを重複なく選んで、和を $0,1,...,\sum{W_i}$ の任意の値にすることができる

数学的帰納法により証明できる。

$N=1$ の場合、$W=(1,)$ であり、命題は成立する。

$N=k$ である場合について考える。根を $v$ とする。
$1 \le i \le k-1$ なる全ての $i$ について、$N=i$ で命題が成立するとする。

頂点 $v$ の部分木に含まれる全頂点における $W_i$ の合計を $M_v$ とする。

$v$ の子を $u_1,u_2,...$ とする。いずれも頂点数は $k$ 未満より命題が成立している。

$u_1$ 以下の部分木を選ぶことで $0～M_{u1}$、$u_2$ 以下の部分木から選ぶことで $0～M_{u2}$、、、を好きに作れるので、 合わせることで $0～(M_{u1}+M_{u2}+...)=M_v-W_v$ の好きな値を作れる。

ここで $W_v$ も採用する/しないを選べるので、$0～M_v$ の好きな値を作れることになる。
よって、$N=k$ の場合でも成立することが示された。

また、$v$ の部分木で総和を $0～M_v$ の任意の値 $S$ にしたいとき、$v$ 以外の頂点で $0～M_v-W_v$ の任意の値が作れるので、貪欲にとって問題ないことも示された。

from operator import itemgetter

n, k = map(int, input().split())
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)

depth = [1] * n
parents = [-1] * n
visit_order = [0]
q = [0]
while q:
    u = q.pop()
    for v in links[u]:
        parents[v] = u
        depth[v] = depth[u] + 1
        links[v].remove(u)
        q.append(v)
        visit_order.append(v)

max_fp = sum(depth)
if not (n <= k <= max_fp):
    print('No')
    exit()

subtree_weights = [0] * n
for u in reversed(visit_order):
    subtree_weights[u] = sum(subtree_weights[v] for v in links[u]) + 1

switch_parent_edge = [0] * n
remaining_decrease = max_fp - k
sws = sorted(enumerate(subtree_weights), reverse=True, key=itemgetter(1))
for u, w in sws[1:]:
    if remaining_decrease >= w:
        switch_parent_edge[u] = 1
        remaining_decrease -= w

assert remaining_decrease == 0

subtree_switch_count = [0] * n
for u in reversed(visit_order):
    subtree_switch_count[u] = sum(subtree_switch_count[v] + switch_parent_edge[v] for v in links[u])

ssc0 = subtree_switch_count[0]
q = [(0, 1, 1 + ssc0, 1 + ssc0, n + 1)]  # 頂点 u 以下、親と逆転させる頂点に [sl, sr), させない頂点に [tl, tr) を割り当てる
ans = [0] * n
while q:
    u, sl, sr, tl, tr = q.pop()
    # print(f'{u=} {sl=} {sr=} {tl=} {tr=}')
    if switch_parent_edge[u]:
        ans[u] = sr - 1
        sr -= 1
    else:
        ans[u] = tl
        tl += 1
    for v in links[u]:
        ssc = subtree_switch_count[v] + switch_parent_edge[v]
        sw = subtree_weights[v]
        q.append((v, sl, sl + ssc, tl, tl + (sw - ssc)))
        sl += ssc
        tl += sw - ssc

print('Yes')
print(*ans)

from collections import defaultdict

n, k = map(int, input().split())
# N^2 個フルで置いたときに、xy,yz,zx が全て同じになる配置。1つずらすことで、必ず (0,0,0) が入るようになる。
row_base = list(range(n))
row_base.reverse()
xy = []
for i in range(n):
    xy.append(row_base[i:] + row_base[:i])
xy.insert(0, xy.pop())

d1 = defaultdict(list)  # 3つ全て一緒の1つ組
d2 = defaultdict(list)  # 3個中2個が一緒の3つ組。2個あるものを3つ使った(x,x,x)の1つ組に置き換え可能。
d3 = defaultdict(list)  # 全て異なる3つ組
for x in range(n):
    for y in range(n):
        z = xy[x][y]
        key = min((x, y, z), (y, z, x), (z, x, y))
        if key[0] == key[1] and key[1] == key[2]:
            d1[key].append((x, y, z))
        elif key[0] == key[1] or key[1] == key[2]:
            d2[key].append((x, y, z))
        else:
            d3[key].append((x, y, z))

assert len(d1) > 0

grp1 = list(d1.values())
grp2 = list(d2.values())
grp3 = list(d3.values())

ans = []
while k > 0:
    if k >= 3 and grp3:
        ans.extend(grp3.pop())
        k -= 3
    elif k >= 3 and grp2:
        ans.extend(grp2.pop())
        k -= 3
    elif grp2:
        x, y, z = grp2.pop()[0]
        if x == y or x == z:
            ans.append((x, x, x))
        else:
            ans.append((y, y, y))
        k -= 1
    elif grp1:
        ans.extend(grp1.pop())
        k -= 1
    else:
        raise AssertionError

print('\n'.join(f'{x} {y} {z}' for x, y, z in ans))