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

2021年11月21日 11:24

はじめに

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

Ａ問題

ここのところＡ問題から骨のある問題が出ることが多い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;
}

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

Ｂ問題

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

いろいろな解法が考えられましたが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;
}

Ｃ問題

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

３日目までの合計点を求め、４日目に対象者は満点、その他の参加者は０点として対象者がK位以内に入っているかを判定します。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;
}

Ｄ問題

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

愚直にやるとО（Q＊N）で間に合いませんので、参照するポジションを保持する配列を準備する方針を立てましたが、時間中では絡まってしまって解ききれませんでした。最初に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;
}

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

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

Ｅ問題

（N^K）^Mを求める問題です。

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

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

おわりに

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

この記事が気に入ったらサポートをしてみませんか？