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

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

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

6327閲覧

標準的な順位付け

majiponi

総合スコア1720

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2017/03/25 09:35

編集2017/03/26 07:22

(カードゲームのログの解析プログラム中、)スコアから順位付けをするコードを書いています。書けたことは書けたのですが、かなり複雑になってしまい、もっと簡単な方法、それこそ、標準STLが用意してくれた方法はないかと調べてみたのですが、自分では見つけられなかったので、御存知の方がいらっしゃれば御教授願います。

自分が書いたコードの概要

構造体 R{ 整数型 スコア,順位,プレイヤーID; } R データ[人数]; 人数分、データ[プレイヤーID].スコアをセット; 人数分、データ[プレイヤーID].プレイヤーIDをセット; std::sortでスコア順にデータをソート; 人数分、データ[i].順位をセット; std::sortでプレイヤーID順にデータをソート;

現在検討中のコード1 (Stack Overflowからヒントをもらった)

構造体 R{ 整数型 スコア,順位; } R データ[人数]; R* 順番[人数]; 人数分、データ[プレイヤーID].スコアをセット; 人数分、順番[プレイヤーID]にデータ[人数]のアドレスをセット; std::sortでスコア順に順番をソート; 人数分、順番[i]->順位をセット;

現在検討中のコード2

構造体 R{ 整数型 スコア,順位; } R データ[人数]; 人数分、データ[プレイヤーID].スコアをセット; 人数分、順番[プレイヤーID]に、std::count_ifで自分のスコアより大きいスコアを持つ人数+1をセット;

ちなみにプレイヤー数は4人以下です。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

こんなんでどぉぢゃろ

C++

1#include <algorithm> 2#include <iostream> 3#include <random> 4 5using namespace std; 6 7struct R { 8 int score; 9 int rank; 10 int id; 11}; 12 13int main() { 14 const int N = 100; 15 R data[N]; 16 17 mt19937 gen; 18 uniform_int_distribution<> dist(0,30); 19 auto rnd = [&]() { return dist(gen); }; 20 21 // テキトーな乱数で埋める 22 for (int i = 0; i < N; ++i) { 23 data[i].id = i; 24 data[i].score = rnd(); 25 } 26 27 // scoreでソートする 28 auto score_less = [](const R& x, const R& y) { return x.score > y.score; }; 29 sort(begin(data), end(data), score_less); 30 31 // 順位づけ 32 for (int i = 0; i < N; ++i) { 33 data[i].rank = static_cast<int>(distance(begin(data), lower_bound(begin(data), end(data), data[i], score_less)))+1; 34 } 35 36 // できたかな? 37 cout << "id\trank\tscore\n"; 38 for ( auto item : data ) { 39 cout << item.id << '\t' << item.rank << '\t' << item.score << endl; 40 } 41 42}

実行結果はこんな↓

id rank score 66 1 30 0 2 29 2 2 29 32 2 29 7 2 29 44 6 28 42 6 28 72 6 28 21 6 28 89 6 28 5 11 27 45 12 26 69 12 26 50 12 26 41 12 26 98 16 25 74 16 25 …

人数分、順番[プレイヤーID]に、自分のスコアより大きいスコアを持つ人数+1をセット

なら上記コードの順位づけの部分を

for_each(begin(data), end(data), [&](R& item) { item.rank = static_cast<int>(count_if(begin(data), end(data), [&](const R& t) { return t.score > item.score; })); });

この場合実行結果は:

id rank score 0 1 29 1 44 15 2 1 29 3 52 13 4 96 0 5 10 27 6 92 1 7 1 29 8 92 1 9 25 21 10 52 13 11 22 22 12 79 5 13 75 6 ...

投稿2017/03/25 13:00

編集2017/03/26 01:13
episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

majiponi

2017/03/25 13:08

ID順に表示したいんですよね… それで、2回ソートってなんか煩雑だし、1回にできないかな、というのがテーマです。言葉足らずで申し訳ないorz
episteme

2017/03/25 13:17 編集

キーの異なるふたつのソートをどうやって一回で済ますんです? 得点順で、同じ得点ならIDの若い順 とかならともかく。 ※ てかソートすんのにsort(...)の一行を追加するのが煩雑?
majiponi

2017/03/27 08:33

師匠から、「アルゴリズムのオーダー改善は必要なのか?」と痛烈な指摘を受けたので、一番分かりやすいと思ったeprstemeさんの案を採用します。 ※実際はtuple使っていたので、sortの1文だけでラムダ関数込みで5行近く書いていたのですよ…。質問は要約です。
Chironian

2017/03/27 08:37

おや? 私の回答は、ソートは事実上1回だけですよ。 スコアとプレイヤーIDのペアをスコアでソートして、結果を枚挙しつつ順位設定です。2回ソートするよりは速い場合が多い筈です。
majiponi

2017/03/27 15:43

実は…何が起きているのかよく分からなかったのです、multimap使ったことがなくて…。動きが正しいのは検証して分かった、でもなんで? 一晩寝かせてようやく「ああ、こういうことなのか」と理解できました。なので、一目で理解できたほうにBAしてしまいました…すみませぬorz
Chironian

2017/03/27 16:37

いいえ。こちらこそ、うまく伝えられなくてすいません。
guest

0

こんにちは。

std::multimapを使う案です。
もっとスマートな方法がありそうな気もしますが、ソートと言えばmapしか思いつかない...(setは面倒ですし)

C++

1構造体 R 2{ 3 整数型 スコア,順位; 4}; 5R データ[人数]; 6{ 7 std::multimap<整数型, 整数型> m; 8 std::pair<const 整数型, 整数型>(スコア, プレイヤーID)を人数分mへemplace; 9 整数型 i=0; 10 for (auto&& プレイヤー : m) 11 { 12 データ[プレイヤー.プレイヤーID].順位=++i; 13 データ[プレイヤー.プレイヤーID].スコア=プレイヤー.スコア; 14 } 15}

順位は同じスコアの時の対処が必要です。

投稿2017/03/25 09:52

編集2017/03/25 09:55
Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問