https://atcoder.jp/contests/abc222/tasks/abc222_c
解説
https://atcoder.jp/contests/abc222/submissions/26480601
シミュレーション問題、実装問題となる。
どういったことを問うているのかについては頑張って読み解いてほしい。
場合によってはサンプルを手計算でシミュレートすることも理解を助けるだろう。
問題を分割する
プログラミングにおいて一般的な話であるが、問題を小問題に分割することで
この問題に立ち向かうことにしよう。
各ラウンドでは
- 上位のユーザーから2人ずつグループにして戦わせる
- その後、これまでの勝敗を集計して、順位順に並びなおす
ということを行う。
問題の入力例1を使いながら理解を深めていくことにする。
あと、自分の実装と合わせるために、1 2 3 4ではなく0 1 2 3として説明していく。
1. 上位のユーザーから2人ずつグループにして戦わせる
順位を配列に入れておくことにしよう。自分はorderという名前で用意した。
最初の順位は0 1 2 3であり、これで上位2人ずつ戦わせていく。
勝敗は、どのラウンドかと、誰と誰の対戦であるかが分かれば決するので、それを引数としたbattle関数を用意した。
引き分けなら-1でそれ以外なら勝者を返す。
この中身は本当に根性実装なので、頑張って理解してほしい。
これで勝敗が分かれば勝者の勝ち点を+1すればいい。
win配列を用意して各人の勝ち数を記録しておくことにしよう。
2. その後、これまでの勝敗を集計して、順位順に並びなおす
どちらかというとこっちが問題である。
それほど厳しい制約でもないので、実装ができればTLEすることはなさそうだが、実装もちょっと大変かもしれない。
C++では、比較関数を自作したソートによって、これを簡単に実装することができる。
順位順に並びなおすというのと、特定のルール下におけるソート処理であると捉え、ルールを作る。
ルールは
- 勝敗が違っていれば勝ち点が多い方が先に来る
if (win[a] != win[b]) return win[a] > win[b]; - 勝敗が同じであれば、番号が小さい方が先に来る
else return a < b;
ということなので、これをソートの条件として指定する。
実装結果は↓にある通りなのだが、慣れないと少しパッと書くのは難しいかもしれない。
だが、このように特殊なソートをする場合にこれを使うことはよくあり、とても便利なのでこれを機に覚えるといい。
int N, M; string A[101]; int win[101]; //--------------------------------------------------------------------------------------------------- int battle(int round, int userA, int userB) { char a = A[userA][round]; char b = A[userB][round]; if (a == b) return -1; if (a == 'G' && b == 'C') return userA; if (a == 'C' && b == 'P') return userA; if (a == 'P' && b == 'G') return userA; return userB; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, N * 2) cin >> A[i]; vector<int> order; rep(i, 0, N * 2) order.push_back(i); rep(round, 0, M) { rep(k, 0, N) { int res = battle(round, order[k * 2], order[k * 2 + 1]); if (0 <= res) win[res]++; } sort(all(order), [&](int a, int b) { if (win[a] != win[b]) return win[a] > win[b]; else return a < b; }); } rep(i, 0, N * 2) printf("%d\n", order[i] + 1); }
