AtCoder Regular Contest 175 A,C,D,E問題メモ
A - Spoon Taking Problem
問題
$N$ 人が円卓に座り、各人の間に $N$ 本のスプーンがある(元の問題文中の図参照)
順列 $P=(P_1,P_2,...,P_N)$ と、'L','R','?' からなる長さ $N$ の文字列 $S$ が与えられる
'?' を 'L' または 'R' で置き換えた文字列 $T$ は、$2^{?の個数}$ 通りある
そのうち、以下の条件を満たすものの個数を $\mod{998244353}$ で求めよ
$i=1,2,...,N$ の順に、人 $P_i$ が以下の行動を取るとする
全員の行動が終了した時、全員がスプーンを取れている
$2 \le N \le 2 \times 10^5$
解法
全員がスプーンを取れるケースは、「全員が自分の左側を取った」「全員が自分の右側を取った」以外にあり得ない。
全員が左を取ることになるような $T$ の個数を考えるとする。(右の場合も同様に考えられる)
各人の行動を $P$ の順にシミュレートして、
よって、「自分の番で、右側のスプーンが取られ左側のみ残っている、$S_i=?$ であるような人数」を $k$ として、$2^k$ 通りある。
全員が右を取る場合もシミュレートして、合計が答え。
Python3
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)
C - Jumping Through Intervals
問題
$N$ 個の $(L_i,R_i)$ の組が与えられる
長さ $N$ の数列 $A=(A_1,...,A_N)$ で、以下の条件にあてはまるものを求めよ
$A_i$ は、$[L_i,R_i]$ の範囲の整数値である
その中で、隣り合う2項間の差の総和 $\displaystyle \sum_{i=1}^{N-1}|A_i - A_{i+1}|$ が最小である
その中で、辞書順最小である
$2 \le N \le 5 \times 10^5$
解法
やりたいことは分かるが、どう実装するかが難しい。
まず、無駄に値をふらふら上下させると2項間の差が増えてしまう。
$(L,R)$ の制約によって上下させる必要は生じるのだが、“最低限の上下回数”に抑えたい。
山と谷を列挙する。
ここでの山と谷とは、ざっくりイメージだが、
「山の $L_i$ と谷の $R_j$ を交互に結び、間を $R_j$ 以上 $L_i$ 以下で適切に埋めたのが、答えとなる」ような位置を指す。
i 0 1 2 3 4 5 6 7 8 ※それぞれのiに対し下がLi,上がRi
9
8 | 8
| 7 | | 7
| | 6 | 6 6 |
| | 5 | | | |
| | | 4 | 4 |
3 | 3 | 3
2 2 |
1 1
山 谷 山
6 6 6 4 4 2 2 4 4 この例の場合の答え
山と谷の間の埋め方は、2項間の差の総和に影響を与えずに辞書順最小にする必要があるので、
谷($i$)→山($j$)なら、$(R_i, L_{i+1},...,L_{j-1},L_{j})$ を、前から累積Maxをとったもの
山($i$)→谷($j$)なら、$(L_i, L_{i+1},...,L_{j-1},R_{j})$ を、後ろから累積Maxをとったもの
で埋めることになる。要は、単調増加/減少になる中で、なるべく小さい値を用いるとよい。
ただし最初と最後は、2項間の差の最小化のため、同じ値を連続させる。
山と谷の求め方
先頭から逐次見ていく中で、$(L_i,R_i)$ の範囲に共通部分があるものを、「区間」とする。
i 0 1 2 3 4 5 6 7 8 ※それぞれのiに対し下がLi,上がRi
9
8 | 8
| 7 | | 7
| | 6 | 6 6 |
| | 5 | | | |
| | | 4 | 4 |
3 | 3 | 3
2 2 |
1 1
|-------||----||----||----| 区間
[6,7] [4,5] [1,2] [4,6] 区間の共通部分の [最小, 最大]
$i$ を進めるたびに、区間の共通部分は狭まっていく。($i=0,1,2$ と進めると、[3,8]→[3,7]→[6,7] となる)
これが、ある $i$ で $(L_i,R_i)$ と共通部分がなくなったら、そこで区切り、$i$ から新たな区間を始める。
このように区間を決めると、隣り合う区間の[最小,最大]は共通部分を持たない。
よって、今の区間が、前後の区間と比べて範囲的に小さいか、大きいかが決まる。([6,7] > [4,5] など)
この時、
同じ値が含まれている場合はどこでもよい。
また、両端の2区間には必ず山 or 谷が含まれる。(唯一の隣接する区間との大小関係により決まる)
山,谷のindexを列挙し、その間を適切に埋めれば、$A$ が求まる。
Python3
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)
解法2
もっとシンプルに解ける。前から以下のように貪欲に決めていく。なるべく2項間の差を小さくしようとしている。
$Ans[i-1]$ に置いた数が、$L_i,R_i$ の範囲内にある場合、$Ans[i]$ に $Ans[i-1]$ と同じ値を置く
そうでなければ、$L_i$ と $R_i$ のうち、$Ans[i-1]$ に近い方を置く
後ろからも同様に構成すると、2つのAnsのminを取ったものが、ほぼ答えとなる。
ただし、「全てに同じ値を置けるパターン」の場合はそれが答え。
またそうで無い場合でも、先頭と末尾に対して、2項間の差を最小化するためにちょっと調整の必要がある。
Python3
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)
D - LIS on Tree 2
問題
$N$ 頂点の木が与えられる
各頂点に、$1~N$ の整数を被らずに1つずつ割り当てることを考える($P_1,P_2,...,P_N$)
$L_i$ を、以下で定義する($i=1,2,...,N$)
整数を上手く割り当てることで、全頂点のLIS長の総和 $\displaystyle \sum_{i=1}^{N}L_i$ をちょうど $K$ にすることができるか判定し、できる場合は一例を示せ
$2 \le N \le 2 \times 10^5$
$1 \le K \le 10^{11}$
解法
上限と下限
頂点1を根とした各頂点の深さを $d_i$ とする($d_1=1$)。
根から昇順に整数を割り当てることで、
全ての頂点で $L_i=数列長=d_i$ という状態になり、$\sum d_i$ が実現できる。これが上限となる。
逆に降順に割り当てると、全ての頂点で $L_i=1$ になり、$N$ が下限となる。
まずこの範囲に $K$ が無ければアウト。
ある場合は、ちょうど $K$ にできるか? どうすればできるか? を考える。
結論から言うと、範囲内であれば必ず $K$ にできる。
$K$ に調整する
昇順に割り当てた場合から $X=\sum d_i-K$ だけ、LIS長の総和を減らせればよい。
試しに、1つだけひっくり返してみると、
① ②
| |
② → ①
/\ /\
③④ ③④
| |
⑤ ⑤
(ひっくり返す前の)②の部分木に含まれる頂点のLISが、1ずつ減る。
上例の場合は、総計で4減ることになる。
つまり、総計で「ひっくり返した箇所の部分木の頂点数」だけ減るので、
この合計が $X$ になるようにひっくり返す箇所を決めれば、調整できそう。
ただ、「ひっくり返す」という考え方だと、複数箇所を考える際にちょっと考えづらい(連鎖的にひっくり返す場合など)。
より適切には、「LISを伸ばすのに使われる頂点と、使われない頂点」に分ける、と考える。
根は必ず伸ばすのに使われるとして、その他を以下のように決めると、
○ ③ ○: 伸ばすのに使われる
| | ●: 使われない
● → ②
/\ /\
○● ④①
| |
○ ⑤
○の時のみ、ちゃんと伸ばすのに使われていることがわかる。
また、●の部分木の頂点数の合計だけ、LIS長の総和は減少する。
よって、「頂点を上手く選ぶと、その部分木の頂点数の合計を $X$ にできるか?」の部分和問題となる。
ただ、$N=2 \times 10^5$、$K=10^{11}$ サイズの部分和問題は、普通では無理。
しかし今回のように「部分木の頂点数」という制約があると、
「頂点数が大きい方から、採用できるなら貪欲に採用する」ことで、必ず作れることが証明できるらしい。
証明
数学的帰納法により証明できる。
$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$ の任意の値が作れるので、貪欲にとって問題ないことも示された。
●にする頂点が決まったら、あとは昇順/降順に置いていけば、答えとなる。
Python3
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)
E - Three View Drawing
問題
$1 \times 1 \times 1$ の立方体 $N^3$ 個を $N \times N \times N$ の形に積み上げた形をイメージする
立方体の各辺は x,y,z軸に平行とし、立方体は $(0,0,0)~(N-1,N-1,N-1)$ の座標で表すとする
このうち、いくつかの立方体だけ残して、取り除く(立方体は宙に浮かせてもよい)
以下の条件を全て満たすような立方体の配置を1つ構築せよ
ちょうど $K$ 個ある
$xy$ 平面に投影しても、$yz$ 平面に投影しても、$zx$ 平面に投影しても、どの立方体も隠れない。
また、3つの投影図で全て同じ影ができる(※)
(※)より厳密には、$S=\{(x_1,y_1,z_1),...,(x_K,y_K,z_K)\}$ として、
①$S$ から、$(x_i,y_i)$ だけを取り出した集合
②$S$ から、$(y_i,z_i)$ だけを取り出した集合
③$S$ から、$(z_i,x_i)$ だけを取り出した集合
①②③が集合として一致し、かつサイズは $K$ のまま(どの2つも一致しない)
$1 \le N \le 500$
$1 \le K \le N^2$
制約の範囲内で、必ず構築できる
解法
$K$ の上限が $N^2$ となっている。2次元に投影する以上、確かにそれが自明な上限である。
制約の範囲内で必ず構築できるらしいので、$K=N^2$ を実現する方法をまず考えてみる。
$K=N^2$ の場合、投影図は $N^2$ の正方形に決まっているので、影の一致は特に気にする必要は無い。
$xy$ 平面の $N \times N$ グリッドに、z座標を表す $0~N-1$ の数を置いていくことを考える。
この時、同じ行・列に同じ数を置いたら隠れることになってしまうので、数独のように、行・列内は全て別々の数字を置く必要がある。
y
3| 0 3 2 1
2| 1 0 3 2
1| 2 1 0 3
0| 3 2 1 0
-|---------→ x
0 1 2 3
逆にそれを満たせば、ひとまず投影して隠れないようにはできるので、$K=N^2$ の場合は成立する。
$K \lt N^2$ の場合は、この $(x,y,z)$ の集合から $K$ 個採用することで構築することを考える。
ただ、適当に採用すると、影が一致しなくなってしまう。
$K=N^2$ を成立させる配置の中でも、(感覚的にではあるが)考えやすそうな配置をベースに考えたい。
冒頭の例を可視化すると($N=4$ と $N=10$ の違いはあるが、考え方は同じとして)下のようになる。
この配置は3軸に対して対称的なので、yz、zx 平面に投影してみても、xy と全く同じ配置の表になる。
z x
3| 0 3 2 1 3| 0 3 2 1
2| 1 0 3 2 2| 1 0 3 2 2つともxyと全く同じ
1| 2 1 0 3 1| 2 1 0 3
0| 3 2 1 0 0| 3 2 1 0
-|---------→ y -+---------→ z
0 1 2 3 0 1 2 3
試しに、この法則による配置をベースとして考察を進めてみる。
これでできる $(x,y,z)$ の組を、$N$ を変えて観察してみると、
① $(1,1,1)$ のような、3つとも同じ座標が0~1個
② $(0,0,3),(0,3,0),(3,0,0)$ のような、3つ中2つが同じ3つ組が $N$ グループほど
③ $(0,1,2),(1,2,0),(2,0,1)$ など、3つとも異なり、転回して同じになる3つ組がその他多数
できることが分かる。
①は、これ単独で採用することができる。どの投影図でも、同じ箇所に影ができる。
②と③は、1グループ3つセットで採用することができる。3個セットで、どの投影図でも同じ3箇所に影ができる。
また、特に②は、この代わりに $(0,0,3),(0,3,0),(3,0,0)→(0,0,0)$ のように、①相当に置き換えることができる。
これで、3つ単位でなく、1個単位でも採用できることになり、自由度が増す。
①+②は必ず $N$ 個(グループ)ある。$N \ge 2$ では $K$ を3で割った端数を必ず調整できる($N=1$ は自明)。
③→②を3個単位→②を1個単位→① の順に貪欲に使っていくと、構築できる。
ただし、
$N$ が3の倍数の時、先述の配置では①が0個になる
$K$ が $N^2$ に近く、かつ3で割って2余る場合、②の6個を捨てて代わりに2個採用する、ということになる
先述の配置を少しずらすことで、$(0,0,0)$ を作り、①を必ず1個以上にすることができる
y
5| 1 0 5 4 3 2
4| 2 1 0 5 4 3
3| 3 2 1 0 5 4
2| 4 3 2 1 0 5
1| 5 4 3 2 1 0
0| 0 5 4 3 2 1
-|------------→ x
0 1 2 3 4 5
こうすると、足りるようになる。
Python3
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))