2021-02-01

ABC188 - C

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

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

作者:色のん
発売日: 2020/05/28
メディア: Kindle版

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

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

atcoder.jp

問題文

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

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

$i = 1, 2, 3, \dots, N$ について順に、以下のことが行われる。
- 各整数 $j (1 \leq j \leq 2^{N - i})$ について、まだ負けたことのない選手のうち、 $2 j - 1$ 番目に番号の小さい選手と $2 j$ 番目に番号の小さい選手が対戦する。

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

制約

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

C++での解答

#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int z=1;
for(int i=0;i<n;i++){
z*=2;
}
vector<pair<long long int,int>> p(z/2),q(z/2);
for(int i=0;i<z/2;i++){
long long int x;
cin>>x;
p[i]=make_pair(x,i+1);
}
sort(p.begin(),p.end());
reverse(p.begin(),p.end());
for(int i=0;i<z/2;i++){
long long int y;
cin>>y;
q[i]=make_pair(y,i+1+z/2);
}
sort(q.begin(),q.end());
reverse(q.begin(),q.end());
if(p[0].first<q[0].first){
cout<<p[0].second<<endl;
}
else{
cout<<q[0].second<<endl;
}
return 0;
}

解答の流れとしては

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

でした。

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

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

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

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

2020-12-11

【Boushitsu Advent Calendar 2020】春は尊しラーメン食べし

初めましての方は初めまして。ドラクエ9ではパラディンが大好きだった麻倉もちょりーぬです。

ドラゴンクエストIX 星空の守り人

発売日: 2009/07/11
メディア: Video Game

新型コロナウイルスに引っ掻き回された2020年、どうだったでしょうか。

私自身にとってこの1年は人生で一番てんやわんやしていたと思います。

年が始まるや否や塾講しながら大学受験をし、運よく合格できました。そして引っ越したかと思えば対面形式での授業もまともに受けられない状態で、大学生なのに昨年とやってること大して変わらないじゃん状態に。

騒ぎが少し落ち着いたころで、以前と全く違う職種のバイトを始めました。右も左もわからずに何度も上司やバイトの先輩に注意されました。*1

長い夏休みには旅行にも出かけました。初めて行く名古屋、大阪、神戸はとてもわくわくしてたまりませんでした。久しぶりに会う方、なんだかんだ初めて会う方、浜松で一緒にさわやかを食べた3日後に神戸で再び会った方*2、ありがとうございました。帰省からのUターンでは渋谷のポムの樹でもちょサー出来ましたね。なかなか会えないからこそのチャンスをものにできてすごく嬉しかったです。

授業が再開すると友人の誘いで新しい出会いにも恵まれました。恋愛ではありませんが*3。ぼっちには大変うれしい限りでございます。

１年生ももうすぐ終盤に差し掛かっていますが、課題が日に日に重くなってきてすぐにでも潰されそうです。助けてください。

書いていて疲れたので最近のおすすめイラストを貼り付けます。