Algorithmyambe2002さんの記事に面白い問題が掲載されていたことをふと思い出して、考えてみました。バイナリツリーの2ノード間の距離を求めるメソッドを作成せよこちらは所謂「ホワイトボードコーディング」で出題された問題だそうです。木が二分木ではない場合、ダブリングを伴ったLCAを答えることが選択肢の一つではないか、と考えました。計算量は\(O(Q\log{}N)\)です。二分木であること、また電話面接だったとのことですので1、おそらく20分以内で簡潔な解法を説明することを要求されているのではないかと感じました。解法はおそらくとてもシンプルなものなのでしょう。2\rfloor\)として親の頂点の番号を取得することができるという性質があります。この性質をうまく使う問題ではないかと思い、考えてみました。\(O(Q\log{}N)\)の解法をすぐ思いつきました。頂点数をN、クエリ数をQとしています。1\)です(dは1以上の整数で、木の深さ)。木の深さが60までだとすると、取りうるNは高々1、3、7、...、1,152,921,504,606,846,975となります。木の深さは\(\log{}N\)です。一般的な木での\(O(QN)\)の解法は以下のようなものになると思います。2つの頂点の深さを合わせる(この回数を\(c_1\)回とします)共通の頂点にたどり着くまで、親をたどる(この回数を\(c_2\)回とします。両方の頂点の移動量は\(2c_2\)となります)図示すると以下のようになるでしょうか。黒い矢印が深さを合わせるフェーズで、灰色の矢印が共通の親を探すフェーズを表します。2c_2\)と計算することができます。一般的な木の場合はDFS等で事前に記録しなければならなさそうですが、こちらも完全二分木ならではの求め方がありそうです。これは各頂点の番号を二進数として表すことで規則性が見えてきました。同じ深さの頂点は高位の1のビットが現れる位置が同じであるわけです。これを行うには何らかのビット演算を行う必要があるように思いました。効率のよろしくないであろう実装を書き始めることも出来そうですが、後に回すことにしました。深さが合っていれば、共通の頂点にたどり着くまで親をさかのぼればよいです。この回数を\(c_2\)として数えます。y\)であるものとしています)。2;これで\(O(Q\log{}N)\)の実装は完成です。考えると、予め深さの調整をせずとも単純に深い方の頂点を上に持ってきてもいい気がします。c;より簡潔に書けました。追いかけっこをしているようなので、そのように名付けます(追いかけ)。深さを合わせる実装も必要なくなってしまいました。...さて、時間が余ってしまいました。ここで面接官が世間話をしてくることはおそらくないでしょう。次の問題を出題するかもしれません。計算量を\(O(Q\log{}N)\)から下げる方法はないか検討することを求めてくるかもしれません。ここで先ほどの図をよく眺めてみます。親の親の頂点番号は場号を右側に2つシフトしたものとなっていますね。nで算出することができそうです。二つの頂点の深さが等しければ、ビットシフトを利用して二分探索をすることができそうです。u;この実装の計算量は\(O(Q\log\log{}N)\)となります。計測してみると、確かに速い。\(O(Q\log{}N)\)のものに比べて10倍速い結果となりました。おざなりにしていた深さを揃える実装を考えてみます。以下のように頂点の高さを揃えたいのです。試しに書いてみたのですが、どうもどんくさい。:どうもうまく書けない。そこでnaoya_t氏にご登場願いました。この話の背景、\(O(Q\log{}N)\)、\(O(Q\log\log{}N)\)の実装アイデア、深さを揃えるところをうまく書けていない...10分ほど会話をしたでしょうか。1時間ほど経ってnaoya_t氏から一報が届きました。実装含め、完了したとのこと。内容は目を疑うようなものでした2。Zero)とビット演算だけで求めることができる、とのことでした。双方の番号のclzを取得して、大きい方の番号をclzの差の分だけ右側にシフトします。これで深さが揃います。1\)ビットだけ右側にずらしてやります。排他的論理和を取って二つの数のビットが異なる初めてのビットまでの位置をclzで取得します。このビット以降をなくしてしまえば、それは共通の祖先の頂点であると言えそうです。Reverse)です。総ビット長(実装では64、図では8)からclzを引いた分が共通の頂点までの距離となります。この距離は2倍しなければならないことに注意してください。\(O(Q\log\log{}N)\)のものに比べてさらに10倍速い。clzは大抵CPUで用意されているので当然と言えば当然です。clzの計算量を\(O(1)\)とすると、全体の計算量は\(O(Q)\)です。Adventarの飛び込みエントリとして書いてみました。氏は多忙であるにも関わらずコミュニティのアクティビティに貢献し続けています。遅筆なところ急ぎ書き起こしたため、読み辛い部分が多いと思います。最近ありがたいことに人付き合いに恵まれ、コンテスト以外でのアクティビティが充実しています。言っても、解けた問題のレビューをしたり、解けなかった問題を教わったり。競技プログラミングのみならず、オンラインコースでの勉強、英会話などなど。充実した時間を過ごしています。アルゴリズムの勉強方法にも少しずつ工夫を取り入れています。派手ではありませんが、レートもジワジワ上がってきていて効果を実感してきています(Codeforcesで100くらい、ですかね)。コンテスト終了時に取り組んでいた問題をコンテスト終了直後にリマインダーに突っ込み、復習する自分が実現したい不明なテクニックがあった場合、コンテスト中でもリマインダーに突っ込むコンテストに参加できなかった知人に良問だと思った問題をリコメンドする(また、知人のレベルではやらなくてよい問題も伝える)良問についてダラダラ語る問題について議論することが相当効いているようです。本文にご登場いただいたnaoya_t氏の発想は自力ではなかなかたどり着けませんし、また氏曰く、自分が考えていた追いかけや二分探索の発想はまずしなかったそうです(ビット演算系がうまく行かなかった後の選択肢なんでしょう)。コンテスト終了後のTLによる感想戦でもこのような知見に出会えるのですが。コンテストからしばらく経ったあとでも議論したりしているとことがいいんでしょうか。面接で求められていたのはどの程度なんでしょうかね。気になるところではあります。題材として引用することを快諾くださったyambe2002さん、どうもありがとうございました。「ビットをゴニョゴニョする」のに、最高位のビットだけ残すことを考えていました。2の冪での床関数です。分岐なしで\(O(log{}N)\)の実装なので、これはこれで大変高速です(これだけ命令があってclzの倍程度)。0000\)を返します。コラボレート可能なエディタにコーディングするよう指示されたそうです↩naoya_t氏の実装を元に筆者の好みで改訂しています(スンマセン)↩おそらくclzのCPU内での実装は\(O(\log{}N)\)のビット演算です。Programming(1...昨年のSIGGRAPH参加後、9月ほどからでしょうか。