2026-10-29
adjacent_pass.cpp
#include <array>
#include <cstdio>
#include <tuple>
int main() {
std::array v{4, 6, 1, 5, 2, 3};
for (std::size_t i = 0; i + 1 < v.size(); ++i) {
for (std::size_t j = 0; j + 1 < v.size() - i; ++j) {
auto [x, y] = std::tie(v[j], v[j + 1]);
if (x > y) {
x = y;
}
}
}
for (int e : v) {
std::printf("%d", e);
}
std::printf("\n");
}
これは何を出力するでしょうか?
Answer
111223 です。
std::tie(v[j], v[j + 1]) が返すのは、2つの要素への参照を持つ std::tuple<int&, int&> です。auto [x, y] はこのタプルをコピーしますが、コピーされるのは参照なので、x と y はコピーした値ではなく v[j] と v[j + 1] そのものを指す名前になります。x = y は配列に書き込み、1回の比較は「v[j] を v[j] と v[j + 1] の小さい方にする」操作です。大きい方の値は右へ運ばれず、そのまま消えます。
この操作を15回追う代わりに、各要素が最後に何になるかを考えます。1回の走査で j は左から右へ進むので、v[j] を書き換えるとき、右隣の v[j + 1] はこの走査ではまだ書き換わっていません。走査のたびに v[j] は右へ1つ広い範囲の最小値になり、v[j] が触られる回数は、内側のループが j まで届く走査の数の 5 - j 回です。そのため最後の v[j] は v[j] から配列の右端までの最小値です。
4 6 1 5 2 3 の各位置から右端までの最小値は、左から1、1、1、2、2、3です。auto がタプルの中身の値をコピーすると読むと配列は変わらず 461523、バブルソートの形から並べ替えを思い浮かべると 123456 と答えてしまいます。