タイトルどうすればいいんですか＞＜
今日の分。28問。
- PKU 2499 Binary Tree
- PKU 1251 Jungle Roads
PKU 2499 Binary Tree
ある地点でのペアの値が (p, q) だとするとその親は p < q なら (p, q-p) で、 p > q なら (p-q, p) である。これはこの二分木の定義より自明。これを順番にやって木を親の方へ手繰っていくというのが基本方針。
ただ、これをそのまま実装すると極端な例で言えば (1, 2000000001) とかいうケースで 2000000000 回も親へ手繰って行く操作が必要になってTLEする。なので、(p, q) に対してたとえば p < q のときは (p, q-p) へ行くのではなく、 q-p > kp となる最大の自然数 k に対して (p, q - (k+1)p) まで行く。つまり p < q である場合は、どんどん手繰って行って p > q になる地点まで一気に行く。逆も同じ。
こうすると、右の子へ行くことをR、左の子へ行くことをLとあらわした場合に "LLLLLLLLLLLLLLLLLLLLL" のような経路に対しては一回の計算で答が出る。また、"RRRRLLLLRRRRLLLL" のような場合には4回でよい。つまり連続したLおよびRをまとめることができる。
この手法をとっても、"LRLRLRLRLRLRLRLRLRLRLRLRL"のように一気に進むことのできる場合がないケースがある。が、このようにLとRが交互に繰り返されるパターンの場合はそのときのペアの値は指数的に増大してすぐに制限である 2*109 を超えるので計算量はたかが知れている。たとえば先の "LRLRLRLRLRLRLRLRLRLRLRLRL"のようにLとRが完全に交互に繰り返されてる場合、その経路におけるペアの値はちょうどフィボナッチ数列になっている(これもこの二分木の定義より自明)。フィボナッチ数列は47番目の要素でもう 2*109 を超える。
知識不足なのでこの方法の計算量を求めることができないが、少なくとも制限値内の値に対してはものすごく高速に解を求められる。
