💬
Bit全探索 + 昇順と降順が混ざる際の対応 ABC 384 C - Perfect Standingsを理解し忘れないようにする
問題概要
ABCDEの空でない部分列を名前とする参加者が存在し、その参加者は名前に含まれる文字に対応する問題解いた。
参加者の名前を、取った点数が大きいほうから順に出力する。
ただし、同じ点数を獲得した参加者については、名前が辞書順で小さいほうを先に出力する。
基本設計
ABCDEの空でない部分列を名前とする参加者が存在し、その参加者は名前に含まれる文字に対応する問題解いた。
Bit全探索を用いてABCDE(00000~11111まで)のどれが使われているのかを判定し名前と点数を配列に格納
参加者の名前を、取った点数が大きいほうから順に出力する。
ただし、同じ点数を獲得した参加者については、名前が辞書順で小さいほうを先に出力する。
点数が大きい方を出力して降順に並べると、同じ点数だった場合に名前を降順に並べてしまう問題点がある。コンテスト中は比較関数を用いて解いたがやや複雑。
対応策として点数を全てマイナスにする。これによって同じ点数の場合に、名前も昇順で並べることができる。
提出コード
提出コード
// 省略
#define rrep(i, j, n) for (int i = j; i < n; i++)
#define all(x) (x).begin(), (x).end()
const double PI = acos(-1);
const int MI = 1e8;
const ll MLL = 1e18;
int main()
{
int n = 5;
vector<int> a(n);
rep(i,n) cin >> a[i];
vector<pair<int,string>> ranking;
rrep(bit,1,(1 << n)) {
string name;
int score = 0;
rep(i,n) {
if ((bit >> i) & 1) {
name += 'A' + i;
score += a[i];
}
}
ranking.emplace_back(-score,name);
}
sort(all(ranking));
for(auto r:ranking) {
cout << r.second << endl;
}
return 0;
}
Discussion