質問: 以下の問題について解いていました 問題 要約すると、Pの値ごとにYをソートできれば良いという問題です 模範解答のコードでは以下のようになっています(少し変更してます) ``` #include using namespace std; typedef long long ll; int main(){ ll n,m; cin>>n>>m; ll p[m],y[m]; vectorpy[m]; for(int i=0;i>p[i]>>y[i]; for(int i=0;ipy[m];をvectorpy[100001];に変えたところ正解扱いになったのですが vectorpy[m];のままだといくつかのテストケースで実行時エラーとなってしまいました pyにpushしていくデータ数はmで間違いないと思うのですが、vector内ではどのようにデータの処理が行われているのでしょうか 色々試したところ[m+1]なら3つほど実行時エラー、[m*2]なら1つだけ実行時エラーが返ってきました 何度も申し訳ありませんが分かる方いらっしゃいましたらご助言お願いします
回答: 質問は次の 4 点でいいでしょうか: 1. `lower_bound()` を使った順位の計算 2. `lower_bound()` が返す「イテレータ」の扱い 3. `vector` を使わない解法 4. `vector py[m];` について とりあえず 1 と 2 に関しては疑問が氷解されたようなので、それについては触れないでいきます。 その前に これは模範回答からこうなっていたのですが... ``` printf("%012lld\n",ll(p[i])*1000000+ int(lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i])-py[p[i]].begin())+1); ``` うーん... `1000000` を掛けるより、普通に次のように二つの別の数字をくっつけて表示するスタイルの方がよい気がします。オーバーフローさせないようにキャストする必要もないですし、 `100000` のように桁を間違えることもないですし、 (これは好みになりますが) より問題文に沿った形になりますしね。ということで、ご紹介まで。 ``` printf("%06d%06d\n", int(p[i]), int(lower_bound(py[p[i]].begin(), py[p[i]].end(), y[i]) - py[p[i]].begin()) + 1); ``` 3. 配列を使った解法 (`vector` を使わない解法) > > またこの問題自体についてですが、p ごとに y をソートしていくのは、普通の C 言語のように配列を使って制限時間内に(2 重ループ使用なしで)解くことは可能でしょうか > > > この言葉の意味を少し計り兼ねているのですが、 * 配列を二重ループなしでソートすることができるか * `vector` を使わないで解くことはできるか のどちらでしょう? ### 配列を二重ループなしでソートすることができるか これはできます。 `std::sort()` は配列に対しても使えます: ``` using namespace std; int arr[3] = {1, 2, 0}; sort(begin(arr), end(arr)); // または次でもよい sort(arr, arr + 3); ``` あるいは自分で quick sort を実装するといったことも普通に可能です。 ### `vector` を使わないで解くことはできるか 本気で `vector` を使わずに解こうとすればできるとは思いますが、そうするメリットはないのではないでしょうか。この問題は、ナイーブにやるには問題が必要とするメモリ領域が大きすぎます。 一般に `vector` を使わない場合の方針は二通りあります: 1. メモリを `new` や `malloc()` を使って動的に確保する方法 2. 十分すぎるサイズの配列を最初に用意しておく方法 #### 1. メモリを `new` や `malloc()` を使って動的に確保する方法 足りなくなったらメモリを自分で確保する方針です。 実はこれは `vector` が内部でやってくれていることと同じです。自前でメモリを管理することは非常に煩雑で、ダングリングポインタ、メモリリーク、二重解放などのバグを **必ず** 埋め込みます。昔からプログラマは皆こうしたバグに苦しめられてきました。それを避けるために `vector` が用意されているのです。必要性がないなら `vector` を使うべきです。 **メモリ管理の勉強のために** ということなら書いてみるのもよいかもしれませんが、現代となっては必要に応じて勉強すればよいことだと思います。 #### 2. 十分すぎるサイズの配列を最初に用意しておく方法 最悪のパターンでもきちんと動作するだけの大量のメモリを最初から取っておく方法です。例えば今回の場合、 * 県が 100000 県あり、全ての県に一つずつ市がある * 市が 100000 市あり、一つの県に全ての市がある ときが最悪の場合です。これを二次元配列で持つには `py[100000][0]` とも `py[1][99999]` ともできないといけないので、全体として `py[100001][100000]` の領域が必要です。つまりだいたい `10^10` (10 の 10 乗) 程度のメモリ領域が必要です。 `py` が int 型で 4 バイトの配列であったとしてもこれはだいたい 40GB ですね。 なぜこんなアホなことになるかというと各ケースごとにかなりの範囲が無駄になっているからです。たとえば全ての県に一つずつ市がある場合、 `py[i][2]` - `py[i][99999]` は完全に使われていません。このあたりは配列はある一つの型だけを最初に決めた数だけしか持てない不自由なコンテナなので仕方ありません。 しかしこれが `vector` の配列であれば、各配列の要素数は可変です。なので、 * 全ての県に一つずつ市がある => 各県に対してだいたい一つ分しかメモリが確保されない * ある県に全ての市がある => その県のみおよそ `m` 個分のメモリを確保してその県以外はメモリが確保されない というふうになります。どのようなケースでも、メモリ消費量がおおよそ市の数 `m` くらいになります。 #### その他の解法 天才的な方法を使うともしかしたらできるのかもしれませんが (一次元配列で `m` 個とって、効率的に要素を挿入していく方法を思い付くとか...?) それは思い付きませんし、そこまでのことが要求されている問題でもないと思います。 4. `vector py[m];` について これは iwanote さんが最初に回答されている通りなのですが (一度理解されたようなので混乱しているだけだと思います、落ち着いて考えてみてください) 、 `py[i]` は何だったかというと、県 `i` に属する市たちが何年に誕生したか、ですよね。 こう書くと分かりにくいのであれば、 `py[P[i]]` は、県 `py[P[i]]` に属する市たちが誕生した年度を集めたもの、という方が分かりやすいでしょうか。 では `P[i]` がとりうる値の範囲はどうだったかというと、問題文には `P[i] <= n` とあります。従って `py[n+1]` が必要です。 `n` と `m` は独立して与えられる数字ですから、 `vector py[m];` として定義されたものはほとんどエラーになるはずです (動いてもたまたま動くだけです) 。 自然に考えると県の数より市の数の方が多い気がしますから、自然には `n <= m` としても問題はないのかもしれませんが、この問題では「市が 1 つも属さない県がある場合に注意してください」とあるので、本当に `n` と `m` は無関係としたほうがよさそうです。