Q&A
itrator勘違いしてませんか？中の数値は参照してませんよ？先頭から何番目かを見てるだけです。
以下の問題について解いていました
問題
要約すると、Pの値ごとにYをソートできれば良いという問題です
模範解答のコードでは以下のようになっています（少し変更してます）
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll n,m; cin>>n>>m; ll p[m],y[m]; vector<ll>py[m]; for(int i=0;i<m;i++)cin>>p[i]>>y[i]; for(int i=0;i<m;i++)py[p[i]].push_back(y[i]); for(int i=0;i<n;i++)sort(py[i+1].begin(),py[i+1].end()); for(int i=0;i<m;i++){ 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); } }
例えば入力例1
2 3
1 32
2 63
1 12
のとき、pyはpごとにソートされているので、
py[1]={12,32} py[2]={63}
という風になっていると思います
出力ではまず、py[p[i]]内でlower_boundでy[i]以上のイテレータを返すので、初めは32を返すと思います
その後のpy[p[i]].begin()+1では、py[p[i]]のうちの初めの要素に1足したものが返ってくるのでpy[i]の最初の要素12+1の13が返ってきて、結果は32-13=19となってしまうように思います
しかし実際はそうはなっていないのでどこかで私が解釈を誤っているのだと思うのですが、どこだか分かりません
また、何が起きているのか確かめようとして以下のようなコードを追加したのですが
for(int i=0;i<m;i++){ printf("%d",ll(lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]))); }
invalid castのエラーが出てしまいます
vectorはlong long int型にキャストできないというような内容のようですが、上記の模範解答はOKで、そこから-py[p[i].begin()の部分を抜いた出力は不適切となるのはどうしてでしょうか
またこの問題自体についてですが、pごとにyをソートしていくのは、普通のC言語のように配列を使って制限時間内に(2重ループ使用なしで)解くことは可能でしょうか
どれか1つについてで良いので、もしよければ回答よろしくお願いします
追記：イテレータについて勘違いしていたようです
注意深く調べたところ
*lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]) なら中身の数値
lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]) なら数値の番地
lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i])-py[p[i]].begin() なら「数値の番地-先頭の数値の番地」すなわち「数値が何番目か」
ということであると分かりました
出力に関してもキャストを外したところ無事実行でき、上記のそれぞれを自分で確認できました
要はこちらの不注意でした、申し訳ありません。また、ご指摘いただいた方は有難うございました
一応、普通の配列でもできないかどうか少し気になっているので質問は数日間残しておきます（回答がつかなければそのまま自己解決という形にさせていただきます）
配列を使った方法は、pについてクイックソートを使うときにその数字が元々何番目だったかなどの情報を保持しておけばいけるのではないかと考えたのですが、私の実装力では試せませんでした
追記2：何度もすみません
上述のプログラムについて、vector<ll>py[m];をvector<ll>py[100001];に変えたところ正解扱いになったのですが
vector<ll>py[m];のままだといくつかのテストケースで実行時エラーとなってしまいました
pyにpushしていくデータ数はmで間違いないと思うのですが、vector内ではどのようにデータの処理が行われているのでしょうか
色々試したところ[m+1]なら3つほど実行時エラー、[m*2]なら1つだけ実行時エラーが返ってきました
何度も申し訳ありませんが分かる方いらっしゃいましたらご助言お願いします
ありがとうございます
少し混乱していたようで申し訳ありません
もう少し調査してみたのですが
lower_boundだけだと中の数値で、lower_bound()-v.begin()という形なら何番目か、という認識でよろしいでしょうか
回答2件
0
ベストアンサー
質問は次の 4 点でいいでしょうか:
lower_bound()を使った順位の計算lower_bound()が返す「イテレータ」の扱いvectorを使わない解法vector<ll> py[m];について
とりあえず 1 と 2 に関しては疑問が氷解されたようなので、それについては触れないでいきます。
その前に
これは模範回答からこうなっていたのですが...
cpp
1printf("%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 のように桁を間違えることもないですし、 (これは好みになりますが) より問題文に沿った形になりますしね。ということで、ご紹介まで。
cpp
1printf("%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() は配列に対しても使えます:
cpp
1using namespace std; 2int arr[3] = {1, 2, 0}; 3sort(begin(arr), end(arr)); 4// または次でもよい 5sort(arr, arr + 3);
あるいは自分で quick sort を実装するといったことも普通に可能です。
vector を使わないで解くことはできるか
本気で vector を使わずに解こうとすればできるとは思いますが、そうするメリットはないのではないでしょうか。この問題は、ナイーブにやるには問題が必要とするメモリ領域が大きすぎます。
一般に vector を使わない場合の方針は二通りあります:
- メモリを
newやmalloc()を使って動的に確保する方法 - 十分すぎるサイズの配列を最初に用意しておく方法
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<ll> py[m]; について
これは iwanote さんが最初に回答されている通りなのですが (一度理解されたようなので混乱しているだけだと思います、落ち着いて考えてみてください) 、
py[i] は何だったかというと、県 i に属する市たちが何年に誕生したか、ですよね。
こう書くと分かりにくいのであれば、 py[P[i]] は、県 py[P[i]] に属する市たちが誕生した年度を集めたもの、という方が分かりやすいでしょうか。
では P[i] がとりうる値の範囲はどうだったかというと、問題文には P[i] <= n とあります。従って py[n+1] が必要です。 n と m は独立して与えられる数字ですから、 vector<ll> py[m]; として定義されたものはほとんどエラーになるはずです (動いてもたまたま動くだけです) 。
自然に考えると県の数より市の数の方が多い気がしますから、自然には n <= m としても問題はないのかもしれませんが、この問題では「市が 1 つも属さない県がある場合に注意してください」とあるので、本当に n と m は無関係としたほうがよさそうです。
投稿2019/02/12 16:19
総合スコア429
回答ありがとうございます
「配列を使って解くことができるか」というのは、vectorを使わないで、という意味でした
しかしメモリの管理が煩雑なことが分かりました
実はvectorに対する理解が曖昧で極力配列を使ってきたのですが、今後は可変コンテナであるvectorを積極的に使っていこうと思います
4については頭がこんがらがっていたのと、「市が一つも存在しない場合もある」という条件忘れでした……
ご丁寧にありがとうございました！
あれですよ、上限が明確にコンパイル時にわかる可変配列はvector使わないでstd::arrayなどをつかいつつ要素数を自力で管理するほうが高速ですから誤解のないように。
vector は動的にメモリを確保したり解放したりする必要があるので、配列や std::array に比べれば確保・解放の部分で時間がかかるということになります。特に push_back() は何もしなければ要素数が倍になるたびに再確保をするので、大量の要素を追加するときは遅いです。また、ヒープアクセスは (キャッシュや最適化などを考慮すると) ごくわずかに遅くなる場合があるかもしれません。
ただし、 push_back() の問題に関しては、上限が分かっているなら reserve() を呼んで事前に確保しておくことで緩和することができます。最初に一回大きな量のメモリ確保がありますが、それ以降の push_back() ではメモリ確保が発生しませんので、十分高速に動作します。それよりも自力で要素数を管理することは面倒だったり思わぬバグを埋め込んだりすることになりかねません。全てを理解した上で、それでもパフォーマンスや止むを得ない制約から vector を使わないことはあるかもしれませんが、基本的には vector を使うと思っておけばよいと思います。特に競技プログラミングにおいては (最低でも初級段階の問題で) 配列を使うか vector を使うかによって AC / WA が変わることは無いと思ってよいですし、むしろ無理に配列を使うことでスタックオーバーフローや初期化ミス/忘れなどのバグを起こしやすくなります。
いや、AtCorderとかには実行時間ガチ勢もいるので一応書いただけだったんですけどね。
あなたの回答
tips
プレビュー
