std::setの使い方
問題
AGC 022 A問題。
解法のポイントとsetの使いどころ
文字数が26文字のとき、後ろから見て最長の昇順文字列(接尾文字列)を取得し、最長の昇順文字列の1つ手前の文字より大きい中で接尾文字列に含まれる一番小さな文字を最後に付け足したい。
ここでsetが役に立つ。
コメント付きメモ。
set<char> g; while (s.size()) { char c = s.back(); s.pop_back(); auto it = g.upper_bound(c); // cが詰めてきた文字より大きな文字の場合、it == g.end() => trueとなる if (it != g.end()) { // it: cより大きい中で一番小さな文字 s += *it; cout << s << '\n'; return 0; } g.insert(c); } cout << -1 << "\n";
提出
Submission #16563738 - AtCoder Grand Contest 022