2026-08-30
unique_sort.cpp
bool same_for_any_sort(std::vector<std::pair<int, char>> v) {
}
v を、要素の first だけを比べて昇順に並べ替えるとします。安定かどうかを問わず、正しく並べ替えるどのアルゴリズムを使っても、並べ替えたあとの列(要素の first と second の並び)が必ず同じになるなら true、アルゴリズムによって違う列になりうるなら false を返す same_for_any_sort を書いてください。v が空なら true です。
入力例 1
same_for_any_sort({{2, 'a'}, {1, 'b'}, {2, 'a'}})
出力例 1
true
入力例 2
same_for_any_sort({{2, 'a'}, {1, 'b'}, {2, 'c'}})
出力例 2
false
入力例 3
same_for_any_sort({})
出力例 3
true
Reference
Reference
bool same_for_any_sort(std::vector<std::pair<int, char>> v) {
std::ranges::sort(v);
return std::ranges::adjacent_find(v, [](const auto& a, const auto& b) {
return a.first == b.first && a.second != b.second;
}) == v.end();
}
アルゴリズムを1つずつ思い浮かべて結果を比べる必要はありません。見るべきなのは、正しく並べ替えたあとの列のうち、どこまでがアルゴリズムによらずに決まるかです。first が違う2つの要素は、どのアルゴリズムでも first の小さいほうが前に来ます。アルゴリズムが自由に決められるのは、first が同じ要素どうしの並び順だけで、安定な並べ替えは元の順に、不安定な並べ替えは何らかの順に置きます。どの並び順も、それを出力する正しいアルゴリズムが作れるので、first が同じ要素の組の中で並び順を入れ替えたときに列が変わるかどうかが答えを決めます。
first が同じ要素の組の中で入れ替えても列が変わらないのは、組の要素がすべて同じ値のときだけです。入力例 1 では first が 2 の要素が2つありますが、どちらも {2, 'a'} なので、どちらを先に置いても列は 1b 2a 2a で、true になります。入力例 2 では {2, 'a'} と {2, 'c'} の順で列が変わるので false です。「first に重複が無ければ true」と判定すると、入力例 1 で間違えます。
参考実装は、この条件を、v の写しをペア全体で並べ替えてから確かめています。first と second の両方で並べると、first が同じ要素は隣り合い、その中は second の順に並びます。組の中に違う second が2つ以上あれば、どこかで隣どうしの second が食い違うので、adjacent_find がその位置を見つけて false を返します。空の列や要素が1つの列では隣り合う組が無く、adjacent_find は v.end() を返すので true です。掲載したのは参考実装で、唯一の正解ではありません。std::map<int, char> に first ごとの最初の second を覚えておき、違う second が来たら false を返す書き方でもかまいません。