きままにものづくり

日々の気付いたことなんかを書いてます。

SRM658Div1Easy

問題

サイズN*Nの配列xが与えられる。サイズNのツリーを考え、配列の各要素はx[i][j]はiからjまでの距離が偶数か奇数かを示している。与えられた配列の条件を満たすツリーを求めよ。

解法

kmjp.hatenablog.jp
ここの解答を参考にした。

ツリーの構築として、偶数か奇数しか制約がないのでひとつのルートを選び、奇数のノードと偶数のノードを接続すれば、条件を満たすツリーを構築できる。

計算量

O(N^3)

コード