山登り《グラフ理論・根付き木》

木のメニュー【子の頂点・親の頂点・ヒープの判定・頂点の高さ・山登り】

問題【STEP: 1】子の頂点
Task
根付き木の子の頂点番号を昇順に出力してね。

【子の頂点】コード

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b + 1);
      // List[b].push(a + 1);
   };
   const List = [];  // 隣接リスト (片方向)
   const [N, K, R] = lines.shift().split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List[i] = [];
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   for (let i = 0; i < K; i++) {
      const parent = lines.shift() - 1;  // 親の頂点番号 - 1
      console.log(...List[parent].sort((s, b) => s - b));  // List[parent]の要素を昇順に出力
   }
});
hogeちゃんの画像

根付き木の隣接リストを生成して List[親の番号]  の要素を昇順に並べ替えて出力しました。

top
問題【STEP: 2】親の頂点
Task
根付き木の親の頂点番号を出力してね。

【親の頂点】コード

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b + 1);
      // List[b].push(a + 1);
   };
   const List = [];  // 隣接リスト
   const [N, K, R] = lines.shift().split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List[i] = [];
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   for (let i = 0; i < K; i++) {
      const child = Number(lines.shift());  // 子の頂点番号
      if (child === R) {  // child が R (根) なら…
         console.log('');  // 空文字を出力
      } else {  // さもなくば…
         for (let i = 0; i < N; i++) {
            if (List[i].includes(child)) {  // List[i]に child が含まれていれば… 
               console.log(i + 1);  // i + 1 を出力
               break;
            }
         }
      }
   }
});
hogeちゃんの画像
親の頂点は一つだけで 根の親はナシ…。
top
問題【STEP: 3】ヒープの判定
Task
根付き木が最大ヒープになっている？ “YES” または “NO” を出力してね。

【ヒープの判定】コード

reader.on('close', () => {
   const [N, R] = lines.shift().split(' ').map(Number);
   let heap = true;  // 最大ヒープであるかどうかの真偽値
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(Number);
      if (A < B) {  // A (親)が B (子)より小さければ…
         heap = false;  // 最大ヒープに該当しない
         break;
      }
   }
   console.log(heap ? 'YES' : 'NO');
});
hogeちゃんの画像

親要素の値が子要素よりも常に大きいか等しいヒープを最大ヒープだそうです。

top
問題【STEP: 4】頂点の高さ
Task
根付き木の頂点 a_iがb_iの親なら “A”・b_iがa_iの親なら “B” を出力してね。

【頂点の高さ】コード

reader.on('close', () => {
   const adjacency_List = (a, b) => {
      List[a].push(b);
      List[b].push(a);
   };
   const [N, R] = lines[0].split(' ').map(Number);
   const List = [];  // 隣接リスト
   for (let i = 0; i < N; i++) {
      List.push([]);
   }
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      adjacency_List(A, B);
   }
   const root = R - 1;
   let next = [root];  // 次に調べる子の親の頂点
   const done = [root];  // 調査済みの頂点
   const level = [[root]];  // 根(level[0])→根の子(level[1])→level[1]の子(level[2])…の順に保存
   while (next.length > 0) {  // next に要素があれば…
      const child = [];  // 子の頂点を保存する配列
      next.forEach(point => {  // next の各要素(point)について…
         for (const p of List[point]) {  // List[point]の各要素(p)が…
            if (!done.includes(p)) {  // 調査済みでなければ…
               child.push(p);  // p を子の頂点として child に保存
               done.push(p);  // p を調査済みの頂点として done に保存
            }
         }
      });
      next = [...child];  // 親の頂点を child で上書き
      level.push([...child]);  // level に child を保存
   }
   const level2 = level.flat();  // level の要素を展開
   for (let i = 1; i < N; i++) {
      const [A, B] = lines[i].split(' ').map(e => e - 1);
      const [a, b] = [level2.indexOf(A), level2.indexOf(B)];  // [a, b]は[A, B]の添字
      console.log(a < b ? 'A' : 'B');  // a が b より小さければ A が親・逆なら B が親
   }
});
hogeちゃんの画像
とりあえず up。
top
問題【FINAL】山登り
Task
paiza君がいる可能性のあるチェックポイントの番号を昇順で出力してね。

【山登り】コード 1/2

reader.on('close', () => {
   const calc_length = (mine) => {  // 各頂点の根からの距離を求める関数
      for (const child of list[mine]) {  // mine の子要素を child に代入
         if (len_from_root[child] === -1) {  // 子の頂点と根からの距離が初期値なら
            len_from_root[child] = len_from_root[mine] + 1;  // 子の頂点と根からの距離を親の頂点+1とする
            parent[child] = mine;  // 添字 = 子の頂点, 値 = 親の頂点番号
            calc_length(child);  // child の根からの距離を求める
         }
      }
   };
   const [n, t, s, c, d] = lines.shift().split(' ').map(Number);
   const list = new Array(n).fill().map(e => []);
   const [root, start] = [t - 1, s - 1];
   for (let i = 0; i < n - 1; i++) {
      const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   const parent = new Array(n).fill(0);  // 添字 = 子の頂点, 値 = 親の頂点番号 を 記録
   parent[root] = -1;  // root の親は存在しないので - 1
   const len_from_root = new Array(n).fill(-1);  // スタート地点から root までの距離 (初期値 - 1)
   len_from_root[root] = 0;  // root から root の距離は 0
   calc_length(root);  // 各頂点の根からの距離を求める関数を呼び出し
   if (len_from_root[start] <= c) {  // スタート地点からroot までの距離が c 以下なら
      for (let node = 0; node < n; node++) {
         if (len_from_root[node] === len_from_root[start] - c + d) {  // root までの距離が スタート地点からroot までの距離 - c + d と一致する頂点を…
            console.log(node + 1);  // 出力
         }
      }
   } else {  // スタート地点から root までの距離が c より大きければ…
      let highest_node = start;  // スタート地点から…
      for (let i = 1; i <= c; i++) {  // c 段階…
         highest_node = parent[highest_node];  // 親の頂点を辿って移動ルートの最高点を記録
      }
      for (let node = 0; node < n; node++) {  // 各頂点の root からの距離 (len_from_root) を順に調べて…
         if (len_from_root[node] === len_from_root[start] - c + d) {  // 各頂点 の root からの距離が root からゴールの距離と同じなら…
            let reverse_d = node;  // 最終的に到達しうる地点の候補としてmove_dに保存
            for (let j = 0; j < d; j++) {  // 最終的に到達しうる地点の候補から d段階…
               reverse_d = parent[reverse_d];  // 親の頂点を辿りながら移動
            }
            if (reverse_d === highest_node) {  // 移動ルートの最高点まで戻れたら…
               console.log(node + 1);  // node + 1 を出力
            }
         }
      }
   }
});
hogeちゃんの画像

解答コード例を参照しました。

top

【山登り】コード 2/2

reader.on('close', () => {
   const Level_survey = (current, nexts, seen) => {  // root からの 標高距離を調べる関数
      levels.push(current);  // [現在の標高]をlevelsに保存
      while (current.length > 0) {  // current に要素があれば…
         for (const node of current) {  // current の各要素を node に代入
            for (const next of list[node]) {  // next に list[node] のの各要素を代入
               if (!seen.includes(next)) {  // seen に next が含まれていなければ…
                  parent[next] = node;  // next の親要素は node
                  nexts.push(next);  // nexts(次に訪問する標高に該当する要素) に next を保存
                  seen.push(next);  // next を訪問済みとする
               }
            }
         }
         return Level_survey(nexts, [], seen);  // 次の標高に移動して Level_survey() を呼び出し
      }
   };
   const [n, t, s, c, d] = lines.shift().split(' ').map(Number);
   const [root, start] = [t - 1, s - 1];
   const list = new Array(n).fill().map(e => []);
   for (let i = 0; i < n - 1; i++) {
      const [a, b] = lines.shift().split(' ').map(e => e - 1);
      list[a].push(b);
      list[b].push(a);
   }
   const levels = [];  // 添字 = 頂上からの標高距離 (2 次元配列)
   const parent = new Array(n).fill(0);  // 添字 = 子の頂点番号, 値 = 親の頂点番号
   parent[root] = -1;  // root の親は存在しないので -1
   Level_survey([root], [], [root]);
   let highest_node = start;  // スタート地点から…
   for (let l = 1; l <= c; l++) {  // c 段階…
      if (highest_node === root) {
         break;
      }
      highest_node = parent[highest_node];  // 親の頂点を辿りながら登って移動ルートの最高点を記録
   }
   let level_now;
   for (let l = 0; l < levels.length - 1; l++) {
      if (levels[l].includes(start)) {
         level_now = l - c + d;  // paiza が辿り着いた場所の標高
      }
   }
   levels[level_now].sort((s, b) => s - b).forEach(node => {
      if (highest_node === root) {
         console.log(node + 1);
      } else {
         let reverse_d = node;  // 最終的に到達しうる地点の候補として reverse_d に保存
         for (let j = 0; j < d; j++) {  // 最終的に到達しうる地点の候補から d 段階…
            reverse_d = parent[reverse_d];  // 親の頂点を辿りながら移動
         }
         if (reverse_d === highest_node) {  // highest_node まで戻れたら…
            console.log(node + 1);  // node + 1 を出力
         }
      }
   });
});
hogeちゃんの画像

親要素は一つだけなので highest_node まで遡ることができれば出力。

top

コメント