XavierこのページではCodeIQ*1で結城浩先生から出題されたクロッシング問題について解説しています。今回、締め切りの時間をすっかり忘れていて、結城先生には最低限の回答だけを提出して終わってしまったことをお詫びします。提出しようと思った解説文、感想を、ココに記して公開します。今回の実行時間を測定する問題は、必ずオーダ計算の問題に突き当たるだろうと予想していました。クロッシング問題は、今までの様に問題を解くだけでなく、実際に実行時間を測定することも、かなり実世界よりな問題になったと思います。交点の数は、光線の本数が少ない状態から順番に推定していきました。光線が2本しか無い時は、交わるか交わらないかの2種類だけです。光線が3本ある時は、交点は最大3点になります。光線が3本あって、交点の数が最大になる場合は、既に2本の光線が交わった上で、その両方と3本目の光線が交わる状態です。今回の問題では光線は発射される時点で左から順番に数字が大きなっていきますから、一番大きい数の光線は一番右側から発されます。この光線が一番左側に到着するときに、全ての光線と交わり、交点の数が最大になります。今回の問題は最大ではなく、交点がいくつか数える問題です。そのために、最大からいくつ足りないか、を数え上げることにしました。自分より右側に到達する、nより小さい数を持つ光線の2種類に分けることができます。ここで気をつけないと行けないのはダブりでカウントしてしまう事態です。交点は1つなのに、直線Aで1点、直線Bでもう1点と、計2点としてカウントしてしまうと、重複してカウントしてしまいます。今回はそれを避けるために、到達した光線の内、左側から順番にカウントしていくことにしました。感覚としては、1本1本、光線をほどいていくイメージです(もしくは皮を剥いでいくイメージなのですが、光線が1次元なので、ほどいていくと表現しました)到達した光線のうち左側から1本ずつ光線をほどいていくと、どんどん交点の数は減っていきます。重複をカウントしてしまうことがありません。†さて、交点の数を数えるためには、左側から順番に自身より右側に到達する、自身より小さい数を持つ光線の本数を数えれば良いことになります。これは数式で書けば以下のようになります。数列を表し、ここでは到着した光線の番号の集合です。i番目の光線より右側に到達する光線の本数がS(i)で表されるわけです。今回の問題では、この総和を求めますので、S(i)の総和を求めれば良いことになります。これだけで求めることができます。数学的な議論から実行時間の話へ。オーダ量の問題だろうと思いながら、ここまでコーディングしました。いざcrossing.txtの処理にかかると、これが応答がなかなか返ってこないデバッグをしてみると、計算量が膨大なのが原因で、iの添字が1秒間に数百〜千程度しか増えていません。問題文は約30万の光線がありますので、数千秒のオーダがかかります。(1時間程度)オーダ量の観点から行けば当然の帰結で、二重に総和を求めているので、計算量のオーダはn^2だけかかります。これを削減する必要があります。なってしまっているのは、二重ループがあるせいです。この二重ループはかなり無駄です。ある数nがあったとして、これより右側に存在する、nより小さい数を探すわけで、毎回30万件を探し当てるのはかなりバカバカしいです。今回の問題はもうひとつ特徴がありました。それは光線の番号が必ず1つずつ増え、光線の数と、光線が持つ最大の数が必ず一致する、ということです。ある数nより、小さい数を持つ光線は必ずn-1本存在することが問題で保証されています。自身より小さい数を持つ光線は、自身の左側か右側のどちらかにしか到達しません。左側に到達した光線の数は、走査する過程でアクセスしますので、アクセスした数をもとに、2分木を作成しました2分木を使うことで、自身より小さい数が、2分木内に幾つ含まれているかをカウントしました。†ある要素が、いくつ子を持っているか2分木では通常数え上げる必要があります。今回は計算時間をさらに短縮するため、2分木にデータを挿入する際に、親ノードへ通知する仕組みを作りました。ある要素が追加された時、追加された要素は自身の親、先祖の要素全てで、カウンタを1つずつ足していきます。今回のソースコードで言えば88行目−93行目のwhileループ内がそれです。一つずつ自身の親を手繰りながら、カウンタを1つずつ足していきます。これをすることで、全ての要素は、自身を含めて自身以下にいくつ子要素が存在するか、常に把握してることになります。一方で、今まで現れた数より小さい数の個数を調べるためには、二分木から、一番近い数を探し、その際のノードの要素を数え上げることで実現されます。今回はWindows.hにあるclock()という関数を使いました。程度で計算が完了しました。重ねて描いてみたが、増え方が線型探索と段違いなのが一目瞭然である。