ABC228(トヨタシステムコンテスト2021)参戦記
見出し画像

ABC228(トヨタシステムコンテスト2021)参戦記

Chacoder


はじめに

画像1

11月20日21:00-22:40に開催されたABC228(トヨタシステムコンテスト2021)に参戦しました。結果は40分16秒ABC3完ノーペナで2694位/6298人中、パフォーマンス782でレーティングは前回863から-8の855となりました。


A問題

ここのところA問題から骨のある問題が出ることが多いABCですが、今回も気を付けないとペナルティを出しそうな問題でした。慎重に場合分けを検討して8:02で提出。無事にACしました。

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

signed main(){
 int s,t,x;
 cin>>s>>t>>x;
 if(s<t && s<=x && x<t){
   cout<<"Yes"<<endl;
   return 0;
 }
 if(s>t && (x>=s||x<t)){
   cout<<"Yes"<<endl;
   return 0;
 }
 cout<<"No"<<endl;
 
 return 0;
}

順位表みるとさすがにトップ勢はこの手の問題でもめったにペナルティを出しません。他方、中下位勢はA問題としては高い割合でペナルティを出しており、競プロは総合力だなということを改めて感じさせます。

B問題

参加者(提出者)の9割近く、5260人も解いてますが、ちょっと前ならC問題かD問題あたりにいてもおかしくない問題です。参加登録者は8000人を超えているので、A問題、B問題あたりを眺めて提出せずに撤退した人も多かったのではないかと想像します。

いろいろな解法が考えられましたがBFSで解くのが素直かなと思いました。

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

signed main(){
 int n,x;
 cin>>n>>x;
 x--;
 kn[x]=1;
 vector<int>vec[n];
 rep(i,n){
   int s;
   cin>>s;
   s--;
   vec[i].push_back(s);
 }
 queue<int>que;
 que.push(x);
 while(que.size() != 0){
   int temp=que.front();
   que.pop();
   for(auto e:vec[temp]){
     if(kn[e]==1) continue;
     kn[e]=1;
     que.push(e);
   }
 }
 int cnt=0;
 rep(i,n){
   if(kn[i]==1){
     cnt++;
   }
 }
 cout<<cnt<<endl;
 return 0;
}

C問題

4日間のテストで3日目を終えており、4日目の結果により上位K位以内に入れる可能性があるかどうかを判定します。

3日目までの合計点を求め、4日目に対象者は満点、その他の参加者は0点として対象者がK位以内に入っているかを判定します。n<=10^5なのでО(n^2)は間に合いませんが二分探索を使えばО(n log n)で間に合います。

二分探索にソートが必要なためqという配列を用意しコピーした上でソートして使いました。問題文の定義から探索したいkeyより大きいイテレータを返すupper_boundを使います。

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

signed main(){
 int n,k;
 cin>>n>>k;
 vector<int>p(n),q(n);
 rep(i,n){
   int d1,d2,d3;
   cin>>d1>>d2>>d3;
   p[i]+=(d1+d2+d3);
 }
 q=p;
 sort(q.begin(),q.end());
 rep(i,n){
   if(n-(upper_bound(q.begin(),q.end(),p[i]+300)-q.begin())+1<=k){
     cout<<"Yes"<<endl;
   }
   else{
     cout<<"No"<<endl;
   }
 }
 return 0;
}

D問題

ちょっと読みにくい問題でしたが問題自体はシンプルです。

愚直にやるとО(Q*N)で間に合いませんので、参照するポジションを保持する配列を準備する方針を立てましたが、時間中では絡まってしまって解ききれませんでした。最初にWAを叩いて少し悩んだあと、ちらっとE問題を見て解けそうな気がして飛ばしたのが立ち回りのミスで、落ち着いてD問題を解ききる方針の方がよかったかも知れません。

時間中にWAしたコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
#define int long long
static const int mod=1048576;
int p[1048576];
int a[1048576];

signed main(){
 int q;
 cin>>q;
 rep(i,1048576){
   p[i]=i;
   a[i]=-1;
 } 
 rep(iq,q){
   int t,x;
   cin>>t>>x;
   if(t==1){
     int h=x;
     a[p[h%mod]]=x;
     int cnt=0;
     while(1){
       if(a[h%mod+cnt]!=-1){
         cnt++;
         continue;
       }
       p[h%mod]=p[(h%mod+cnt)%mod];
       break;
     }
   }
   if(t==2){
     cout<<a[x%mod]<<endl;
   }
 }
 return 0;
}

落ち着いて解きなおしてACしたコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
#define int long long
static const int mod=1048576;
int p[2000000];
int a[2000000];

signed main(){
 int q;
 cin>>q;
 rep(i,mod) a[i]=-1;
 rep(iq,q){
   int t,x;
   cin>>t>>x;
   if(t==1){
     int h=x;
     int pos=x%mod;
     if(a[pos]==-1){
       a[pos]=x;
     }
     else{
       if(p[pos]!=0) pos=p[pos];
       while(a[pos] != -1){
         pos++;
         pos%=mod;
       }
       a[pos]=x;
       p[x%mod]=pos;
     }
   }
   if(t==2){
     int pos=x%mod;
     cout<<a[pos]<<endl;
   }
 }
 return 0;
}

E問題

(N^K)^Mを求める問題です。

単純に高速累乗だけで解けるならEにいるはずはないのですが、ちらっと見て簡単そうに見えて手を出して延々とWAを出して沈みました。

画像2

解説を見てフェルマーの小定理を使う方法を学びましたが自力で書けるまでにはまだ少し距離があります。

おわりに

なかなかレートには反映されてきませんが、毎回コンテストに出るたびに新しいことを学び、経験を獲得している実感はあります。知識を整理する時間がとれていないので、そのあたりは意識していきたいと思います。

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