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のステージだ。部分数列の追加は複数回できるため、最終的な数列の要素数はとても大きなものとなるはずだ
- さて、効率的にクエリを行うために、タイプによって異なるデータ構造を用意することにした
- タイプが1のステージ
- 数値が納まる位置と数値自身
- タイプが2のステージ
- 区間が始まる位置と幅
- タイプが1のステージ
- もう一度記載するが、全てのステージのタイプが1であった場合、数値の数は高々105だ
- さほど多くないので、データ構造にはstd::mapを用いることにした
- 区間の開始位置の探索方法を具体的に考えてみよう
- 以下の例で考えてみる(再掲)
- 区間の開始位置は2、3、5、9となる
- 実際の一次元配列は上記のようなものだ。だが、二分探索を考察するために以下のような作図を行おう
- 各セルに対して区間の番号を追加するとさらによい
- さて、例えば7の位置に対する問い合わせを行った場合は、2を返したい
- 別の言葉で言い表すと、「左閉半開区間の二分探索」とでもいうのだろうか
int n = std::upper_bound(a, a + size, x) - a - 1;
- ここまでを元に実装を行って、提出。無事システムテストをパスした
- 区間の二分探索を実装をするとき、いつもstd::lower_boundかstd::upper_boundを用いるか考えてしまう
- 常々「慣れてなくて危険だなぁ」と考えていた。いい機会なので少し考察する
- 今回の考察を終えても完全に理解することはできなかったので、先に記載しておく
- まず、メソッドの説明を読むことから始めた(cplusplus.com - The C++ Resources Networkを参照した)
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という単語には苦手意識がある)
- そのため、日本語での説明を探した。以下はC++編(標準ライブラリ) 第20章 ソート済みの範囲を扱うアルゴリズムでの説明だ
・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;
- 探索の全体の様子は以下だ
- かなりすっきりしている
- 終了位置を記録するとデバグのときに混乱しそうではあるが、実装がすっきりしたものとなる可能性がある
追記
- 上位コーダーの方々から基調なご意見をいただいたので、引用させていただきます
- @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; }