パ研合宿 2024 「パ研杯」
解説
a1048576・ keisuke6・ joi_ganbaru・ hiikunZ・ MtSaka・ fact493・ Cyanmond・ shiomusubi496
全体講評
運営の想定難易度たち
ytqm3 の想定難易度 : A < H < D < E < G < B < C < F
MtSakaの想定難易度: A < H < D < E <B < G < F < C
shiomusubi496の想定難易度: A < H < D < E < G < F < C < B
実際の解かれ具合(全体)
A : 100 : 104 人 50<= : 104 人 E : 100 : 21 人 50<= : 26 人
B : 100 : 0 人 50<=: 7 人 F : 100 : 1 人 50<= : 2 人
C : 100 : 0 人 50<=: 1人 G : 100 : 1 人 50<= : 2 人
D : 100 : 38 人 50<=: 38 人 H : 100 : 29 人 50<= : 33 人
今年のセットについて
今年は例年に比べて部分点が多く、とっかかりやすい問題も多かったんじゃないでしょうか
問題は今年も難しく、解きごたえがあるんじゃないかと思います
オンサイト表彰
First AC, Unique AC 賞
on-site First AC(AC が出なかった場合は最高得点)
A : 100pts square1001 さん (0:46)
B : 60pts Flipper(hirayuu_At) さん (137:42)
C : 50pts square1001 さん (205:30)
D : 100pts E869120 さん (18:25)
on-site First AC(AC が出なかった場合は最高得点)
E : 100pts tatyam さん (40:54)
F : 40pts square1001 さん (139:56)
G : 49pts nahco314(【本物】shiomusubi496) (235:58)
H : 100pts hirayuu_At さん (42:28)
オンサイト高順位チーム表彰
6-10 位
10 位 : O(N A^2 R) (Iroha_3856, rurumaru) さん (299 点, 100-10-15-100-0-9-0-65)
9 位 : suminoeno7 さん (300 点, 100-1-5-100-12-1-6-75)
8 位 : チーム名何にする？(ryusei111, Unbakedbread, Tamiji) さん (320 点, 100-2-0-100-8-10-0-100)
7 位 : ポケモン(zeta7532, anemame) さん (397 点, 100-38-0-100-60-0-0-100)
6 位 : tatyam さん (429 点, 100-0-0-100-100-0-29-100)
4-5 位
5 位 : Mikoto Misaka(kaichou243) さん
(437 点, 100-37-0-100-100-0-0-100)
4 位 : nouka28 さん
(482 点,100-37-5-100-100-40-0-100)
3 位
🥉3 位🥉 : square1001 さん
(485 点, 100-10-50-100-100-40-10-75)
2 位
🥈2 位🥈 : E869120 さん
(508 点,100-59-40-100-100-9-0-100)
1 位
👑1 位👑 : Flipper(hirayuu_At) さん
(537 点, 100-60-30-100-100-40-7-100)
A 問題「An Easy Ranking Problem」解説
解説: MtSaka
問題概要
長さ N の整数列 Aが与えられる。これを降順にソートした整数列を B としたとき、B_4 - B_5 を求めよ
解法
Aを問題文の通りに降順ソートしてBを得て答えを計算しましょう。
C++では std::sortを使えます。(昇順ソートのときは std::sort(A.begin(), A.end()), 降順のときは std::sort(A.rbegin(), A.rend()) でソートできる)
余談: 設定はJOIの春季トレーニングです。(30人以下、1200点満点等)
統計情報
全体FA: square1001 0:46
オンサイトFA: square1001 0:46
ACチーム数: 104
提出チーム数: 104
H 問題「Hold a Contest」解説
原案: hiikunZ
解説: MtSaka
問題概要
N 人の住人がいてそれぞれレーティング R_i を持っている。各住人は友達の住人がいたりする。
あなたはレート制限 X を定めてから K 人に招待状を渡す。各住人は初めて招待状を受け取った時、自身のレートが X 以上であればコンテストに参加し友達全員に招待状を渡す。これを招待状が渡されなくなるまで行われる。
k=1,...., N について以下を解く
コンテストの参加者が k 人以上にするために X を最低でいくつにする必要があるか。
小課題1
N ≦ 2 の場合
k = 1 はレーティングが大きい方
k = 2 はレーティングが小さい方
K によらずこうなります
小課題2
M = 0
k ( ≦ K) 人来てもらうにはレーティングが大きい方から k 番目のレーティングを制限にすればよい
k ( > K) は不可能 (-1)
小課題3
N ≦ 10 の場合
まず、レーティング制限としてありえるのは N 人のレートのみである。
また、招待状を最初に送る K 人の選び方は C(N, K)(<2^N) 通り
全探索してあげて O(2^N N^2) とか
小課題4
R_i = 1 の場合
まず、レーティング制限は 1 である必要がある
では K 人に招待状を送って、最大で何人コンテストに参加するか？
→ 友達関係を辺とするグラフの各連結成分が大事
小課題5
ある連結成分の住人に招待状を送ると連結成分の住人全員来る
では連結成分の大きさが大きいほうから K 個選んでそれぞれの連結成分の住人1人に招待状を送るとよい
Union Find や シンプルなDFS/BFS で解くことができる。
小課題6
K = 1
レーティング制限を X としたとき:
先ほどのグラフのうち X 以上の住人同士の辺のみのグラフを考える
一人にしか招待状を送れないのでこのグラフでの大きさが最大の連結成分の人に招待状を送る。
小課題6
レーティング制限が X のときのグラフの連結成分の大きさの最大値を X を動かしながら求められないか？ → Xが大きい方から小さい方に動かすとよさそう
X を 1 減らす時: レーティング X - 1 の人と X-1 以上の人との間の辺が追加される。
ここで辺が追加された連結成分しか大きさが変わらない。
小課題6
最初辺がない状態から Union Find を使って連結成分と大きさを管理してあげて、レーティング制限が X のときに最大で何人コンテストに参加するかを求められる！
あとはここから k 人にするにはレーティング制限をいくつにする必要があるかは簡単に求められます
O(NlogN) とかになります
小課題7
K ≦ 5
さっきの連結成分の大きさを最大値だけではなく、std::multisetなどで全て管理してあげて削除/追加をしていって、レーティング制限が X の時に この大きい方から K 個取って計算すると良い
O(NK log N) とか
小課題8
K は一定であることに着目する
値を削除/追加しながら常に上位(大きい方から) K 個の総和を管理する方法はないか？
実はできる！上位 K 個を入れておく multiset とそれ以外を入れておく multiset の二つを持っておいて、適切に追加/削除を処理すればよい。
このテクニックは典型なので知っておいて損はない？！
(このパートをセグ木 / BIT で処理することも可能)
統計情報
全体FA: hirayuu_At(Flipper, 42:28)
オンサイトFA: hirayuu_At(Flipper, 42:28)
ACチーム数: 29
提出チーム数: 54
D 問題「Double Mochi」解説
原案・解説: keisuke6
問題概要
長さ N の広義単調増加数列 W に対して、Q 個のクエリが飛んでくる：
区間 [l, r] を指定するので、(W_l, W_{l+1} … W_r) をいくつかの (連続するとは限らない) 部分列に分割して、それぞれの列が倍々以上に増えていくようにしたい。最小でもいくつに分割する必要があるか？
部分点 (追加の制約)
�←ここまでで 25 点
小課題 1, 2 (N <= 16)
全探索 / bit dp で解くことができます
dp[S] := 「餅集合 S のみを使ってダブル餅を作ったときの最小個数」
状態数 2^N 通り、遷移 2^N 通りの dp をすると小課題 2 は通らない
for(int t=s; t>0; t = ((t-1) & t)) みたいにすると、s&t = t なる t を列挙できる
→ O(3^N) 時間で解を求めることができ、小課題 2 に通る
小課題 3,4 (N <= 200000) (解法 1)
解法 1 : 何かいい貪欲はないのか？
餅を左から見て追加していき、「すでにあるダブル餅の下に置く」 or 「何もないところにその餅を置く 」のどちらかをする
もし前者が選べる場合は前者をなるべく選ぶようにするとそれだけで最適
小課題 3,4 (N <= 200000) (解法 1)
例：
(2,3,4,6,8,10,16)
()
()
()
小課題 3,4 (N <= 200000) (解法 1)
例：
(3,4,6,8,10,16)
(2)
()
()
小課題 3,4 (N <= 200000) (解法 1)
例：
(4,6,8,10,16)
(2)
(3)
()
小課題 3,4 (N <= 200000) (解法 1)
例：
(6,8,10,16)
(2, 4)
(3)
()
小課題 3,4 (N <= 200000) (解法 1)
例：
(8,10,16)
(2, 4)
(3, 6)
()
小課題 3,4 (N <= 200000) (解法 1)
例：
(10,16)
(2, 4, 8)
(3, 6)
()
小課題 3,4 (N <= 200000) (解法 1)
例：
(16)
(2, 4, 8)
(3, 6)
(10)
小課題 3,4 (N <= 200000) (解法 1)
例：
()
(2, 4, 8, 16)
(3, 6)
(10) 3 個
小課題 3,4 (N <= 200000) (解法 1)
「現在一番後ろ (下) にある餅の大きさの集合」を持ちながら貪欲を回し、最終的な集合の大きさが答えになる
集合を vector で持つと N <= 2000 が通り、
集合を multiset で持ってうまいことやると N <= 200000 が通る
小課題 3,4 (N <= 200000) (解法 1)
「現在一番後ろ (下) にある餅の大きさの集合」を持ちながら貪欲を回し、最終的な集合の大きさが答えになる
集合を vector で持つと N <= 2000 が通り、
集合を multiset で持ってうまいことやると N <= 200000 が通る
Q <= 200000 への一般化は難しそう 別の解法を考える
小課題 3,4 (N <= 200000) (解法 2)
解法 2 : いい感じの評価はないか？
下界が実は上界だったり、上界が実は下界だったり
「どの 2 つも同一のダブル餅に含むことのできない餅の集合のうち、一番大きいものの大きさ」は下界になりそう（例えば、(5,6,7,8,9) とか）
→ a をいろいろ置いたときの「[a, 2a) の範囲にある (数列の) 要素の個数」として取りうる最大値は下界になる
小課題 3,4 (N <= 200000) (解法 2)
実は...
小課題 3,4 (N <= 200000) (解法 2)
実は... この下界は達成可能です
小課題 3,4 (N <= 200000) (解法 2)
実は... この下界は達成可能です
小課題 3,4 (N <= 200000) (解法 2)
実は... この下界は達成可能です
証明：
[a, 2a) に m 個の要素があり、これが最大だったとする
もしこれが条件を満たさない、
すなわち 2 × s_i > s_{i+1} なる s_i が存在したとすると、[s_i, 2 × s_i) には m+1 個以上の要素が存在することになり、
最大であることに矛盾する
小課題 3,4 (N <= 200000) (解法 2)
これを使って問題を解いてみる
Q = 1 の場合は、焼くなり煮るなり Q が一般の場合は？
小課題 5 (Q <= 200000) (解法 2)
これを使って問題を解いてみる
Q = 1 の場合は、焼くなり煮るなり Q が一般の場合は？
各要素 W_s に関して、「W_i <= 2 × W_s を満たす最大の i」を持つ最大値を取得するセグ木を用意、これによってクエリあたり log に落ちます
（正確には、区間 [l,r] の中の 2 × W_i <= W_r となる i の区間は場合分けしなきゃいけない）
統計情報
全体FA: E869120 (18:25)
オンサイトFA: E869120 (18:25)
ACチーム数: 38
提出チーム数: 70
E 問題「Excluded Children」解説
原案・解説: a1048576
改題: shiomusubi496
問題概要
根付き木が与えられる。
まず、葉の頂点に0か1を書く。
次に、葉以外の頂点に対し、その頂点に書く数を子の頂点に書かれた整数の集合のmexとする。
頂点1に書かれた整数がkとなるような葉への書き方の通り数をk = 0,1,...,N について求めよ。
小課題1：葉の数が5個以下 (4 points)
葉の頂点に書く数を全探索できそう（最大で2^5 = 32通り）
それぞれの場合に対し、葉以外の頂点に書く値を木DPで求める
葉の個数をdとしてO(N 2^d)
小課題2：P_i = 1 (2 ≦ i ≦ N) (8 points)
頂点1がN-1個の子を持ち、他の頂点は全て葉。よって、次のように問題を言い換えられる
長さN-1の配列Aがあり、各要素を0か1に定めます。
mex(A) = kとなるような要素の定め方を全てのkに対して求めてください。
小課題2：P_i = 1 (2 ≦ i ≦ N) (8 points)
まず、Aが2以上の要素を含むことはないので、mex(A) ≦ 2
・mex(A) = 0 ⇔ Aが0を含まない ⇔ 全ての要素が1
・mex(A) = 1 ⇔ Aは0を含むが、1は含まない ⇔ 全ての要素が0
・mex(A) = 2 ⇔ Aは0も1も含む
以上より、答えは1, 1, 2^(N-1)-2, 0, 0,..... (mod 998244353)
小課題3:P_i = floor(i/2) (2 ≦ i ≦ N) (8 points)
つまり、与えられる木は二分木 → 各頂点は子を高々2個しか持たない
重要な性質：mex(S) ≦ |S| （|S| は S の大きさを表す）
よって、各頂点に書かれる値は高々2
→DP[i][j]:頂点iにjが書かれる時の場合の数
計算量はO(N)
小課題4:N ≦ 100 (15 points)
ここからは一般の木について解く必要がある
普通に木DPをすると、計算量がO(N^2 2^N) かかってしまい到底間に合わない
2^Nの部分をどうにかして高速化できないか
小課題4:N ≦ 100 (15 points)
考察方針によっては小課題5まで一気に解けるかもしれないが、ここでは小課題3にて用いた性質を使う
重要な性質：mex(S) ≦ |S| （|S| は S の大きさを表す）
小課題4:N ≦ 100 (15 points)
mex(S) ≧ k ⇔ Sが0,1,...,k-1を全て含む
これと先ほどの性質を組み合わせると、
ある頂点にkが書かれる時、その子の頂点に0,1,..,k-1が書かれている必要がある
小課題4:N ≦ 100 (15 points)
mex(S) ≧ k ⇔ Sが0,1,...,k-1を全て含む
これと先ほどの性質を組み合わせると、
ある頂点にkが書かれる時、その子の頂点は少なくとも0,0,2,3,..,k-1個の子を持つ必要がある
小課題4:N ≦ 100 (15 points)
mex(S) ≧ k ⇔ Sが0,1,...,k-1を全て含む
これと先ほどの性質を組み合わせると、
ある頂点にkが書かれる時、その頂点を根とした部分木のサイズは最小で1+(0+1)+(0+1)+(2+1)+...+(k-1+1) = (1+k)*k/2
小課題4:N ≦ 100 (15 points)
よって、頂点に書かれ得る値 k の最大値はおよそ√2N
この制約においては k ≦ 13 となる
最初に話した木DPがO(Nk 2^k) ≒ O(N√N 2^√2N)で解ける
小課題5:N ≦ 5000 (25 points)
更に書かれる値の候補を減らせないか
f(k) = 根にkが書かれるような木のサイズの最小値
を考える
小課題5:N ≦ 5000 (25 points)
f(0),f(1) = 1
f(2) = 1+f(0)+f(1) = 3
f(3) = 1+f(0)+f(1)+f(2) = 6
f(4) = 1+f(0)+f(1)+f(2)+f(3) = 12
同様に計算すると、f(5) = 24, f(6) = 48, f(7) = 96...
小課題5:N ≦ 5000 (25 points)
kが1増えるごとにf(k)の値は2倍になっている！
これを用いると、kの最大値はおよそlogN
この制約においては k ≦ 12 となる
後は小課題4と同様にDPをするとO(Nk 2^k) ≒ O(N^2 logN)
小課題6:N <= 200000 (40 points)
f(k) ≦ N の時、ある形の木において頂点1にkを書くことは可能であり、これ以上kの最大値を減らすことはできない
別の方針で計算量を改善できないか
小課題6:N <= 200000 (40 points)
例えば、dp2[x] = 頂点xに書かれ得る値の最大値
として、頂点xについてDP[x]を求める時は子yをdp2[y]の小さい順にソートしてから考えると、全ての子についての遷移の時に毎回2^k回 (N = 200000のときk = 18) の遷移をしなくても良くなる（子yについて考えるときは2^(dp2[y]+1)回の遷移で十分）
小課題6:N <= 200000 (40 points)
実は、これだけで計算量が大きく改善されている
各kについて、dp2[x] = kとなるようなxの個数が十分小さい値に収まることを証明する。
小課題6:N <= 200000 (40 points)
右の図より、dp2[x] = kとなるようなxを2個作るために必要な頂点数は、右の図から下のように祖先と子孫の関係にある方が少ない。よって、dp2[x] = kとなるようなxの個数を最大化する時、祖先から子孫へ1つのパスを成すようにして配置するのが最適。
小課題6:N <= 200000 (40 points)
この時、dp2[x] = kとなるようなxをt個作るために必要な頂点数は
(f(0)+f(1)+f(2)+...+f(k-2))*t+f(k-1) = f(k-1)*(t+1)
よって、これは最大でfloor(N/f(k-1))-1個しか作ることができない
小課題6:N <= 200000 (40 points)
以上より、dp2[x] = kとなるx1つにつき計算量がO(2^(k+1))かかることを考えると、全体の計算量は大体
(N/f(1)-N/f(0))*2^1+(N/f(2)-N/f(1))*2^2+...
= N/f(0)*2^1+N/f(1)*2^2+N/f(2)*2^3+…
≒ O(NlogN)
よって、先程の木DPを全体でO(NlogN)で動かすことができて、十分高速。
統計情報
全体FA: toam(15:26)
オンサイトFA: tatyam(40:54)
ACチーム数:21
提出チーム数:52
B 問題「Biscuit and Ants」解説
原案: keisuke6
改題: shiomusubi496, turtle_ytqm3
問題概要
N 頂点の木のいくつかを選んでビスケットを乗せると、自身に直接隣接する頂点の K 個以上にビスケットがある頂点にもビスケットが運ばれてくる（これは連鎖的に行われる）
最初の置き方は 2^N-1 通りあるが、それぞれについての「最終的にビスケットが存在する頂点の個数」を P で割った余りを求めたい
部分点 (追加の制約)
����←大きめ部分点��←大きめ部分点
小課題 1 (K = 1)
K = 1 なので、1 箇所にビスケットが置かれていたら全ての頂点にビスケットが運ばれる (与えられるグラフは連結)
解法コード (お借りしました)：
たくさんの人に�解いていただきました
小課題 3 (N <= 15)
ビスケットの置き方は 2^N-1 通り → 全部試して足し合わせる
巣 s = 1,2 … N の順で見て、「巣 s の周りに K 個以上ビスケットがあれば s にもビスケットを置く」という操作を N 回やればよい
O(2^N N^2) 時間で答えを求めることができる
小課題 4 (パスグラフ)
主客転倒をして考えてみる：「ある巣 s に最終的にビスケットが存在するようになる最初の置き方の通り数」を s=1,2 … N について足し合わせてもよい
巣 s に最終的にビスケットが置かれているような条件は以下のいずれかを満たすとき：
小課題 4 (パスグラフ)
あとは算数をしよう：
K = 1 のときはさっき書いた通り
K > 1 のときは、2^N + 5 * 2^(N-3) * (N-2)
この部分点で主客転倒を考えたので、それを使い小課題 5 を解く→
小課題 5 (N <= 2000, K <= 5)
次のような問題を考えてみる (prob2 とする)
「与えられた木を根が巣 1 である根付き木として、p[i] -> i への辺が貼られた有向木として解釈する。ある巣 s について、自身の子である頂点のうち K 個以上にビスケットが存在する場合、巣 s にもビスケットを～(ry」
この問題は割と自然な木 dp で解ける
小課題 4 (N <= 2000, K <= 5)
さっき使った主客転倒：巣 s = 1,2 … N それぞれについて、s にビスケットが存在するために必要なビスケットの個数を数え上げたい
prob2 では、ある頂点での最終的なビスケットの有無は、その頂点の部分木の巣たちへのビスケットの置き方のみによって決まる
小課題 4 (N <= 2000, K <= 5)
dp[i] := {巣 i の部分木へのビスケットの置き方であって、最終的に巣 i にビスケットが存在するようになるものの通り数}
遷移はそこまで難しくない（逆に、巣 i に存在しないようなビスケットの置き方の通り数も数える dp も用意すると便利かも）
この dp の計算量は O(NK) 時間
小課題 4 (N <= 2000, K <= 5)
ところで：今考えてたのは prob2 でした
同じ dp を無向木 (元の問題) に適用しようとするとどうなるか？
小課題 4 (N <= 2000, K <= 5)
例) N=8 , K = 2
小課題 4 (N <= 2000, K <= 5)
例) N=8 , K = 2
巣 1 のアリが巣 2,3 から運び出す
小課題 4 (N <= 2000, K <= 5)
例) N=8 , K = 2
巣 1 のアリが巣 2,3 から運び出す
巣 6 のアリが巣 7,8 から運び出す
小課題 4 (N <= 2000, K <= 5)
例) N=8 , K = 2
巣 1 のアリが巣 2,3 から運び出す
巣 6 のアリが巣 7,8 から運び出す
巣 0 のアリが巣 1,6 から運び出す
小課題 4 (N <= 2000, K <= 5)
例) N=8 , K = 2
巣 1 のアリが巣 2,3 から運び出す
巣 6 のアリが巣 7,8 から運び出す
巣 0 のアリが巣 1,6 から運び出す
巣 4 のアリが巣 0,5 から運び出す
小課題 4 (N <= 2000, K <= 5)
例) N=8 , K = 2
巣 1 のアリが巣 2,3 から運び出す
巣 6 のアリが巣 7,8 から運び出す
巣 0 のアリが巣 1,6 から運び出す
↑？
巣 4 のアリが巣 0,5 から運び出す
小課題 4 (N <= 2000, K <= 5)
親である巣からビスケットを運び出してしまう可能性があるため、正しく数えることができない...
小課題 4 (N <= 2000, K <= 5)
親である巣からビスケットを運び出してしまう可能性があるため、正しく数えることができない...
本当に全部の頂点で正しく数えることができないのか？
小課題 4 (N <= 2000, K <= 5)
親である巣からビスケットを運び出してしまう可能性があるため、正しく数えることができない...
本当に全部の頂点で正しく数えることができないのか？
一部の頂点では正しい答えを出せていたりしないか？
小課題 4 (N <= 2000, K <= 5)
親である巣からビスケットを運び出してしまう可能性があるため、正しく数えることができない...
本当に全部の頂点で正しく数えることができないのか？
一部の頂点では正しい答えを出せていたりしないか？
例えば、親が存在しない巣であるところの、根とか...
小課題 4 (N <= 2000, K <= 5)
実は：先ほどの木 dp で根の頂点における主客転倒の答えは正しく求めることができています：
理由：親となる巣が存在しないから ( + 親からビスケットを運び出すことによる変化は、根の状態変化に関係がないため)
よって、O(NK) 時間の木 dp を、根を 1,2 … N にしてそれぞれ回すことで、正しい解を求めることができる。計算量は O(N^2 K) 時間
小課題 5 (N <= 10^6, K <= 5)
根を 1 つずつ動かすのは無駄
根をいろんな頂点に動かして、それぞれに対して答えを求める高速なアルゴリズムと言えば.........
小課題 5 (N <= 10^6, K <= 5)
根を 1 つずつ動かすのは無駄
根をいろんな頂点に動かして、それぞれに対して答えを求める高速なアルゴリズムと言えば.........
全方位木 dp
小課題 5 (N <= 10^6, K <= 5)
先ほどの木 dp を全方位化すると小課題 5 が通ります
計算量は O(NK) 時間 ここまでで 60 点
小課題 6 (N <= 10^5)
小課題 6 (N <= 10^5)
小課題 6 (N <= 10^5)
小課題 2 (K = N-1)
ここで：小課題 2 を考えます
K = N-1 では、変化しうる巣が高々 1 つ
→よって、その頂点のみ考えて主客転倒し、他は変化しないから 2^{N-1} を答えとしてよい
小課題 2 (K = N-1)
ここで：小課題 2 を考えます
K = N-1 では、変化しうる巣が高々 1 つ
→よって、その頂点のみ考えて主客転倒し、他は変化しないから 2^{N-1} を答えとしてよい
見るべき頂点が少ないなので、楽に計算できます
小課題 6 (N <= 10^5)
同じ議論をします：
小課題 6 (N <= 10^5)
同じ議論をします：
後から変化しうる巣の個数は（その巣の次数が K 以上で無ければならないことから）、高々 2N/K 個しかありません
小課題 6 (N <= 10^5)
出典：
小課題 6 (N <= 10^5)
全方位木 dp の計算量が、頂点の個数を n として O(nK) であったため、n <= 2N/K とした上での計算量は O(N) 時間になります
よって小課題 6 を解くことが出来ました + 小課題 7 も定数倍が良ければ通ります
小課題 6 (N <= 10^5)
ちなみに：writer 解も tester 解も 1000ms を超えた実行時間です
もしかしたら python は通らないかも
統計情報
全体FA: - (最高点: 84 shobonvip)
オンサイトFA: -
ACチーム数: 0
提出チーム数: 48
F 問題「French Restaurant」解説
原案・解説: shiomusubi496
証明協力: MtSaka
問題概要
1, 2, …, K からなる整数列 A に対して、
問題概要
小課題
小課題1: K=1
明らかに、 R-L+1 が答え
この部分点は回収しましたか？�JOI ではこの 1 点が勝負を分けるかもしれません
小課題2: N,Q<=2000
(1, 2, …, K) がいくつ取れるか、 (1, 2, …, K-1) がいくつ取れるか、
…、 (1) がいくつ取れるか、を持ちながら左から貪欲できる
更新も言われた通りに書けば、時間計算量 O(NQK)
小課題3: K=2
ここからが本質
ここからは R に 1 を足すなどして半開区間 [L, R) として扱う
小課題3: K=2
これは二部マッチングの問題
二部マッチングと言えば Hall の結婚定理
JOI の過去問だと Ants and Sugar など
小課題3: K=2
ある index M (L <= M <= R) を取る
([L, M) にある 1 の個数) + ([M, R) にある 2 の個数) は上界になっている
逆に、この最小値は必ず取ることができる (Hall の定理で示せるらしい)
小課題3: K=2
あとは累積和を管理すれば解けそう
頑張ると遅延セグ木に乗りそう
30 点おめでとうございます
小課題4,5,6
やることが同じです
まとめて解説
小課題4,5,6
K=2 を拡張すれば解けそう
広義単調増加な m1, m2, …, m(K-1) を用意して、
([L, m1) の 1 の個数 ) + ([m1, m2) の 2 の個数) + … + ([m(K-1), R) の K の個数)�の最小値が答えなのでは？
証明しよう
小課題4,5,6
フローに帰着させます
(L, 0), (L, 1) , .. , (L, K), (L + 1, 0) , ... , (R, 0),...,(R, K) に対応する (R-L+1)K 個の頂点を用意する
(i, j) → (i+1, j) に流量 inf の辺、(i, D_i -1) → (i, D_i) に流量 1の辺を貼る
このとき、[L, R] の答えは (L, 0) から (R, K) への最大流と等しい
小課題4,5,6
(L,0) と (R,K) の最小カットを取った時各 i について (i, j) が (L, 0) 側か (R, K) 側かは単調で、境界も単調増加である
この性質を満たすようなもののうち最小コストのカットを考えればよい
このカットは先ほどの広義単調増加な m1, m2, …, m(K-1) を用意して、
([L, m1) の 1 の個数 ) + ([m1, m2) の 2 の個数) + … + ([m(K-1), R) の K の個数)
と言い換えることができる。
小課題4,5,6
実際に求める方法
遅延セグ木にA_{i,j} = その区間を区間に分割して i, i + 1, i + 2, …, j に順に割り振った時それぞれに含まれる i の個数 , i + 1 の個数, … , j の個数 の合計の最小値 (i > j については 円環のようにして考える ) を持つ
各ノードに K^2 個の値を持つ
小課題4,5,6
実際に求める方法
マージ: O(K^4) (定数倍軽め) あるいは O(K^3)
区間代入: A_{v, v}= (区間の大きさ) とすればよい (それ以外は 0) O(K^2)
区間シフト: 更新前を A として、A’_{i + 1 , j + 1} = A_{i, j} にする O(K^2)
小課題4,5,6
実際に求める方法
そのまま遅延セグ木に乗せることができる！
計算量: O(K^3 Nlog N) あるいは O(K^4 NlogN) で満点をとることができます
統計情報
全体FA: yuto1115 (228:36)
オンサイトFA: -
ACチーム数: 1
提出チーム数: 32
Greedy Robot
Editorial : hiikunZ
問題概要
N頂点M辺の連結な無向グラフがあります
全ての辺はK色のうち1色で塗られてます
同じ頂点に同じ色の辺は2つ以上存在しません
ジャッジに頂点vと1からKまでの順列 P を投げて次のことを聞けます
・頂点 v に隣接する辺のうち、色が P に最初に出てくるものの v でない方の端点は?
10000 回以内の質問でグラフの形と辺の色を特定してください
小課題
小課題1 (N = 3, M = 2, K = 2)
小課題1 (N = 3, M = 2, K = 2)
こういう形しかありえない
?
?
?
色1
色2
小課題1 (N = 3, M = 2, K = 2)
端にいる場合
?
?
?
色1
色2
小課題1 (N = 3, M = 2, K = 2)
端にいる場合
?
?
?
色1
色2
1
2
小課題1 (N = 3, M = 2, K = 2)
端にいる場合
逆にしても一緒
?
?
?
色1
色2
2
1
小課題1 (N = 3, M = 2, K = 2)
中央にいる場合
?
?
?
色1
色2
1
2
小課題1 (N = 3, M = 2, K = 2)
中央にいる場合
逆にすると行き先が変わる
?
?
?
色1
色2
2
1
小課題1 (N = 3, M = 2, K = 2)
中央にいる場合
逆にすると行き先が変わる
?
?
?
色1
色2
2
1
真ん中の頂点の番号がわかる
小課題1 (N = 3, M = 2, K = 2)
あとは普通に質問する
?
X
?
色1
色2
小課題1 (N = 3, M = 2, K = 2)
あとは普通に質問する
Y
X
?
色1
色2
1
2
小課題1 (N = 3, M = 2, K = 2)
あとは普通に質問する
Y
X
Z
色1
色2
2
1
小課題1 (N = 3, M = 2, K = 2)
あとは普通に質問する
Y
X
Z
色1
色2
2
1
3点
小課題2 (N = 3, M = 2)
小課題2 (N = 3, M = 2)
こういう形しかありえない
?
?
?
色?
色?
小課題2 (N = 3, M = 2)
端にいる場合
?
?
?
色?
色?
小課題2 (N = 3, M = 2)
端にいる場合
?
?
?
色?
色?
2
4
1
3
5
小課題2 (N = 3, M = 2)
端にいる場合
逆にしても一緒
?
?
?
色?
2
色?
4
5
1
3
小課題2 (N = 3, M = 2)
中央にいる場合
?
?
?
色?
色?
2
4
1
3
5
小課題2 (N = 3, M = 2)
中央にいる場合���逆にすると行き先が変わる
?
?
?
色?
色?
2
4
5
1
3
小課題2 (N = 3, M = 2)
中央にいる場合���逆にすると行き先が変わる
?
?
?
色?
色?
2
4
5
1
3
真ん中の頂点の番号がわかる
小課題2 (N = 3, M = 2)
あとは…?
?
?
?
色?
色?
2
4
1
3
5
小課題2 (N = 3, M = 2)
あとは…?
?
?
?
色?
色?
2
4
1
5
3
小課題2 (N = 3, M = 2)
あとは…?
?
?
?
色?
色?
1
2
4
5
3
小課題2 (N = 3, M = 2)
あとは…?
?
?
?
色?
色?
3
1
2
4
5
小課題2 (N = 3, M = 2)
あとは…?
?
?
?
色?
色?
1
3
4
2
5
小課題2 (N = 3, M = 2)
切り替わった時
?
?
?
色?
色?
2
4
1
5
3
小課題2 (N = 3, M = 2)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
小課題2 (N = 3, M = 2)
切り替わった時
?
?
?
色?
色?
2
4
1
5
3
小課題2 (N = 3, M = 2)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
小課題2 (N = 3, M = 2)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
後ろに追いやられると
行き先が変わる
小課題2 (N = 3, M = 2)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
後ろに追いやられると
行き先が変わる
クエリは K + 2N 回
小課題2 (N = 3, M = 2)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
後ろに追いやられると
行き先が変わる
クエリは K + 2N 回
合計6点
小課題3 (K = 2)
小課題3 (K = 2)
K = 2 より次数が高々 2
小課題3 (K = 2)
K = 2 より次数が高々 2
?
?
?
色1
色2
?
色1
小課題3 (K = 2)
K = 2 より次数が高々 2
?
?
?
色1
色2
?
色1
色2
小課題3 (K = 2)
小課題 1 でやったように
・端かどうか
・(端で無い場合) 色 1 / 2 の辺の先
がわかる
1
2
1
2
小課題3 (K = 2)
小課題 1 でやったように
・端かどうか
・(端で無い場合) 色 1 / 2 の辺の先
がわかる
1
2
1
2
3≦Nより両方が端になる辺はないのでOK
小課題3 (K = 2)
小課題 1 でやったように
・端かどうか
・(端で無い場合) 色 1 / 2 の辺の先
がわかる
1
2
1
2
3≦Nより両方が端になる辺はないのでOK
クエリは 2N 回
小課題3 (K = 2)
小課題 1 でやったように
・端かどうか
・(端で無い場合) 色 1 / 2 の辺の先
がわかる
1
2
1
2
3≦Nより両方が端になる辺はないのでOK
クエリは 2N 回
合計10点
小課題4 (追加の制約無し)
ところで
今頂点 X を考えていて、�とりあえず色 C の辺で 頂点 Y に行けることは既知とする
?
X
?
色?
色?
Y
色C
典型: 二分探索
?
X
?
色?
色?
Y
色C
2
4
1
C
3
典型: 二分探索
?
X
?
色?
色?
Y
色C
2
4
1
C
3
典型: 二分探索
?
X
?
色?
色?
Y
色C
2
4
1
C
3
典型: 二分探索
?
X
?
色?
色?
Y
色C
2
4
1
C
3
典型: 二分探索
P
X
?
色?
色?
Y
色C
2
4
1
C
3
P とする
典型: 二分探索
P
X
?
色?
色?
Y
色C
2
4
1
C
3
この色は C より前
典型: 二分探索
P
X
?
色?
色?
Y
色C
2
4
1
C
3
典型: 二分探索
P
X
?
色?
色?
Y
色C
C
2
4
1
3
この色は C より後
まとめると
P
X
?
色?
色?
Y
色C
この色は C より前
2
4
1
C
3
まとめると
P
X
?
色?
色?
Y
色C
この色は C より後
2
4
1
C
3
まとめると
じゃあ色 の辺
で P に行けそう
P
X
?
色2
色?
Y
色C
この色は C より後
2
まとめると
P
じゃあ色 の辺
で P に行けそう
2
X
?
色2
色?
Y
色C
この色は C より後
辺あたり log2500 ≒ 9回
まとめると
P
X
?
色2
色?
Y
色C
じゃあ色 の辺
で P に行けそう
2
この色は C より後
辺あたり log2500 ≒ 9回
色の番号が小さい方から特定可能
Q. もう全ての辺が判明しているかの判定は?
?
X
?
色?
色?
Y
色C
Q. もう全ての辺が判明しているかの判定は?
最初に聞いておく
?
X
?
色?
色?
Y
色C
3
C
2
4
1
Q. もう全ての辺が判明しているかの判定は?
最初に聞いておく
?
X
?
色?
色?
Y
色C
3
C
2
4
1
Q. もう全ての辺が判明しているかの判定は?
最初に聞いておく
?
X
?
色?
色?
Y
色C
3
C
2
4
1
色最大の辺の行き先が分かる
Q. もう全ての辺が判明しているかの判定は?
色最大の辺の行き先が分かる
色の番号が小さい方から
特定可能
Q. もう全ての辺が判明しているかの判定は?
色最大の辺の行き先が分かる
色の番号が小さい方から
特定可能
一致したら終わり
ところで
今頂点 X を考えていて、�とりあえず色 C の辺で 頂点 Y に行けることは既知とする
?
X
?
色?
色?
Y
色C
ところで
今頂点 X を考えていて、�とりあえず色 C の辺で 頂点 Y に行けることは既知とする
?
X
?
色?
色?
Y
色C
最初は?
X から 色 C の辺で Y に行けるような X, Y, C の特定
葉にロボットを置くと困る
?
X から 色 C の辺で Y に行けるような X, Y, C の特定
葉かの判定は 2 回でできる
?
2
4
1
3
5
2
4
5
1
3
X から 色 C の辺で Y に行けるような X, Y, C の特定
葉かの判定は 2 回でできる
?
2
4
1
3
5
2
4
5
1
3
葉だったらたどれば葉じゃなくなる
小課題2 (N = 3, M = 2) (再掲)
葉じゃなければ
?
?
?
色?
色?
2
4
1
3
5
小課題2 (N = 3, M = 2) (再掲)
葉じゃなければ
?
?
?
色?
色?
2
4
1
5
3
小課題2 (N = 3, M = 2) (再掲)
葉じゃなければ
?
?
?
色?
色?
1
2
4
5
3
小課題2 (N = 3, M = 2) (再掲)
葉じゃなければ
?
?
?
色?
色?
3
1
2
4
5
小課題2 (N = 3, M = 2) (再掲)
葉じゃなければ
?
?
?
色?
色?
1
3
4
2
5
小課題2 (N = 3, M = 2) (再掲)
切り替わった時
?
?
?
色?
色?
2
4
1
5
3
小課題2 (N = 3, M = 2) (再掲)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
小課題2 (N = 3, M = 2) (再掲)
切り替わった時
?
?
?
色?
色?
2
4
1
5
3
小課題2 (N = 3, M = 2) (再掲)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
小課題2 (N = 3, M = 2) (再掲)
切り替わった時
?
?
?
色?
色?
1
2
4
5
3
後ろに追いやられると
行き先が変わる
まとめ
まとめ
葉の回避: 2回
まとめ
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回
まとめ
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回
葉を回避しながら辺の色を二分探索: N + (M-1) × 9 = 4991 回
まとめ
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回
葉を回避しながら辺の色を二分探索: N + (M-1) × 9 = 4991 回
合計 5500 回ぐらい
合計 36 点
ところで
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回
葉を回避しながら辺の色を二分探索: N + (M-1) × 9 = 4991 回
ところで
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回
葉を回避しながら辺の色を二分探索: N + (M-1) × 9 = 4991 回
ところで
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回
葉を回避しながら辺の色を二分探索: N + (M-1) × 9 = 4991 回
減らせそう
X から 色 C の辺で Y に行けるような X, Y, C の特定
にぶたんしたい
X から 色 C の辺で Y に行けるような X, Y, C の特定
葉ではないとする
?
?
?
色?
色?
X から 色 C の辺で Y に行けるような X, Y, C の特定
最初に聞く
?
?
?
色?
色?
2
4
1
3
5
X から 色 C の辺で Y に行けるような X, Y, C の特定
最初に聞く
?
?
?
色?
色?
2
4
1
3
5
色最小の辺の行き先が分かる
X から 色 C の辺で Y に行けるような X, Y, C の特定
X から 色 C の辺で Y に行けるような X, Y, C の特定
2 番目の頂点を二分探索で求めればええんちゃう?
X から 色 C の辺で Y に行けるような X, Y, C の特定
2 番目の頂点を二分探索で求めればええんちゃう?
天才
X から 色 C の辺で Y に行けるような X, Y, C の特定
最初に聞く
?
?
?
色?
2
4
1
3
5
色最小の辺の行き先
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
2
4
1
3
5
色最小の辺の行き先
ひっくり返す
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
2
4
3
1
5
色最小の辺の行き先
ひっくり返した
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
2
4
3
1
5
色最小の辺の行き先
ひっくり返した
行き先が同じ
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
2
4
3
1
5
色最小の辺の行き先
この中に 2 番目はない
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
2
4
1
3
5
色最小の辺の行き先
ひっくり返す
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
3
2
4
1
5
色最小の辺の行き先
ひっくり返した
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
3
2
4
1
5
色最小の辺の行き先
ひっくり返した
行き先が違う
X から 色 C の辺で Y に行けるような X, Y, C の特定
天才
?
?
?
色?
3
2
4
1
5
色最小の辺の行き先
この中に 2 番目がある
X から 色 C の辺で Y に行けるような X, Y, C の特定
(再掲)
?
?
?
色?
2
4
3
1
5
色最小の辺の行き先
この中に 2 番目はない
X から 色 C の辺で Y に行けるような X, Y, C の特定
?
?
?
色?
色4
4
色 だ! 行き先は?
X から 色 C の辺で Y に行けるような X, Y, C の特定
さっき聞いた
?
?
?
色?
3
2
4
1
5
色最小の辺の行き先
この中に 2 番目がある
ということで
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回 → 9 回
葉を回避しながら辺の色を二分探索: N + (M-1) × 9 = 4991 回
ということで
葉の回避: 2回
X から 色 C の辺で Y に行けるような X, Y, C の特定
: 500回 → 9 回
葉を回避しながら辺の色を二分探索: N + (M-1) × 9 = 4991 回
合計 5002 回ぐらい
合計 94 点
ウィニングラン
二分探索で 500 択 を探す
→ たまに 9 回じゃなくて 8 回でできる
ウィニングラン
二分探索で 500 択 を探す
→ たまに 9 回じゃなくて 8 回でできる
→ いい感じに乱択すれば 5000 回を切れる! (はず)
ウィニングラン
二分探索で 500 択 を探す
→ たまに 9 回じゃなくて 8 回でできる
→ いい感じに乱択すれば 5000 回を切れる! (はず)
ちなみに考察を頑張ると乱択なしで 5000 回を達成可能 (想定解)
乱択なしで 5001 回
まず 5002 回解法から 1 回削る
乱択なしで 5001 回
まず 5002 回解法から 1 回削る
・探索をしていった最後の頂点で質問をする必要はない!
乱択なしで 5001 回
まず 5002 回解法から 1 回削る
・探索をしていった最後の頂点で質問をする必要はない!
理由: 全て辺が全て特定済みなのでその時点で解答して OK
乱択なしで 5000 回
最初が葉でない場合�
最初が葉の場合�
乱択なしで 5000 回
最初が葉でない場合� → 葉かどうかのための質問の答えを使い回せる
最初が葉の場合�
乱択なしで 5000 回
最初が葉でない場合� → 葉かどうかのための質問の答えを使い回せる
最初が葉の場合� → 最初の頂点についてこれ以上質問しなくていい� + 探索済みにしてよい
乱択なしで 5000 回
最初が葉でない場合� → 葉かどうかのための質問の答えを使い回せる
最初が葉の場合� → 最初の頂点についてこれ以上質問しなくていい� + 探索済みにしてよい
どちらのケースでも 5000 回を達成可能
乱択なしで 5000 回
最初が葉でない場合� → 葉かどうかのための質問の答えを使い回せる
最初が葉の場合� → 最初の頂点についてこれ以上質問しなくていい� + 探索済みにしてよい
どちらのケースでも 5000 回を達成可能
満点
実装
実装をミスるとクエリが 500, 3, 2, 1 回とか無駄に増える
→ 満点を取りたい場合は頑張ろう
統計情報
全体FA: Nachia (164:35)
オンサイトFA: -
ACチーム数: 1
提出チーム数: 27
C 問題「Can Make Palindrome」解説
原案・解説: shiomusubi496
問題概要
木があり、各頂点 v に整数 C[v] が定まっている
f(u, v, i) を u-v パス上で i から最も近い頂点とする
i 日目に C[f(U_i, V_i, L_i)], C[f(U_i, V_i, L_i + 1)], …, C[f(U_i, V_i, R_i)] を得る
S_i, S_i+1, …, T_i 日目に得る整数を並び替えて回文にできるか？
小課題
たくさんある
小課題1: N, M <= 300, Q=1, C<=2
回文は 1, 2 が両方とも奇数回現れるときだけ不可能
それが分かっていればおそらく何をやっても通る
小課題2: N, M <= 2000, Q=1, C<=2
少し難しい
各日の各 f(U_i, V_i, j) を高速に求めれば AC が得られる
U_i - V_i パス上の頂点を列挙して、 j ごとに二分探索などが楽か？
小課題3: N, M <= 2000, C<=2
これは難しくない
M 日ごとに求めた 1, 2 の個数を累積和を取るなど
毎クエリ [S, T] を全部見ても割と間に合う
小課題4: A_i=i, B_i=i+1, C<=2
直線グラフなので、 u-v パスが u, u+1, …, v ですね
j=L_i, L_i+1, …, R_i について、 f(U_i, V_i, j) = clamp(j, U_i, V_i)
[L_i, R_i] と [U_i, V_i] の二つの区間の位置関係で場合分ける
小課題4: A_i=i, B_i=i+1, C<=2
例えば [L_i, R_i] が [U_i, V_i] を内包するなら、
累積和などを取っておくとすぐに取れる
小課題5: A_{i+1}=B_i, C<=2
直線グラフだけど、頂点番号順ではない�4 みたいな解法は通用しない…
頂点番号が小さい順に走査していく�最初全ての頂点を off にして、順に on にしながらクエリ処理
楽にするために：�L_i, L_i+1, …, R_i を求める代わりに 1, 2, …, L_i-1 と 1, 2, …, R_i を求めるテク
小課題5: A_{i+1}=B_i, C<=2
頂点をパスの順に並べ、区間和セグ木 seg1, seg2 を持つ
さっきは [L_i, R_i] それぞれに clamp を取ったが、�今回は seg0, seg1 で 1 になっているところに clamp を取る
さっきとほぼ同じで、適当な区間和のクエリに落ちる
小課題6: A_{i+1}=B_i
今までずっとあった C の制約が消えてしまった！
C の値それぞれについて求めることはもうできない…
まとめて扱えないか？
小課題6: A_{i+1}=B_i
ところで：C の値それぞれの偶奇だけ分かれば良いです
やりたいことは、個数 mod 2 を同一視した上で、�S = ∅ であるかや S = {1} や S = {2} であるかの判定
集合の一致判定と言えば有名なものがありますね
小課題6: A_{i+1}=B_i
ところで：C の値それぞれの偶奇だけ分かれば良いです
やりたいことは、個数 mod 2 を同一視した上で、�S = ∅ であるかや S = {1} や S = {2} であるかの判定
集合の一致判定と言えば有名なものがありますね
Zobrist Hash
小課題6: A_{i+1}=B_i
1, 2, …, N にそれぞれ乱数を割り当てて、�C[v] に割り当てられた乱数で C[v] を置き換える
さっきまで 1, 2 ごとに和を取っていたが、まとめて xor を取る
xor が 0 になる、または C[1], C[2], …, C[N] のいずれかに等しいと Yes�std::set とかを持ったり std::binary_search を使うと良い
小課題6: A_{i+1}=B_i
注意： (N+1)Q 回の判定が起きるので、 32bit だと割と衝突する
64bit を使いましょう
小課題7,8: 追加制約なし
Zobrist Hash ができてなくても 7 は取れるが、まとめて解説
小課題7,8: 追加制約なし
パスじゃない
一般の木で同じことをしなければならない
小課題7,8: 追加制約なし
パスじゃない
一般の木で同じことをしなければならない
一般の木をパスに分解してしまおう！
小課題7,8: 追加制約なし
パスじゃない
一般の木で同じことをしなければならない
一般の木をパスに分解してしまおう！
Heavy Light Decomposition
小課題7,8: 追加制約なし
heavy edge を優先的に選ぶ dfs-order 順に区間XORセグ木を持つ
ここで、セグ木の v に持たせるのは、
このセグ木により、 heavy path を上昇を一気に処理できるようになる
小課題7,8: 追加制約なし
light edge を上がるために、単に on の個数を持つセグ木もあると楽
頂点を on にするのは、 heavy path の 1 点更新になり上手くいく
小課題7,8: 追加制約なし
実装を楽にするテクニック
小課題7,8: 追加制約なし
実装を楽にするテクニック
さっき [L, R) の代わりに�[0, L), [0, R) を考えた
同じように工夫すると�0 - U パスと 0 - V パスにできる
統計情報
全体FA: -
オンサイトFA: -
ACチーム数: 0
提出チーム数: 15