こどふぉ#480Div2 E問題の反省と真解法のメモ(後日更新予定)
この問題
ダメな解法
番号が一番でかいノードを根とする。
すべての葉をヒープに突っ込む。
ヒープからひとつ取り出してその親をヒープに突っ込む。
k個取り出すまで繰り返す。
Submission #38044094 - Codeforces
(ここにtestcase7を踏まえた、なんでダメなのかという考察が入る)
よさそうな解法
AGC022Cでみた
C: Remainder Game - AtCoder Grand Contest 022 | AtCoder
ノードiを取り除くなら、i未満のノードを全部取り除いたほうがまし
→i未満のノードを全部取り除くことでノードiを取り除かないですむなら、取り除かないでおきたい
→i未満のノードを取り除くことでノードiを取り除かなくてもいけるか？？？
番号が一番でかいノードを根とする。
すべての葉の番号をsetに突っ込む。
取り除くものがなくなるまで以下を繰り返す。
自分より親の番号が大きいような葉の親の番号をsetに突っ込む。
自分より親の番号が大きいような葉を木から取り除く。
setの中身がすべて0になるまで以下を繰り返す。
setの中で、番号が最も大きいものAを探す。
setに含まれるノードで番号がA未満のものの個数を調べる。
k以上なら
setからAを取り除く。
k未満なら
AとAの子孫だったものをダメにして、それらをsetから取り除く。
その個数だけsetに0を突っ込む。
木からAを取り除く。
取り除くものがなくなるまで以下を繰り返す。
自分より親の番号が大きいような葉の親の番号をsetに突っ込む。
自分より親の番号が大きいような葉を木から取り除く。
ダメにしたものを番号順に出力する。
(ここにやってみた結果が入る)
