プログラミングの為の数学と算数 vol.2at TECHプログラミングの為の数学と算数 vol.2 - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このｽﾚｯﾄﾞのURL■項目テキスト550:デフォルトの名無しさん 06/07/19 15:07:18 Perl 以外でもいいですか？ 551:デフォルトの名無しさん 06/07/19 15:23:21 >550 >549に代わってお願いします。 ぜひC++で（ry 552:デフォルトの名無しさん 06/07/19 15:23:34 >>糞ｺﾃ そういう態度だから何処へ行っても嫌われる。 553:デフォルトの名無しさん 06/07/19 21:59:50 >549 死に晒せｳﾞｫｹ 554:デフォルトの名無しさん 06/07/20 07:11:30 550 じゃないが >>551 http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/2409.cpp 方針は以下： (1) は自明． (2) はソートして左から数える．ソートしたおかげで単調性が得られ， 一度交わらなくなったらそれより先を調べる必要がなくなる． (3) は (2) でどこまで調べないといけないかを二分探索を行う． 555:デフォルトの名無しさん 06/07/20 08:09:59 拙いPerlですが。 http://sourcepost.sytes.net/sourcepost/sourceview.aspx?source_id=28099 (i) 区間対の個数はO(nn)、重なりの有無の判定はO(1)だから、全体でO(nn)。 (ii) >>554に同じ。 (iii) 与えられた区間の始点と終点を列挙し、ソートし、各点に何個の始点・終点が重なっているか調べる。 区間のネストの数を把握しながらこの列を走査して重なりの総数を得る。 実際のコードでは始点・終点の個数の計算と最後の操作を一つのループで行っている。 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch