脳log[20220415]

2022年04月15日 (金) [AtCoder] 精進。全国統一プログラミング王決定戦予選-D「Restore the Tree」(水 diff)。子孫ノードへのショートカットが M 本追加された(元)木からショートカットを取り除く問題。ショートカット先が子孫ノードに限定されているのでそれほど複雑なグラフになるわけではない。たとえば根から始めて各ノードの深さを決めていくとする。ショートカットがあるので親が１つとは限らないわけで、異なる複数の深さが１つのノードに与えられそうになるけれど、常に最大の深さがそのノードの本来の深さで間違いない。深さを比べれば親がわかる。■しかし TLE。幅優先探索でも max-heap でも min-heap でも時間内に深さが決められない。■提出 #30984890 (AC / 267 ms) 一夜明けての AC。方針転換を決めてからは早かった。すべての親が到着するのを待ってから下方向への探索をキューに入れる。深さを決める問題が部分木ごとに独立した問題になるから問題ない。最後に到着した親が本当の親。うまく型にはまってくれない問題だった。解く側の印象はそうなんだけど、他の人の Ruby での解答をざっと見た印象では、自分のとやっていることがほぼ同じだった。親の数をデクリメントするあたりが特徴的。型にはまらないように見えて解答の型はがっちり決まっていた、ということ。