Codeforces # 223 Div. 2

Codeforces # 223 Div. 2

http://codeforces.com/contest/381

Codeforces # 223 Div. 2に参加。ABCが通り、2,492点。94位。部屋(Room 74)でも初めて1位となり、嬉しい回であった。レートは1,621から1,720へ。紫コーダーになった。

今回のエントリではstd::lower_boundおよびstd::upper_boundメソッドを考察するため、C. Seraja and Prefixesのみ記載することにする。

C. Seraja and Prefixes

http://codeforces.com/contest/381/problem/C

  • 与えられたステージの情報から数列を構築し、クエリに答える問題
    • 入力例は以下だ
6
1 1
1 2
2 2 1
1 3
2 5 2
1 4
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  • ステージの型が1である場合、続く数値を数列に足す
  • ステージの型が2である場合、数列の先頭から続く数値分の長さを切り出し、追加する。さらに続く数値は、追加する回数だ
  • さて、この入力例を処理した結果、数列の要素数は16となる。最後にその全ての要素のクエリを行っている
    • そのため、出力結果は以下となる
1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 4
  • 効率よく考察するため、作図した


  • 白いセルはタイプが1のステージによって追加された要素を表す。同様に灰色のセルはタイプが2のステージによって追加された要素を表している
  • こう見ると、タイプが2のステージは区間であることが分かる
  • さて、この数列に対してクエリを行う
  • クエリの対象が白いセルであれば、要素をそのまま返せばよいことが分かる。例えば以下は、5に対するクエリだ。これは3を返す


  • クエリの対象が灰色のセルであれば、その要素が参照している元の要素を再帰的にクエリすればよい。例えば、4に対するクエリは以下のようになる。これは2を返す


  • 7に対するクエリは以下のようになる


  • 13に対するクエリは以下のようになる。再帰的にクエリをする様子がよく分かる


  • ここまで考えた結果、タイプが2のステージの情報は「区間のまま」管理するとメモリ効率が良さそうなことが分かってくる
  • さて、再帰するクエリは再帰関数で実装したい。だが、過剰な回数の再帰を引き起こさないだろうか?
  • 再帰の回数が多くなるパターンを少し考えてみよう


  • 16に対するクエリは以下のようになる。灰色のセルは数列の先頭からの要素のコピーであるため、再帰の回数がそれほど多くなるような感じはしない...

  • 実装を考えてみよう
  • ステージの数は高々105であるため、全てのステージのタイプが1であった場合でも高々105分の数値を扱えればよい
    • これはあまり問題にならない
  • 問題はタイプが2のステージだ。部分数列の追加は複数回できるため、最終的な数列の要素数はとても大きなものとなるはずだ
    • 単純に数列を構築したらTLEかMLEとなりそうだ。やはり「区間のまま」管理したほうがバランスを維持出来そうに思える
    • また、オーバーフローを防ぐためにクエリの位置や区間の始まる位置をlong longで管理し実装時に細心の注意を払うことにした
  • さて、効率的にクエリを行うために、タイプによって異なるデータ構造を用意することにした
    • タイプが1のステージ
      • 数値が納まる位置と数値自身
    • タイプが2のステージ
      • 区間が始まる位置と幅
  • もう一度記載するが、全てのステージのタイプが1であった場合、数値の数は高々105
    • さほど多くないので、データ構造にはstd::mapを用いることにした
  • ではタイプが2のステージはどうだろう?
    • こちらもタイプが1のステージと同様の考え方を適用できるので、区間の数は高々105であると言える
    • また、区間は重ならない
  • そのため、区間が始まる位置を一次元配列で管理することにした。こうすればクエリの位置を含む区間を二分探索で効率的に探索することができそうだ
  • さらに区間の長さを保持しておけば、クエリの位置と区間の始まる位置から、参照しているセルの位置が算出できる
  • 区間の開始位置の探索方法を具体的に考えてみよう
    • 以下の例で考えてみる(再掲)


  • 区間の開始位置は2、3、5、9となる


  • 実際の一次元配列は上記のようなものだ。だが、二分探索を考察するために以下のような作図を行おう


  • 各セルに対して区間の番号を追加するとさらによい


  • さて、例えば7の位置に対する問い合わせを行った場合は、2を返したい


  • 別の言葉で言い表すと、「左閉半開区間の二分探索」とでもいうのだろうか
  • このようなデータ構造において区間(左閉半開区間だ)の二分探索を行う場合、与えられた位置を用いて、以下のように求めることが出来る(配列をa、配列の大きさをsize、与えられた位置をxとしている)
  int n = std::upper_bound(a, a + size, x) - a - 1;
  • 区間の二分探索を実装をするとき、いつもstd::lower_boundかstd::upper_boundを用いるか考えてしまう
  • 常々「慣れてなくて危険だなぁ」と考えていた。いい機会なので少し考察する
    • 今回の考察を終えても完全に理解することはできなかったので、先に記載しておく

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

lower_bound - C++ Reference

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

upper_bound - C++ Reference
  • これがさっぱり理解できない
    • 英語が難解だ(compareという単語には苦手意識がある)

・lower_bound()

lower_bound()は、指定した値"以上"の要素が最初に現れる位置を返します。 この位置は、現在のソート済みの状態を崩すことなく、指定した値を挿入できる最初の位置になります。

http://www.geocities.jp/ky_webid/cpp/library/020.html

・upper_bound()

upper_bound()は、lower_bound()とよく似ています。upper_bound()の場合には、 指定した値より"大きい"の要素が最初に現れる位置を返します。つまり「以上」と「大きい」の違いです。 これは言い換えると、ソート状態を崩さずに値を挿入できる最後の位置を返すということになります。

http://www.geocities.jp/ky_webid/cpp/library/020.html
  • これらはstd::lower_bound、std::upper_boundを適用した結果をとてもよく言い表している
  • 日本語での説明と英語での説明が随分違うが、以下のように言い表すことができる
  • std::lower_boundは与えられた値以上の値で一番小さいものを返す
  • std::upper_boundは与えられた値より大きい値で一番小さいものを返す
  • なるほど...
  • これらの説明をより理解するために、以下のような実装を行い、実験してみた
  std::vector<int> a = {2, 3, 5, 9};

  std::cout << std::lower_bound(ALL(a), 5) - a.begin() << std::endl;
  std::cout << std::lower_bound(ALL(a), 7) - a.begin() << std::endl;
  std::cout << std::lower_bound(ALL(a), 9) - a.begin() << std::endl;

  std::cout << std::upper_bound(ALL(a), 5) - a.begin() << std::endl;
  std::cout << std::upper_bound(ALL(a), 7) - a.begin() << std::endl;
  std::cout << std::upper_bound(ALL(a), 9) - a.begin() << std::endl;
  • 結果は以下のようになった
2
3
3
3
3
4
  • なるほど、確かに...
    • じっくり考えるためにそれぞれを視覚化した
  • 以下は5に対するstd::lower_boundの結果


  • 以下は7に対するstd::lower_boundの結果


  • 以下は9に対するstd::lower_boundの結果


  • 以下は5に対するstd::upper_boundの結果


  • 以下は7に対するstd::upper_boundの結果


  • 以下は9に対するstd::upper_boundの結果

  • あー
  • 少しすっきりしてきた
  • std::lower_boundとstd::upper_boundは、与えられた値が存在しない場合同じ結果となる
    • これも実装実験を行い、作図した。以下はstd::lower_boundの動作例


  • 以下はstd::upper_boundの動作例

  • なるほど、以下のように言い表すこともできそうだ
  • 与えられた数値が存在する場合、
    • std::lower_boundはその要素の位置を返す
    • std::upper_boundはその次の要素の位置を返す
  • また与えられた数値が存在しない場合、std::lower_boundとstd::upper_boundは同じ結果となる
  • これまで考察したことを応用して、区間を右閉半開区間として扱うことを考えてみる
    • 右閉半開区間が二分探索と親和性が高いことは以前考察した。興味があったら参照して欲しい
    • 以下の例で考えてみる(再掲)


  • 左閉半開区間区間を処理していた際は区間の開始位置を記録していたが、右閉半開区間を処理するために区間の終了位置を記録することにする


  • このデータ構造でstd::lower_boundを用いると、うまく行きそうだ
  • 以下は5に対するstd::lower_boundの結果


  • 以下は7に対するstd::lower_boundの結果


  • 以下は8に対するstd::lower_boundの結果


  • 以下は9に対するstd::lower_boundの結果


  • 右閉半開区間を用いれば、std::lower_boundを用いて以下のように二分探索できる(配列をa、配列の大きさをsize、与えられた位置をxとしている)
  int n = std::lower_bound(a, a + size, x) - a;
  • 探索の全体の様子は以下だ
    • かなりすっきりしている


  • 終了位置を記録するとデバグのときに混乱しそうではあるが、実装がすっきりしたものとなる可能性がある
    • 例えば、確率密度関数から累積分布関数を構築し、逆関数法を適用する際に応用できる。(0, 1]の範囲で値が単純増加する配列を用意し、std::lower_boundでクエリすれば効率が良い(区間の終了値を保存するのがポイント)
  • またこの問題のように区間の開始位置の情報を用いる場合には使えない(区間の開始位置を使って、次のクエリ位置を算出している)。注意が必要だ

追記

  • 上位コーダーの方々から基調なご意見をいただいたので、引用させていただきます
    • @kinabaさん、@kroton1992さん、どうもありがとうございます

  • std::lower_bound、std::upper_boundの本来の用法はstd::equal_rangeを考える分かりやすいか
    • 値が格納されている範囲を左閉半開区間で見つける
    • 配列に値が存在しないときに意味が分からなくなるのが玉にきず
      • 区間としては空なのだが、位置のことを考えると混乱を招きやすいように思う

  • いつか作図したい応用用例

まとめ

  • 今回のエントリでは、std::lower_boundとstd::upper_boundの動作を考察し、まとめた
  • std::lower_boundとstd::upper_boundを用いる際はここで考察したことを意識して扱うようにしてみたいと思う

おまけ

long long l[111111], r[111111];

int q = 0;

std::map<long long, int> map;


int query(long long x)
{
  if (map.count(x))
    return map[x];

  int t = std::upper_bound(r, r + q, x) - r - 1;

  long long o = (x - r[t]) % l[t] + 1;

  return query(o);
}

int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  int m, n;
  
  std::cin >> m;

  long long p = 1;
  
  for (int i = 0; i < m; i ++) {
    int x, y;

    std::cin >> x;

    if (x == 1) {
      std::cin >> x;

      map[p ++] = x;
    }
    else {
      std::cin >> x >> y;

      l[q] = x;
      r[q] = p;
      
      p += x * y;

      q ++;
    }
  }

  std::cin >> n;

  for (int i = 0; i < n; i ++) {
    long long x;

    std::cin >> x;

    std::cout << query(x) << ' ';
  }
  
  std::cout << std::endl;

  return 0;
}