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

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

新規登録して質問してみよう
ただいま回答率
87.20%
ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

C++

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

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

解決済

stable_sort()をしているのに安定ソートが出来ない

kay_ventris4
kay_ventris4

総合スコア263

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

C++

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

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

1回答

0リアクション

0クリップ

392閲覧

投稿2022/07/17 17:23

編集2022/07/17 19:22

問題
ABC260 B問題

正解コード(Python3)
ソートの順番は、優先度の低いものから先にやっていくという方針です。

Python

N, X, Y, Z = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) ans = [] passed = {} for i in range(N): passed[i + 1] = False score1 = [] for i in range(N): score1.append([A[i], B[i], A[i] + B[i], i + 1]) score1.sort(key = lambda x: x[3], reverse = True) score1.sort(key = lambda x: x[0]) L1 = len(score1) for i in range(L1 - 1, L1 - X - 1, -1): passed[score1[i][3]] = True ans.append(score1[i][3]) score2 = [] for i in range(L1): if passed[score1[i][3]] == False: score2.append(score1[i]) score2.sort(key = lambda x: x[3], reverse = True) score2.sort(key = lambda x: x[1]) L2 = len(score2) for i in range(L2 - 1, L2 - Y - 1, -1): passed[score2[i][3]] = True ans.append(score2[i][3]) score3 = [] for i in range(L2): if passed[score2[i][3]] == False: score3.append(score2[i]) score3.sort(key = lambda x: x[3], reverse = True) score3.sort(key = lambda x: x[2]) L3 = len(score3) for i in range(L3 - 1, L3 - Z - 1, -1): ans.append(score3[i][3]) ans.sort() for el in ans: print(el)

不正解コード(C++17)
上のPythonのアルゴリズムと全く同じ方針でC++で行おうとしたものです。

C++

#include <bits/stdc++.h> #include <math.h> using namespace std; #define ll long long /* import vector from standard input */ vector<ll> import_vector(ll n) { vector<ll> li; for (ll i = 0; i < n; i++) { ll j; cin >> j; li.push_back(j); } return li; } void solve() { ll N, X, Y, Z; cin >> N >> X >> Y >> Z; vector<ll> A = import_vector(N); vector<ll> B = import_vector(N); map<ll, bool> passed = {}; for (ll i = 1; i < N + 1; i++) { passed[i] = false; } vector<ll> ans = {}; vector<vector<ll>> score1 = {}; for (ll i = 0; i < N; i++) { score1.push_back({A.at(i), B.at(i), A.at(i) + B.at(i), i + 1}); } sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];}); reverse(score1.begin(), score1.end()); sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[0] < beta[0];}); ll L1 = score.size(); for (ll i = L1 - 1; i >= L1 - X; i--) { passed[score1.at(i).at(3)] = true; ans.push_back(score1.at(i).at(3)); } vector<vector<ll>> score2 = {}; for (ll i = 0; i < score.size(); i++) { if (passed[score1.at(i).at(3)] == false) { score2.push_back(score1.at(i)); } } sort(score2.begin(), score2.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];}); reverse(score2.begin(), score2.end()); sort(score2.begin(), score2.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[1] < beta[1];}); ll L2 = score2.size(); for (ll i = L2 - 1; i >= L2 - Y; i--) { passed[score2.at(i).at(3)] = true; ans.push_back(score2.at(i).at(3)); } vector<vector<ll>> score3 = {}; for (ll i = 0; i < score2.size(); i++) { if (passed[score2.at(i).at(3)] == false) { score3.push_back(score2.at(i)); } } sort(score3.begin(), score3.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];}); reverse(score3.begin(), score3.end()); sort(score3.begin(), score3.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[2] < beta[2];}); ll L3 = score3.size(); for (ll i = L3 - 1; i >= L3 - Z; i--) { ans.push_back(score3.at(i).at(3)); } sort(ans.begin(), ans.end()); for (ll el: ans) { cout << el << endl; } } int main() { solve(); }

改善策と質問
後者がうまくいかなかった理由として、C++のSTLで実装されるsort()が安定ソートではなく不安定ソートである為、ケースによっては受験者の番号の順序を保存したまま点数を並び替え出来ないからと推測しています。そうであるとした場合そこで、例えば

C++

sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];}); reverse(score1.begin(), score1.end()); sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[0] < beta[0];});

C++

stable_sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];}); reverse(score1.begin(), score1.end()); stable_sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[0] < beta[0];});

としようとしたのですが、ラムダ関数をstable_sort()には使えないとコンパイルエラーが起きました。このような場合、どのようにすれば所望の出力を得られるのでしょうか。素人質問にて恐縮ですが、お力添え頂ける箇所が御座いましたら、ご教授のほど宜しくお願い申し上げます。

追記)このようにソート関数を自作しても同じテストケースで引っかかり駄目でした:

C++

#include <bits/stdc++.h> #include <math.h> using namespace std; #define ll long long /* import vector from standard input */ vector<ll> import_vector(ll n) { vector<ll> li; for (ll i = 0; i < n; i++) { ll j; cin >> j; li.push_back(j); } return li; } /* sorted(li, key = lambda x: x[K], ascending = x) */ vector<vector<ll>> key_sort(vector<vector<ll>> li, ll K, bool x) { vector<vector<ll>> ans = {}; for (ll i = 0; i < li.size(); i++) { ans.push_back(li.at(i)); } for (ll i = 0; i < ans.size(); i++) { swap(ans.at(i).at(0), ans.at(i).at(K)); } if (!x) { stable_sort(ans.begin(), ans.end()); reverse(ans.begin(), ans.end()); } else { stable_sort(ans.begin(), ans.end()); } for (ll i = 0; i < ans.size(); i++) { swap(ans.at(i).at(0), ans.at(i).at(K)); } return ans; } void solve() { ll N, X, Y, Z; cin >> N >> X >> Y >> Z; vector<ll> A = import_vector(N); vector<ll> B = import_vector(N); vector<vector<ll>> score = {}; for (ll i = 0; i < N; i++) { score.push_back({A.at(i), B.at(i), A.at(i) + B.at(i), i + 1}); } map<ll, bool> passed = {}; for (ll i = 1; i < N + 1; i++) { passed[i] = false; } vector<ll> ans = {}; score = key_sort(score, 3, false); score = key_sort(score, 0, true); for (vector<ll> el: score) { show(el); } ll L1 = score.size(); for (ll i = L1 - 1; i >= L1 - X; i--) { passed[score.at(i).at(3)] = true; ans.push_back(score.at(i).at(3)); } vector<vector<ll>> score2 = {}; for (ll i = 0; i < score.size(); i++) { if (passed[score.at(i).at(3)] == false) { score2.push_back(score.at(i)); } } score2 = key_sort(score2, 3, false); score2 = key_sort(score2, 1, true); ll L2 = score2.size(); for (ll i = L2 - 1; i >= L2 - Y; i--) { passed[score2.at(i).at(3)] = true; ans.push_back(score2.at(i).at(3)); } vector<vector<ll>> score3 = {}; for (ll i = 0; i < score2.size(); i++) { if (passed[score2.at(i).at(3)] == false) { score3.push_back(score2.at(i)); } } score3 = key_sort(score3, 3, false); score3 = key_sort(score3, 2, true); ll L3 = score3.size(); for (ll i = L3 - 1; i >= L3 - Z; i--) { ans.push_back(score3.at(i).at(3)); } sort(ans.begin(), ans.end()); for (ll el: ans) { cout << el << endl; } } int main() { solve(); }

以下のような質問にはリアクションをつけましょう

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

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

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

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

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

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

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

C++

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

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。