Sat Aug 29 21:19:48 JST 2015

C++ STL unique uniq

問題

C: 数を3つ選ぶマン - AtCoder Beginner Contest 028 | AtCoder

解法

ありうる和が \(5 \times 4 \times 3\) 通りなので、それを全部列挙

vector<int> xs(5); cin >> xs;
vector<int> s;
rep (i, 5) rep (j, i) rep (k, j) s.push_back(xs[i] + xs[j] + xs[k]);

ソートして、重複を取り除いて、3番目を実際に出力する.

初め、下のようにした.
std::unique というものの存在が知らなかったので、軽くググった.
sort してから使うもののようなので (Unix の uniq コマンドと同じだ):

sort(begin(xs), end(xs));
unique(begin(xs), end(xs));
reverse(begin(xs), end(xs));
cout << xs[2] << endl;

なんかバグった (Submission #479383).

というわけで、もうちょっと詳しく調べることにする. (軽く調べる、とは、ググった検索結果ページを見ることであって、さらに該当のページを読むことではない).

「末尾にゴミが残る」状態から reverse したのだから、 ゴミを見て回答してたことになる.

そのページにあるように、erase したところ正答 (Submission #479557)

しかしならば、reverse してから unique すればよかったわけだ (check Submission #480275).

追記

よく考えると、入力は相異なる5つであったので、 和を重複せずに求めてれば、unique とか要らなかった.

あと、全列挙するまでもなく、三番目の和は高々二通りだった:

\(A<B<C<D<E\)について

Bash

sed 's/.*/&\n&/' |
awk 'NR==1{print $2+$3+$5} NR==2{print $1+$4+$5}' |
sort -n | tail -1