ABC216参戦記
見出し画像

ABC216参戦記


画像2

はじめに

2021年8月29日21:00-22:40に開催されたABC216に参戦しました。

結果は96:09 ABCEの4完で1777th/7377人中,パフォーマンスは1122でレーティングは前回898から+24の922となりました。

A問題


最近はA問題から骨のある問題であることが多いと思います。見るからに誤差が怖そうな見かけなので文字列で受けて数字に変換して丁寧に判定する実装にしました。7:29はA問題としてはかけ過ぎか。なお、作問者のツイートによるとdoubleとかで受けても誤差は生じなかった模様です。

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

int main(){
 string s;
 cin>>s;
 int x,y;
 int len=s.size();
 if(len==4){
   x=(s[0]-'0')*10+(s[1]-'0');
 }
 else{
   x=(s[0]-'0');
 }
 if(len==4){
   y=(s[3]-'0');
 }
 else{
   y=(s[2]-'0');
 }
 //cout<<x<<" "<<y<<endl;
 if(0<=y && y<=2){
   cout<<x<<"-"<<endl;
 }
 else if(3<=y && y<=6){
   cout<<x<<endl;
 }
 else if(7<=y && y<=9){
   cout<<x<<"+"<<endl;
 }
 return 0;
}


B問題


N人の姓名が与えられるので同姓同名の人が存在するかどうかを判定する問題です。制約は2<=N<=1000と小さめ。

これもmapを使いこなせないころには解けなかったかもしれない問題です。B問題としてはそこそこ難しめに感じました。mapが使えればpair<string.string>を突っ込んで重複を見るだけでわりと簡単です。

4分33秒 通算12分秒

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<string,string> PS;
int main(){
 map<PS,int>mp;
 int n;
 cin>>n;
 rep(i,n){
   string s,t;
   cin>>s>>t;
   mp[make_pair(s,t)]++;
 }
 for(auto e:mp){
   if(e.second>=2){
     cout<<"Yes"<<endl;
     return 0;
   }
 }
 cout<<"No"<<endl;
 return 0;
}

C問題

空の箱に魔法A(箱の中のボールを1つ増やす)か魔法B(箱の中のボールを2倍にする)かのいずれかの魔法をかけてちょうどN個にする方法を示します。1<=N<=1e18と制約は大きめ。

よく見るタイプの問題で2進数変換する要領で実装。わりと簡単目でした。

手慣れた実装で6分26秒通算18分28秒。Aに手間取ったせいか、提出時点で予想パフォ700台でもうひとがんばりが必要です。

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

int main(){
 ll n;
 cin>>n;
 string s="";
 while(n != 1){
   if(n%2==1){
     n--;
     s+="A";
   }
   else{
     n/=2;
     s+="B";
   }
 }
 reverse(s.begin(),s.end());
 cout<<"A"<<s<<endl;
 return 0;
}

D問題

面白い問題です。愚直な実装はできましたがO(MN)より短くできずTLEを連発。諦めてE問題へ。

TLEした愚直実装だけ記念に貼っておきます

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

int main(){
 int n,m;
 cin>>n>>m;
 vector<queue<int>> vec(m);
 rep(i,m){
   int k;
   cin>>k;
   rep(j,k){
     int temp;
     cin>>temp;
     vec[i].push(temp);
   }
 }
 int flag=1;
 while(flag){
   flag=0;
   map<int,int>mp;
   rep(i,m){
     if(!vec[i].empty()){
       mp[vec[i].front()]++;
     }
   }
   vector<int>sa;
   for(auto e:mp){
     if(e.second==2){
       flag=1;
       sa.push_back(e.first);
     }
   }
   rep(i,m){
     for(auto e:sa){
       if(vec[i].front()==e){
         vec[i].pop();
       }
     }
   } 
 }
 rep(i,m){
   if(!vec[i].empty()){
     cout<<"No"<<endl;
     return 0;
   }
 }
 cout<<"Yes"<<endl;
 return 0;
}

解説にO(N+M)に落とす解法がありましたが,まだ理解できていません。後日復習予定です。

E問題

D問題を諦め、E問題に挑みます。なんか愚直にやって解けそうです!

ソートして大きな方から順に愚直にやっていく、和の公式の応用で計算速度をあげる、という方針でやってたらACできました!久しぶりにEが解けて,さすがに暖まりそうです。

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

int main(){
 int n;
 ll k;
 cin>>n>>k;
 vector<ll> a(n);
 rep(i,n) cin>>a[i];
 sort(a.rbegin(),a.rend());
 //rep(i,n) cout<<a[i]<<" ";
 ll sum=0;
 ll cur=0;
 while(k>0 && cur<n){
   //cout<<sum<<endl;
   ll kaisu=min((a[cur]-a[cur+1])*(cur+1),k);    
   sum+=(a[cur]+a[cur]-kaisu/(cur+1)+1)*(cur+1)*(kaisu/(cur+1))/2;
   sum+=(a[cur]-kaisu/(cur+1))*(kaisu%(cur+1));
   k-=kaisu;
   cur++;
 }
 cout<<sum<<endl;
 return 0;
}

おわりに

久しぶりにE問題まで解けましたがレーティング1200以上の水パフォにはもう一歩。水色を目指すにはコンスタントに水以上がとれないとだめなので,もうひとがんばりが必要です。ただ,ここのところ少しづつですが前に進んでいる実感があるので(広義単調増加ストリーク6)焦らず引き続き一歩々々がんばっていこうと思います。

画像3





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