- 1 名前：デフォルトの名無しさん [04/09/05 16:22]
- プログラムに必要な数学、算数に関する話題について
語りましょう。TIPS/Q&Aスレです。
- 554 名前：デフォルトの名無しさん mailto:sage [2006/07/20(木) 07:11:30 ]
- 550 じゃないが
>>551
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/2409.cpp
方針は以下：
(1) は自明．
(2) はソートして左から数える．ソートしたおかげで単調性が得られ，
一度交わらなくなったらそれより先を調べる必要がなくなる．
(3) は (2) でどこまで調べないといけないかを二分探索を行う．
- 555 名前：デフォルトの名無しさん mailto:sage [2006/07/20(木) 08:09:59 ]
- 拙いPerlですが。
sourcepost.sytes.net/sourcepost/sourceview.aspx?source_id=28099
(i) 区間対の個数はO(nn)、重なりの有無の判定はO(1)だから、全体でO(nn)。
(ii) >>554に同じ。
(iii) 与えられた区間の始点と終点を列挙し、ソートし、各点に何個の始点・終点が重なっているか調べる。
区間のネストの数を把握しながらこの列を走査して重なりの総数を得る。
実際のコードでは始点・終点の個数の計算と最後の操作を一つのループで行っている。
|
 |
