ABC216参戦記

はじめに

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

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

A問題

A - Signed Difficulty

最近は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問題

C - Many Balls

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

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

手慣れた実装で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問題

D - Pair of Balls

面白い問題です。愚直な実装はできましたがＯ（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;
}

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

Ｅ問題

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

E - Amusement Park

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

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

おわりに

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