[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 168 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
219(3): 2024/03/28(木)20:40 AAS
>>198
∑LIS(1,v)=K になるように、条件を満たしながら頂点に値を振る方法
まずは上界、つまり子の値が必ず (自分の値)+1 になっている場合からスタート
頂点 1 に注目する
1 の子 q について、 qの値が 1 の値)+1 になっているなら、qの部分木が含む頂点すべての値をごっそり 1 減らしても（条件）を満たす
これで（qの部分木サイズ）だけ ∑LIS が減らせる
（qの部分木サイズ）-1 だけ減らしたいときはどうするか？
q 自体は減らさず、qの全部の部分木に対して値を減らせばいい
こんな感じに思うと、子の部分木サイズが（残り減らすべき∑LIS）以下だったら減らす、という貪欲でやっていったら0≦x≦(q の部分木サイズ）の任意のxだけ必ず減らせる
225: 2024/03/28(木)20:51 AAS
そんなことよりARC-Dの解説昨日くらいから求められてたのに、>>219でようやく解説されたのがヤバい
デ・アの話を増やさないと
僕ですか？
ABまでしか解けなかったので説明無理ですｗ
226: 2024/03/28(木)20:51 AAS
>>219
まあコンテスト中は試行錯誤したから
「値をswapしていけばLISを1ずつ減らせるのでは」で失敗
その後頂点にLIS(1,v)を振って挙動を試す（上界下界はここでわかった）
その後構築方法より先に ∑LIS を K にする方法を思いつく（swapで構築はかなりやりづらかったから、全部のLIS(1,v)を決めれば構築方法があるのではという直感があった）
234: 2024/03/28(木)21:40 AAS
>>219
解説きとるやん
サンキューガイジ
上界下界はすぐ見えたんだが頂点のリス値をつけると親子間のリス差が常に1以下になるってのが見えなかったな
そこさえ抜ければ構築法が(リス値, 深さ)の辞書順なのは試行錯誤で出てきそう
リス値の貪欲割り当て法は時間かければ解けるので一番の実力要素はリスへの不理解とみた
ためになった
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.834s*