ABC212参戦記

atcoder.jp

はじめに

7月31日21:00-22:40ABC212に参戦しました。
結果は81:59 ABCD4完2425位/7893人中でパフォーマンス934レーティングは前回875から+6の881となりました。
ABC8問制の初回で難易度傾斜が弱くなるとの触れ込みでしたがE以降はとても難しく難問が増えただけのような印象でした。
もっともDまででも楽しいセットだったと思います。

A問題

金と銀の量が示され混ぜ合わせたものが純金か純銀か合金かを判別する問題です。

B問題

B - Weak Password

数字4桁のパスワードの強度を判別する問題。
４つとも同じ数字か順番に１づつ大きくなる（9の次は0）場合に弱いパスワードになります。
stringで入力して処理。

提出コード

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

signed main(){
  string s;
  cin>>s;
  if(s[0]==s[1] && s[1]==s[2] && s[2]==s[3]){
    cout<<"Weak"<<endl;
    return 0;
  }
  if((s[1]==s[0]+1 ||(s[1]=='0' && s[0]=='9'))&&
     (s[2]==s[1]+1 ||(s[2]=='0' && s[1]=='9'))&&
     (s[3]==s[2]+1 ||(s[3]=='0' && s[2]=='9'))){
    cout<<"Weak"<<endl;
    return 0;
  }
  cout<<"Strong"<<endl;
  return 0;
}

Ｃ問題

C - Min Difference
数列Aと数列Bから要素を１こづつ選んだときの差の最小値を求める問題です。
片方ソートしておいて二分探索が頭をよぎりましたが尺取りみたいなやり方の方がまぎれが少なそうです。
両方ソートしておいて，インデックスを動かしながら差の最小値を求めました。

提出コード

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

signed main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(n,0);
  vector<int> b(m,0);
  rep(i,n) cin>>a[i];
  rep(i,m) cin>>b[i];
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  int aind=0;
  int bind=0;
  int mindif=1000000000;  
  while(aind<n && bind<m){
    int dif=abs(a[aind]-b[bind]);
    mindif=min(mindif,dif);
    if(aind==n-1) bind++;
    else if(bind==m-1) aind++;
    else if(abs(a[aind+1]-b[bind])>=abs(a[aind]-b[bind+1])){
      bind++;
    }
    else{
      aind++;
    }
  }
  cout<<mindif<<endl;
  return 0;
}

Ｄ問題

D - Querying Multiset
①要素の追加、②集合全部に加算、③最小の値を出力して削除、という３つのクエリ―を処理する問題です。
ヒープ（priority_queue)を使った実装をすぐ思いつき、②について要素とは別に累積の加算量を準備し③の出力の際に足す工夫をしました。ところがサンプルは通りましたが提出するとWAです。
途中で追加された要素について、②の値がずれてくるのが問題だと気づきましたが、なかなか解決策を思いつきませんでした。血迷って愚直解を書いてみましたが当然ながらＴＬＥ。自作のサンプルを書き出していろいろいじっているうちに、要素を追加する際にそこまでの累積の加算量を引いてやればよい、と気づいて「解けた！」となりました。提出コードはめちゃめちゃシンプルです。

提出コード

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

signed main(){
  int q;
  cin>>q;
  priority_queue<int, vector<int>, greater<int> > que;
  int base=0;
  while(q--){
    int t,x;
    cin>>t;
    if(t != 3) cin>>x;
    if(t==1) que.push(x-base);
    if(t==2) base+=x;
    if(t==3){
      cout<<que.top()+base<<endl;
      que.pop();
    }
  }
  return 0;
}

親子競プロ結果

今回も負けました。Dで同じ間違いをしてましたがリカバリーが早い。
Eをしっかり考察して通していて着実に力をつけてるなと思いました。