ABC217参戦記
見出し画像

ABC217参戦記

はじめに

2021年9月4日21:00-22:40ABC217に参戦しました。結果は9分07秒ABCの3完で3831位/8543人中パフォーマン698でレーティングは前回922から-20の902になりました。

画像1

A問題

文字列S、Tの辞書順での大小を比較する問題。A問題らしい簡単な問題で一安心。

#include <bits/stdc++.h>
using namespace std;

int main(){
string s,t;
 cin>>s>>t;
 if(s<t) cout<<"Yes"<<endl;
 else cout<<"No"<<endl;
 return 0;
}

B問題

画像2

いろいろな実装が考えられますが手が動くままに素直に実装。これもわりといい感じでした。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int ans[4];

int main(){
 string s[4]={"ABC","ARC","AGC","AHC"};
 rep(i,3){
   string temp;
   cin>>temp;
   rep(j,4){
     if(temp==s[j]){
       ans[j]=1;
       break;
     }
   }
 }
 rep(i,4){
   if(ans[i]==0){
     cout<<s[i]<<endl;
     return 0;
   }
 } 
 return 0;
}


C問題

画像4

これも素直に実装。QのPi番目の要素がiであるをそのまま式にして ans[p[i]-1]=i+1; 

まぎれずに書けてよかったです。回答出力用の配列を用意するあたりはだいぶ慣れてきました。ここまで9分ほどでまあまあの速度でした。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
 int n;
 cin>>n;
 vector<int>p(n);
 rep(i,n) cin>>p[i];
 vector<int>ans(n);
 rep(i,n){
   ans[p[i]-1]=i+1;
 }
 rep(i,n){
   if(i != 0) cout<<" ";
   cout<<ans[i];
 }
 cout<<endl;
 return 0;
}

D問題

解けませんでした。TLEするかなと思いつつ素直な実装を書いたらRE。たしかに制約が10e9まであるのでメモリが足りるはずがありません。記念に貼っておきます。その後,さては座圧かと思っていろいろ試しましたが解ききれず。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
 int l,q;
 cin>>l>>q;
 vector<pair<int,int>>p(l+1,make_pair(0,l));
 //rep(k,l+1) cout<<k<<" "<<p[k].first<<" "<<p[k].second<<endl;
 rep(t,q){
   int temp,x;
   cin>>temp>>x;
   if(temp==1){
     //前へ
     for(int i=x-1;i>=p[x].first;i--){
       //cout<<i<<" "<<p[i].second<<"$"<<endl;
       p[i].second=x;
     } 
     //後ろへ
     for(int i=x+1;i<p[x].second;i++){
       //cout<<i<<" "<<p[i].first<<"#"<<endl;
       p[i]=make_pair(x,p[x].second);
     }
     //rep(k,l+1) cout<<k<<" "<<p[k].first<<" "<<p[k].second<<endl;       
   }
   if(temp==2) cout<<p[x].second-p[x].first<<endl;
 }
 return 0;
}

今日復習してデータ構造setを使うととてもシンプルに解けるのを学びました。setの二分探索とかとてもおしゃれです。

ちなみにイテレーターの一個手前の出力に悩みました。it--もit-1もうまくいかず、--itでACできました。このあたりまだ仕組みがよくわかっていません。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
 int l,q,temp,x;
 cin>>l>>q;
 set<int>s;
 s.insert(0);
 s.insert(l);
 rep(i,q){
   cin>>temp>>x;
   if(temp==1){
     s.insert(x);
   }
   if(temp==2){
     auto it=s.upper_bound(x);
     cout<<*(it)-*(--it)<<endl;
   }
 }
 return 0;
}

E問題

D問題が解けなかったのでトライしてみましたが手が出ませんでした。

queueとpriority_queueをうまく組み合わせて使うようなことを考えてみましたが詰まりました。記念提出だけ貼っておきます。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
 int q;
 cin>>q;
 queue<int>que;
 priority_queue<int>que2;
 int flag=1;
 rep(i,q){
   int temp;
   cin>>temp;
   if(temp==1){
     int x;
     cin>>x;
     que.push(x);
   }
   if(temp==2){
     cout<<que.front()<<endl;
     que.pop();
   }
   if(temp==3){
     int len=que.size();
     rep(i,len){
       int now=que.front();
       que.pop();
       que2.push(now);
     }
     rep(i,len){
       int now=que2.top();
       que2.pop();
       que.push(now);
     }
   }

 }
 return 0;
}

反省など

今回は冷えました。Dが解けなかったのが敗因ですが、データ構造についての知識がまだ不十分です。特にvectorやqueue、mapなど比較的得意なデータ構造がある反面、setなどの使い方にまだ慣れていません。setを二分探索するというのも新鮮でメンバ関数にupper_boundがあってlogNで走るのも勉強になりました。

冷える回ほど学ぶことが多いので、一回々々のコンテストの結果に一喜一憂せず、しっかり復習して次につなげていきたいと思います。

この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!
ありがとうございます!
noteでは野鳥と旅行の写真を中心に投稿します。