ABC188 - C

どうも、最近病みメイクのエモさを感じているもちよです。

一途ビッチちゃん【電子特典付き】 (コミックエッセイ)

ABC188のC問題で初めてpairを使った問題を自力ACしたので使い方の確認もこめてブログに残します。

問題自体は簡単ですが、解いた問題を正しく理解するための復習がすごく苦手なので練習するためにちょいちょいやろうと思います。

atcoder.jp

問題文

選手 $1$ から選手 $2^N$ までの $2^N$ 人の選手がトーナメント形式のプログラミング対決をします。
選手 $i$ のレートは $A_i$ です。どの $2$ 人の選手のレートも異なり、$2$ 人の選手が対戦すると常にレートが高い方が勝ちます。

トーナメント表は完全二分木の形をしています。
より正確には、このトーナメントは以下の要領で行われます。

• $i=1,2,3,\dots ,N$ について順に、以下のことが行われる。

  • 各整数 $j(1\le j\le 2^{N-i})$ について、まだ負けたことのない選手のうち、 $2j-1$ 番目に番号の小さい選手と $2j$ 番目に番号の小さい選手が対戦する。

準優勝する、すなわち最後に行われる対戦において負ける選手の番号を求めてください。

制約

• $1\le N\le 16$
• $1\le A_i\le {10}^9$
• $A_i$ は相異なる
• 入力に含まれる値は全て整数である

C++での解答

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. int main(){
5. int n;
6. cin>>n;
7. int z=1;
8. for(int i=0;i<n;i++){
9. z*=2;
10. }
11. vector<pair<long long int,int>> p(z/2),q(z/2);
12. for(int i=0;i<z/2;i++){
13. long long int x;
14. cin>>x;
15. p[i]=make_pair(x,i+1);
16. }
17. sort(p.begin(),p.end());
18. reverse(p.begin(),p.end());
19.  
20. for(int i=0;i<z/2;i++){
21. long long int y;
22. cin>>y;
23. q[i]=make_pair(y,i+1+z/2);
24. }
25. sort(q.begin(),q.end());
26. reverse(q.begin(),q.end());
27.  
28. if(p[0].first<q[0].first){
29. cout<<p[0].second<<endl;
30. }
31. else{
32. cout<<q[0].second<<endl;
33. }
34.  
35. return 0;
36. }

解答の流れとしては

1. 全選手の人数の把握
2. トーナメントの左の選手から番号が1,2,...,2^nなので、半分にあたる2^(n-1)人目で分割し、2グループに分ける
3. 選手番号とレートを結び付け、レートの大きさで各グループの最大レートの特定
4. 各グループの最大レートを比較し、レートが低いほうの選手番号を出力

でした。

自分的に3つ目の結び付けについて実装がおぼつかない状況でしたが、APG4bを見ながら頑張って書きました。

配列は1つの型しか入れることが出来ないと思っていましたが、pairと併用することで、数字と数字、数字と文字列といった2つの情報を入れられるっぽいです。

全然関係ないですが、逆順ソートしたのは配列の最後が2^(n-1)か、2^(n-1)-1かわからなかったので確実性を上げるためにです。

おわりだよ～(〇・▽・〇)