質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.10%

c++のlower_boundについてと配列ごとのソートについて

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 447

l_h_l_h

score 18

以下の問題について解いていました
問題
要約すると、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つだけ実行時エラーが返ってきました
何度も申し訳ありませんが分かる方いらっしゃいましたらご助言お願いします

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • iwanote

    2019/02/11 23:58

    itrator勘違いしてませんか?中の数値は参照してませんよ?先頭から何番目かを見てるだけです。

    キャンセル

  • l_h_l_h

    2019/02/12 00:11

    ありがとうございます
    少し混乱していたようで申し訳ありません

    もう少し調査してみたのですが
    lower_boundだけだと中の数値で、lower_bound()-v.begin()という形なら何番目か、という認識でよろしいでしょうか

    キャンセル

回答 2

checkベストアンサー

+1

質問は次の 4 点でいいでしょうか:

  1. lower_bound() を使った順位の計算
  2. lower_bound() が返す「イテレータ」の扱い
  3. vector を使わない解法
  4. vector<ll> 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<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/13 21:16

    回答ありがとうございます

    「配列を使って解くことができるか」というのは、vectorを使わないで、という意味でした
    しかしメモリの管理が煩雑なことが分かりました
    実はvectorに対する理解が曖昧で極力配列を使ってきたのですが、今後は可変コンテナであるvectorを積極的に使っていこうと思います

    4については頭がこんがらがっていたのと、「市が一つも存在しない場合もある」という条件忘れでした……
    ご丁寧にありがとうございました!

    キャンセル

  • 2019/02/14 23:26

    あれですよ、上限が明確にコンパイル時にわかる可変配列はvector使わないでstd::arrayなどをつかいつつ要素数を自力で管理するほうが高速ですから誤解のないように。

    キャンセル

  • 2019/02/15 01:14

    vector は動的にメモリを確保したり解放したりする必要があるので、配列や std::array に比べれば確保・解放の部分で時間がかかるということになります。特に push_back() は何もしなければ要素数が倍になるたびに再確保をするので、大量の要素を追加するときは遅いです。また、ヒープアクセスは (キャッシュや最適化などを考慮すると) ごくわずかに遅くなる場合があるかもしれません。
    ただし、 push_back() の問題に関しては、上限が分かっているなら reserve() を呼んで事前に確保しておくことで緩和することができます。最初に一回大きな量のメモリ確保がありますが、それ以降の push_back() ではメモリ確保が発生しませんので、十分高速に動作します。それよりも自力で要素数を管理することは面倒だったり思わぬバグを埋め込んだりすることになりかねません。全てを理解した上で、それでもパフォーマンスや止むを得ない制約から vector を使わないことはあるかもしれませんが、基本的には vector を使うと思っておけばよいと思います。特に競技プログラミングにおいては (最低でも初級段階の問題で) 配列を使うか vector を使うかによって AC / WA が変わることは無いと思ってよいですし、むしろ無理に配列を使うことでスタックオーバーフローや初期化ミス/忘れなどのバグを起こしやすくなります。

    キャンセル

  • 2019/02/15 12:37

    いや、AtCorderとかには実行時間ガチ勢もいるので一応書いただけだったんですけどね。

    キャンセル

+1

vector<ll>py[m];
これmがn+1でないとおかしくないですか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/02/12 08:58

    ありがとうございます
    まさにその通りですね……
    取り乱していたようです
    申し訳ありません……

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.10%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る