本履歴

購入した古本の履歴と時々プログラミング

木構造

印象に残ったので書いておく

NWERC 2011 Semi-Live online contest(http://www.spoj.pl/NWERC11/) Bird treeより

既約分数a/bが与えられたときに、Bird Tree(http://www.cs.ox.ac.uk/ralf.hinze/publications/Bird.pdf)上でRoot(1/1)からその分数までの辿り着くためのパス(direction(L,R))を出力せよ。

与えられた木を睨んでみると、対称性と、左が1未満で右が1より大なのが分かる。
つまり最初のdirectionは、a/bが1より小さい場合は左に、1より大きい場合は右に行くしか無い。
さて次だが、例えば7/3に行きたくて、2/1に今いる。どうしたら7/3へ辿り着けるのだろうか。
2/1以下の部分木全体を考え、1/(r-1)で全体を変換すると(再帰的に定義されているのだから)2/1が1/1となるBird Treeが出てくるはず。
すなわち、1/1から1/(7/3-1)へ辿り着くパスを決定すればOK。あれ?これってさっき考えてた問題じゃん、ということでa/bが1になるまでこれを続ける。
それにしてもBird Tree内に全ての分数が出てくるのが驚きだ。

Acceptedコード。分数なのでmathnを使う。

require "mathn"
gets.to_i.times{
	r=gets.to_r
	until r==1
		if r<1 
			print ?L
			r=1/r-1
		else
			print ?R
			r=1/(r-1)
		end
	end
	puts
}

Codeforces Testing Round #3 (http://www.codeforces.com/contest/134) Pairs of Numbersより

(a,b)から(a+b,b), (a,a+b) という2つのペアを作り出す操作がある。nが与えられたときに(1,1)から最小何回の操作でnを含むペアを作り出せるか?

これはコンテスト中に出来なかった問題(Hackされた)。後日TLEと闘いながらなんとか解けた・・・
図を書くと木構造だよなあ。これも睨むと対称性があるのと、必ず任意の整数を含むペアは出てくるのが分かる(1,1)->(2,1)->(3,1)->(4,1)で増やしていけばOK。
方針はkをnより小さい自然数とし、(n,k)が(1,1)に辿り着けるかチェックしていき、その中の最小数を出力する。Bird Treeと違って(1,1)に辿り着けない、すなわちこの木に出てこない可能性があるのが注意。if a>b then a,b=a-b,b else a,b=a,b-a でrootに向かっていく。
(104,5)は5を引き続けることで(4,5)にできるよねーということで剰余計算したり、2.upto(n/2)として計算量を半分にして1130 msでAccepted。時間内にできたとしても、n/2ではなくnのままだと最後のシステムチェックでTLEだもんなあ、Ruby超不利なんですけど。CodechefみたいにCの3倍の実行時間とかハンデ欲しいすw

n=gets.to_i
ans=n-1
2.upto(n/2){|a|
        k=0
        b=n
        until a==b
                d=(b-a-1)/a+1
                k+=d
                b-=a*d
                a,b=b,a
        end
        ans=k if (b==1)&&(k<ans)
}
p ans

木の問題でRootから辿り着くか?系はNodeからRootへ行くのを考えるのがいいみたい。