Problem G : Entangled Tree 原案 : 野田 模範解答 : 野田・福澤 解説 : 野田
問題 (1) 系統樹を表す木が与えられる 枝同士が接しない、かつ若い番号の葉がなるべく左に来るように並び変えた際、クエリで与えられた葉が左から何番目に来るか求めよ 1 2 3 4 5 6 1 4 2 5 3 6
問題(2) 入力で与えられる情報は枝分かれ(ノード)位置と枝分かれ後のノード番号 ノード数N<=10万
解法 木の構築 トポロジカルソート
木の構築 入力で与えられる枝分かれ情報(ノード情報)から木を構築する ノードを高い順にソート 高い位置の分岐から順に木を構築 それぞれの分岐以下にある葉のうち、最も若い番号を記憶させる 根の番号を記録する
木構造(例) ノード構造体 以上を配列として保持 親ノードへのポインタ(or番号) 子ノードへのポインタ(or番号)配列 (ノード以下にある葉のうち、最も若い葉の番号) 以上を配列として保持
木の構築 1 5 6 3 6 1 4 2 5 1 2 3 4 5 6
木の構築 親ノード→子ノードの書き換え 子ノード→親ノードの書き換え 1 5 6 3 6 1 4 2 5 1 2 3 4 5 6
木の構築 1 5 6 3 6 1 4 2 5 1 2 3 4 5 6
木の構築 1 5 6 3 6 1 4 2 5 1 2 3 4 5 6
木の構築 1 5 6 3 6 1 4 2 5 1 2 3 4 5 6
木の構築 それぞれの分岐以下にある葉のうち、最も若い番号を記憶させる 1 5 6 3 6 3 1 4 1 2 2 5 1 2 3 4 5 6
トポロジカルソート 木の根から若い番号の葉に向かってDFS(深さ優先探索) 葉に到着した際に番号を配列に追加していく
トポロジカルソート 先ほどメモした番号の 小さい順にたどる 葉に到達した場合は その番号を配列に保持する 1 5 6 3 6 3 1 4 1 先ほどメモした番号の 小さい順にたどる 葉に到達した場合は その番号を配列に保持する 1 5 6 3 6 3 1 4 1 2 2 5 1 2 3 4 5 6
トポロジカルソート 1 5 6 3 6 3 1 4 1 2 2 5 1 4 2 3 5 6
トポロジカルソート 1 5 6 トラックバックして 次の枝を探す 3 6 3 1 4 1 2 5 2 1 4 2 5 3 6
トポロジカルソート 1 5 6 3 6 3 1 4 1 2 5 2 1 4 2 5 3 6
トポロジカルソート 1 5 6 3 6 3 1 4 1 2 5 2 1 4 2 5 3 6
トポロジカルソート 1 5 6 3 6 3 1 4 1 2 5 2 1 4 2 5 3 6
計算量 ノード情報を高さでソートする・・・O(NlogN) 各ノード以下の若いノード番号の記録・・・O(N)
注意(1) N=10万のため、計算量がO(N2)となるアルゴリズムを使用することができない O(NlogN)に抑えなければならない
注意(2) 再帰関数は10万回再帰することができない スタックオーバーフローを引き起こす ループとスタックデータ構造で代用する RuntimeError ループとスタックデータ構造で代用する
注意(3) DFSでたどる順番を間違えないようにする 枝を正しくソートしてからたどる 模範解答作成者二名のうち両方ともこれではまりました
模範解答 野田 C++ 143行 福澤 Java 90行
結果 First Submit : - (-) First Accepted : - (-) Reulst : 0/0
ジャッジより きちんと整理してからプログラムを書き始めないと間違い無く嵌ります
御清聴有難うございました