Idiom: Passing reverse iterator to a constructor

文字列\(s\)から反転した文字列\(t\)を作成するとき、これまではコピーして反転という処理をしていました。

  std::string s("string");

            :

  std::string t(s);

  std::reverse(ALL(t)); // tの内容は"gnirts"となる

今日なんとなくこの実装を見て目から鱗が落ちました。コンストラクタにリバースイテレータを渡してしまえばいいんですね。この発想はなかった。

  std::string s("string");

  std::string t(s.rbegin(), s.rend());  // tの内容は元々"gnirts"となる!

「何かを反転したもの」を得たいことはよくあるのでこの手法はこれから活躍しそうです。

Using std::multiset instead of std::priority_queue

std::multisetをstd::priority_queueの代わりに使う実装例を目にしました。std::priority_queueは重いと言われているし、std::multisetのほうが性能がよいのであれば使う価値があるな...と考えて計測してみたところstd::priority_queueよりも3倍重く少しがっかり。まあ知見は得られたのでよしとします。

以下は検証に使った実装です。こちらはstd::priority_queueを使ったもので、数値の小さいものをキューに残そうとします。値が重複していても大丈夫です。

  int N = 1000000, M = 100, K = 1000;

  std::priority_queue<int> pq;

  for (int i = 0; i < N; i ++) {        // N回
    int size = rand() % M;
    
    for (int j = 0; j < size; j ++)     // [0, M)個のランダムな値を追加して
      pq.push(rand());

    while (pq.size() > K)               // キューがK個になるまで大きな数値を取り除く
      pq.pop();                         // (つまり、小さな数値を最大K個残す)
  }

std::multiset版はこちらです。数値の小さいものを残すために値の正負を反転しています(std::multiset::removeがリバースイテレータを取れればいいのですが、そういうものではないようです)。

  std::multiset<int> set;

  for (int i = 0; i < N; i ++) {
    int size = rand() % M;
    
    for (int j = 0; j < size; j ++)
      set.insert(- rand());

    while (set.size() > K)
      set.erase(std::begin(set));
  }

それでもstd::multisetを使う利点があるとすれば、要素を取り出すことなく反復できるところでしょうか(std::priority_queueは取り出す必要があります)。

  // 要素を(結果、降順で)表示する

  for (const auto& i : set)
    std::cerr << - i << std::endl;

Visualizing Rank on Union-Find Tree

縮約を伴ったUnion-Find木は高速に動作することで知られています。以下は蟻本からの抜粋です。

// 木の根を求める
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rank[x] < rank[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
  }
}

木の根を求める際、同時に縮約を行い、また併合の際にはランクを使って木の高さに偏りが発生するのを抑えます。

同時に蟻本には以下のように注記がなされています。

縮約を行って木の高さが変化しても、簡単のため rank を変えることは考えません。

ランクの概念や制限も大体理解しているつもりでしたのでライブラリにほぼ写経した実装を押し込み、習得したものとしていました。ですが、先日参加したコンテストこの実装を見て、憧れの念が生まれました。ランクを使いこなしている。そう感じたからです。

早速蟻本の実装を見直しました。理解していたつもりがスラスラと読めない...後からでも正確にイメージできるように作図することにしました。

  • 木のランクが異なる場合、ランクの小さい木の根からランクの大きい木の根に辺を張る

例えば以下のxとyの頂点を併合することを考えます。頂点の右の数値はランクを表しています。xのランクは1、yのランクは2です。そのため、右のように辺を張ります。

f:id:agw:20180623094352p:plain

\(\mathit{rank}_x < \mathit{rank}_y\)ですので、\(\mathit{rank}_x + 1 \le \mathit{rank}_y\)が常に成り立ちます。ですので、yのランクを更新する必要はありません。

同様に木のランクが異なる場合の例です。

f:id:agw:20180623094401p:plain

  • 木のランクが同じ場合、片方の木の根から他の木の根に辺を張る。そのとき、辺を張られるほうの木のランクを1つ増やす

以下の例でもxとyの頂点を併合することを考えています。双方の木のランクは同じですので、この場合はxからyに辺を張ってみることにしましょう。ランクは2になります。

f:id:agw:20180623094446p:plain

ランクが同じときの辺の張りかたも統一しておくとよいでしょう。ここでは蟻本を見習って、「根のインデックスが大きいものから小さいものに辺を張る」ことにしましょう。これに習うと上の例は以下のようになります。

f:id:agw:20180623094501p:plain

さて、併合時に縮約が起きる様子も見てみましょう。以下は、多少作為的ですが、蟻本の実装ではこうはならない、という例です。今回はzとaを併合します。

zの根を求める際に縮約が発生します(中央の図)。aの根はaですので縮約は発生しません。結果的に、xとaを併合します。

f:id:agw:20180623094510p:plain

さて、どこが作為的なのでしょうか? 実はこれ、縮約された木のランクを意図的に操作しているのです。これまで行儀のいい場合のみ図示してきましたが、蟻本の実装では縮約の際にランクを操作しません。そのため、実際には以下のようになります。

f:id:agw:20180623094521p:plain

併合時に参照されるランクは根のものだけであることに注意してください。言い換えると、一回子供になってしまった頂点のランクはもう気にする必要はありません。少々乱暴ですが、縮約は根の参照の効率を改善するためだけに行われていると言ってもいいでしょう。

蟻本の例には以下のような縮約の例が掲載されています。具体的にはeをfindするとこのような縮約が発生します。

f:id:agw:20180623094531p:plain

蟻本の図にはランクが示されていません。そのため、図からこのようなことが起こっていると捉えてしまっている人は少なくないかもしれません。

f:id:agw:20180623094614p:plain

また、木の中腹の頂点をfindすると以下のような縮約が発生します。これはcをfindした例です。

f:id:agw:20180623094628p:plain

最後に、ここまでの図にはランクが2の木が出てきていました。では実際にランク2の木はどのように作ることがができるでしょう? ランクを2にするには、ランク1の木が二つないといけません(おそらく、今まで説明に使ったx、y、zの3頂点からなる木は作れないように思います)。

f:id:agw:20180623094641p:plain

Idiom: Partial Sorting

書庫から久しぶりに取り出したEffective STLをパラパラめくっていて、std::partial_sortのうまい用法を学びました(第31項「ソートの選択肢を知っておこう」)。昇順に整列して初めから20番目の要素までの合計を取りたいときにはstd::sortを使うより、std::partial_sortを使ったほうが効率的であるようです。

std::vector<int> a;

// ...aを更新する

std::partial_sort(std::begin(a),
                  std::begin(a) + 20,
                  std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

イテレータを3つ取る関数には苦手意識がありましたが、この用法は覚えやすいですし、手軽な定数倍高速化として重宝するかもしれません。計算量は面白く、

$$ O({}(\mathrm{last} - \mathrm{first})\log(\mathrm{middle} - \mathrm{first}){}) $$

だそうです。線形の項が配列全体の要素数なので劇的に計算量が減るわけではなさそうですが、以下のように一定の効果は期待できそうです。

$$ \begin{array}{cccc} \mathrm{first} & \mathrm{middle} & \mathrm{last} & \text{Complexity}\\ \hline 0 & 10 & 1000 & 1000 \times 3.322\\ 0 & 100 & 1000 & 1000 \times 6.644\\ 0 & 500 & 1000 & 1000 \times 8.966\\ 0 & 1000 & 1000 & 1000 \times 9.966\\ \end{array} $$

よしよし、一つ賢くなったぞ...と喜んでいたのも束の間、合計を取りたいのであればstd::nth_elementで十分であることに気づきました。std::nth_elementはstd::partial_sortと書式がほとんど一緒ですが、std::partial_sortが先頭から20要素までに上位20個の要素を整列して格納するのに比べ、先頭から20要素までに上位20個の要素を格納する、とのこと。

std::vector<int> a;

// ...aを更新する

std::nth_element(std::begin(a),
                 std::begin(a) + 20,
                 std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

(この用途では1)計算量はstd::parital_sortに比べとても効率的で、\(O(\mathrm{last} - \mathrm{first})\)だそうです。\(\log\)が落ちてしまうんですね。


  1. C++17から追加されたstd::nth_elementの計算量は少々複雑であるようです

Multi-start Breadth First Search

先日参加したコンテストで以下のような問題が出題されました1

シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。ただし、頂点の最大数は\(10^{5}\)である。

この問題、コンテスト中には全く手が出ませんでした。それぞれの頂点から幅優先探索を行なって任意のグループに属する頂点に出会う度に記録すれば、目的はまあ達成です。ですが、計算量は軽く見積もっても\(O(N^{2})\)。\(10^{10}\)を超えてしまいます。これは駄目です。

また、制約から考えると、\(10^{5} \times 100\)のテーブルを用意して記録していけばよいように思うのですが、うまく埋めていくことができませんでした。

このときは次のように考えていました。

  • 各頂点から幅優先探索を行う。訪れた頂点のグループ情報を得る。そのグループに初めて訪れているなら、距離を最短距離として記録する(全てのグループに出会ったらその頂点に関しての探索は終了する)

さてコンテスト終了後に色々考えても計算量が落とせなかったので他のコンテスタントの実装を読んでみました。皆幅優先探索を実装しているようですが、探索をグループの数分しか行なっていません...はて?

ポイントは以下でした。

  • 幅優先探索の開始点はグループに属する全頂点とする(!)
  • 幅優先探索を行う。先ほどのようにグループ情報を集めるのではなく、開始点のグループ情報を伝搬するようにする

なるほど、これなら計算量も\(O(MN)\)に落とすことができます。「多点開始幅探索」、とでも呼称できそうな技法です。

以下のような盤面を考えてみます。ここで、グループは4色の色として表しています。また、グラフは表示されているよりも広く存在しています。

f:id:agw:20180604152628p:plain:w350:h350

単点開始幅優先探索では以下のように探索を行います。この緑色の頂点はすぐに、青色と紫色の点を見つけることができますが、赤色の頂点にたどり着くまでには3ステップかかっていることが分かります。

f:id:agw:20180604152739p:plain

赤色の頂点にたどり着いた時点で自分が属する色以外の3色の頂点にたどり着いたのでここで探索を打ち切ることはできますが、最悪\(O(N)\)の探索を\(N\)回繰り返さなければならないので、計算量は依然\(O(N^{2})\)と考えたほうがよいでしょう。

では多点開始幅探索を見て見ましょう。探索は以下のようになされているようです。先ほどの単開始点から行う幅優先探索に比べて、ほとんどの頂点をすぐ網羅することも注目しましょう。

f:id:agw:20180604153135p:plain

一回の探索で訪れる頂点の数は単点開始でも多点開始でも\(N\)ですが、探索を全体で\(N\)回(最大\(10^{5}\)回)やらなければいけないか、\(M\)回(最大100回)でいいのかで総合的な計算量は大きく変わります。ぜひ覚えておきたい技法です。


  1. 少し簡潔な問題としています

Idiom: Enumerate ranges that decrease(but not strictly)

コンテストに参加していると、数列の部分的に降順になっている区間を列挙することを求められることがままあるのですが、苦手意識がありました。図でいえば、[4, 9]、[18, 21]、[23, 24]を列挙することです。

f:id:agw:20180215092113p:plain

この小問題、自分にはなかなか難しいものでした。特に初めの区間のように、単調に減少しないものを処理しなければならない場合は無駄に複雑な実装をして時間を浪費することが多かったように思います(この問題を見るたびに「隣り合う値から微分を検出すれば書けるのでは?」と考えてしまうのが敗因です)。

今日参加したコンテストでも同じように迷い、しゃくとりを使えば簡潔に書けることにやっと気づきました。

for (int i = 1; i <= N; )
  if (a[i] <= a[i + 1]) {
    i ++;
  }
  else {
    for ( ; i <= N && a[i] >= a[i + 1]; i ++)
      ;

    ranges.emplace_back(i, j);  // 区間はinclusive。[i, j]
  } 

しゃくとり以外に工夫していることといえば、処理を簡潔にするために最初と最後に番兵を入れていることでしょうか(実際には先頭の番兵を\(-\infty\)、最後の番兵は\(\infty\)としています)。

f:id:agw:20180215092108p:plain

隣り合う値から微分を検出しようとしてうまく行かなかったのですが、番兵のアイデアはそのときに微分を確実に取れるように、と思いついたものです(この問題設定だと先頭はなくてもよい)。面白いですね。

これからは迷うことなく書くことができそうです。

Finding Distance Between Two Nodes of a Binary Tree

yambe2002さんの記事に面白い問題が掲載されていたことをふと思い出して、考えてみました。

バイナリツリーの2ノード間の距離を求めるメソッドを作成せよ

こちらは所謂「ホワイトボードコーディング」で出題された問題だそうです。つまり、面接の問題です。

木が二分木ではない場合、ダブリングを伴ったLCAを答えることが選択肢の一つではないか、と考えました。計算量は\(O(Q\log{}N)\)です。しかし二分木であること、また電話面接だったとのことですので1、おそらく20分以内で簡潔な解法を説明することを要求されているのではないかと感じました。解法はおそらくとてもシンプルなものなのでしょう。

根の番号を1とした二分木では、頂点の番号をiとした場合に

  • \(\lfloor{}i / 2\rfloor\)として親の頂点の番号を取得することができる

という性質があります。この性質をうまく使う問題ではないかと思い、考えてみました。

f:id:agw:20171206082249p:plain

まず\(O(Q\log{}N)\)の解法をすぐ思いつきました。頂点数をN、クエリ数をQとしています。二分木なので想定して、頂点数Nはたかだか\(2^d - 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\)となります)

図示すると以下のようになるでしょうか。黒い矢印が深さを合わせるフェーズで、灰色の矢印が共通の親を探すフェーズを表します。

f:id:agw:20171206082406p:plain

\(c_1\)と\(c_2\)から二つの頂点の距離は\(c_1 + 2c_2\)と計算することができます。

頂点の深さを求めるにはどうしたらよいでしょう? 一般的な木の場合はDFS等で事前に記録しなければならなさそうですが、こちらも完全二分木ならではの求め方がありそうです。これは各頂点の番号を二進数として表すことで規則性が見えてきました。

f:id:agw:20171206082442p:plain

つまり、同じ深さの頂点は高位の1のビットが現れる位置が同じであるわけです。これを行うには何らかのビット演算を行う必要があるように思いました。おそらく効率のよろしくないであろう実装を書き始めることも出来そうですが、後に回すことにしました。

深さが合っていれば、共通の頂点にたどり着くまで親をさかのぼればよいです。この回数を\(c_2\)として数えます。

f:id:agw:20171206082549p:plain

実装はおそらく以下のようなものになるのではないでしょうか(ここから全編を通して\(x \le y\)であるものとしています)。

  // ゴニョゴニョした結果、xとyの深さは揃っているものとする

  int c2 = 0;

  for ( ; x != y; c2 ++, x /= 2, y /= 2)
    ;

  return c1 + c2 * 2;

これで\(O(Q\log{}N)\)の実装は完成です。

こう考えると、予め深さの調整をせずとも単純に深い方の頂点を上に持ってきてもいい気がします。

  int c = 0;

  for ( ; x != y; c ++)
    (x > y ? x : y) /= 2;

  return c;

より簡潔に書けました。追いかけっこをしているようなので、そのように名付けます(追いかけ)。深さを合わせる実装も必要なくなってしまいました。めでたしめでたし。

...さて、時間が余ってしまいました。ここで面接官が世間話をしてくることはおそらくないでしょう。次の問題を出題するかもしれません。また、計算量を\(O(Q\log{}N)\)から下げる方法はないか検討することを求めてくるかもしれません

ここで先ほどの図をよく眺めてみます。親の親の頂点番号は場号を右側に2つシフトしたものとなっていますね。これは利用できないでしょうか?

同様に、n個上の親の頂点の番号はx >> nで算出することができそうです。二つの頂点の深さが等しければ、ビットシフトを利用して二分探索をすることができそうです。

f:id:agw:20171206082629p:plain

  // ゴニョゴニョした結果、xとyの深さは揃っているものとする

  int l = -1, u = 66;

  while (u - l > 1) {
    int m = (l + u) / 2;

    ((x >> m) == (y >> m) ? u : l) = m;
  }

  return c1 + 2 * u;

この実装の計算量は\(O(Q\log\log{}N)\)となります。計測してみると、確かに速い。\(O(Q\log{}N)\)のものに比べて10倍速い結果となりました。

さて、おざなりにしていた深さを揃える実装を考えてみます。以下のように頂点の高さを揃えたいのです。

f:id:agw:20171206082536p:plain

試しに書いてみたのですが、どうもどんくさい。

  int c1 = 0, c2 = 0;

  long long s = (xのビットをゴニョゴニョする), t = (yのビットをゴニョゴニョする);

  for ( ; s != t; t /= 2, y /= 2, c1 ++)    // 深さを揃える
    ;
                     :

どうもうまく書けない。そこでnaoya_t氏にご登場願いました。この話の背景、\(O(Q\log{}N)\)、\(O(Q\log\log{}N)\)の実装アイデア、深さを揃えるところをうまく書けていない...10分ほど会話をしたでしょうか。

1時間ほど経ってnaoya_t氏から一報が届きました。実装含め、完了したとのこと。内容は目を疑うようなものでした2

  int c = __builtin_clzll(x) - __builtin_clzll(y);

  return c + (64 - __builtin_clzll(x ^ (y >> c))) * 2;

結局のところ、二分探索も必要なく3先頭からの0のビットの数を数えること(clz / Count Leading Zero)とビット演算だけで求めることができる、とのことでした。びっくり4

まず双方の番号のclzを取得して、大きい方の番号をclzの差の分だけ右側にシフトします。これで深さが揃います。以下の例の場合、\(5 - 4 = 1\)ビットだけ右側にずらしてやります。

f:id:agw:20171207100732p:plain

さらに、排他的論理和を取って二つの数のビットが異なる初めてのビットまでの位置をclzで取得します。このビット以降をなくしてしまえば、それは共通の祖先の頂点であると言えそうです。またその距離は右側からこのビットまでのビット数(bsr / Bit Scan Reverse)です。つまり総ビット長(実装では64、図では8)からclzを引いた分が共通の頂点までの距離となります。この距離は2倍しなければならないことに注意してください。

f:id:agw:20171207100716p:plain

さて、計測です。\(O(Q\log\log{}N)\)のものに比べてさらに10倍速い。clzは大抵CPUで用意されているので当然と言えば当然です。clzの計算量を\(O(1)\)とすると、全体の計算量は\(O(Q)\)です。

ちょっとしたあとがき

このブログはnico_shindanninさんが主宰するCompetitive Programming Advent Calendar 2017 - Adventarの飛び込みエントリとして書いてみました。氏は多忙であるにも関わらずコミュニティのアクティビティに貢献し続けています。いつも本当にありがとうございます(就寝するときはシンガポールに足を向けないようにしています :))。遅筆なところ急ぎ書き起こしたため、読み辛い部分が多いと思います。ごめんなさい。

最近ありがたいことに人付き合いに恵まれ、コンテスト以外でのアクティビティが充実しています。と言っても、解けた問題のレビューをしたり、解けなかった問題を教わったり。競技プログラミングのみならず、オンラインコースでの勉強、英会話などなど。大変充実した時間を過ごしています。

アルゴリズムの勉強方法にも少しずつ工夫を取り入れています。あまり派手ではありませんが、レートもジワジワ上がってきていて効果を実感してきています(Codeforcesで100くらい、ですかね)。

  • コンテスト終了時に取り組んでいた問題をコンテスト終了直後にリマインダーに突っ込み、復習する
  • 自分が実現したい不明なテクニックがあった場合、コンテスト中でもリマインダーに突っ込む
  • コンテストに参加できなかった知人に良問だと思った問題をリコメンドする(また、知人のレベルではやらなくてよい問題も伝える)
  • 良問についてダラダラ語る

問題について議論することが相当効いているようです。本文にご登場いただいたnaoya_t氏の発想は自力ではなかなかたどり着けませんし、また氏曰く、自分が考えていた追いかけや二分探索の発想はまずしなかったそうです(ビット演算系がうまく行かなかった後の選択肢なんでしょう)。もちろんコンテスト終了後のTLによる感想戦でもこのような知見に出会えるのですが。コンテストからしばらく経ったあとでも議論したりしているとことがいいんでしょうか。

さて、面接で求められていたのはどの程度なんでしょうかね。気になるところではあります。題材として引用することを快諾くださったyambe2002さん、どうもありがとうございました。

ちょっとした追記

「ビットをゴニョゴニョする」のに、最高位のビットだけ残すことを考えていました。つまり、2の冪での床関数です。分岐なしで\(O(log{}N)\)の実装なので、これはこれで大変高速です(これだけ命令があってclzの倍程度)。

inline long long bfloor(long long x)
{
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x |= x >> 32;
  return x - (x >> 1);
}

例えば\(0010\ 1011\)を渡すと\(0010\ 0000\)を返します。


  1. コラボレート可能なエディタにコーディングするよう指示されたそうです

  2. naoya_t氏の実装を元に筆者の好みで改訂しています(スンマセン)

  3. おそらくclzのCPU内での実装は\(O(\log{}N)\)のビット演算です。分岐不要な二分探索として実装されているものも多いようです

  4. 実際のところ、__builtin_clzは引数に0を取った場合の返り値が未定義となりますので、long long z = x ^ (y >> c); return z ? c + (64 - __builtin_clzll(z)) * 2 : c;等としなければなりません