ABC217参戦記

はじめに

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

Ａ問題

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

#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;
}

Ｂ問題

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

#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;
}

Ｃ問題

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

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

#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;
}

Ｄ問題

解けませんでした。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;
}

Ｅ問題

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で走るのも勉強になりました。

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