ABC203参戦記 - chacoderのブログ

f:id:chacoder:20210601124419p:plain
f:id:chacoder:20210601124458p:plain
f:id:chacoder:20210601131503p:plain

はじめに

2021年5月30日21:00-22:40に開催されたABC203に参戦しました。
結果は12:43　３完ノーペナで1595位／8432人中　パフォーマンス1213でレーティングは前回861から+41の902になりました。

はじめに
A問題
- 提出コード
B問題
D問題
E問題
- 記念提出
- 解説AC
終わりに

A問題

ちんちろりんとはなんとも昔懐かしいサイコロ賭博です。
３つのサイコロをふって２つが同じ目のとき残りの１つのサイコロの目が得点になるのが基本です。
「目」といいます。
バラバラだとクズといって０点ですね。
実際のルールはもう少し複雑で３つとも目が揃うとアラシ､１，２，３がでるとヒフミといって無条件の負け，４，５，６はシゴロといって無条件の勝ちで掛け金の２倍がもらえたりします。

素直に実装して丁寧にサンプルを試して2:13。まあまあ。

提出コード

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

signed main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a == b){
    cout<<c<<endl;
    return 0;
  }
  if(c == b){
    cout<<a<<endl;
    return 0;
  }
  if(a == c){
    cout<<b<<endl;
    return 0;
  }  
  cout<<0<<endl;
  return 0;
}

B問題

B - AtCoder Condominium

部屋番号を３桁の整数と見なして足し合わせる問題。
i,jが9までなので，素直に実装してよさそうです。
サンプル確認して提出。

2分14秒　通算4分27秒は快調。

提出コード

#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;
  int ans=0;
  rep(i,n) rep(j,k){
    ans+=(i+1)*100+j+1;
  }
  cout<<ans<<endl;
  return 0;
}

C問題

C - Friends and Travel costs

貪欲に手持ちのお金で次の村までたどり着けるか，たどり着けたらBiを手持ちのお金に足す，という方針でよさそうです。
最初に書いたコードは，村のソートを忘れており，入力例３が合わなくて気づきました。
親切なサンプルがあってよかった。
ソートを書き加えてAC。

8分16秒　通算12分43秒はまずまずです。
ノーペナで比較的スムーズに３完できたのが幸いで，エスティメーター見ると水パフォが出てました。
もっとも，このあたりまで好調でも後半にずるずる落ちてくのが常なので，気を引き締めて先に進みました。

提出コード

#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(){
  ll n,k;
  cin>>n>>k;
  vector<pair<ll,ll>> ab;
  ll a[n];
  ll b[n];
  rep(i,n){
    cin>>a[i]>>b[i];
    ab.push_back(make_pair(a[i],b[i]));
  }
  sort(ab.begin(),ab.end());
  ll ans=0;
  ans+=k;
  rep(i,n){
    if(ab.at(i).first<=ans){
      ans+=ab.at(i).second;
    }
    else break;
  }
  cout<<ans<<endl;
  return 0;
}

D問題

D - Pond

N×Nの区画中にとれるK×Kの区画のマスの中央値の最小値を求める問題です。
難しかったです。
愚直解は思いつきますが，Ｏ（N^4）でN==800だと到底間に合いません。
計算量落とす工夫も思いつかず15分ほど悩んで先に進みました。

E問題

E - White Pawn

チェスのポーンの動きをシミュレートして最下段の到達し得るマスの数を出力する問題です。
非常に幅の広いフィールドですが黒ポーンは高々２＊１０^５しかないので，黒ポーンのあるところだけ操作をすればよさそうです。
解法は思いついたのですが，実現するデーター構造を思いつかず，pairをつかったりvector>をつかったりしてあれこれやってみましたが詰まってしまい解ききれませんでした。

記念提出

雰囲気はでてますがダメダメです。

#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(){
  ll n,m;
  cin>>n>>m;
  vector<vector<int>> G(2*n+1);
  rep(i,m){
    ll x,y;
    cin>>x>>y;
    G[x].emplace_back(y);
  }
  sort(G.begin(),G.end());
  vector<ll>vec;  
  vec.push_back(n);
  int s=G.size();
  rep(i,s){
    //cout<<"#"<<vec.size()<<endl;
    vector<ll>nvec;  
    for(auto e:G){
      for(auto u:vec){
        if(count(e.begin(),e.end(),u)==0){
          nvec.push_back(u);
        }
        for(auto v:e){
          if(v==u-1){
            nvec.push_back(u-1);
          }
          if(v==u+1){
            nvec.push_back(u+1);
          }
        }
      }
    }
    vec=nvec;
  }
  cout<<vec.size()<<endl;
  return 0;
}

解説AC

昨晩解説を見て今朝解いてみました。
実装が軽くて冴える技が入っていていい問題です。
setの使い方やmapのsecondでvectorを扱う方法など応用のきく技を理解しました。
sをいじるタイミングで壊してしまわないようaddという配列を用意して更新するところもポイントですね。

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

int main(){
  int n,m;
  cin>>n>>m;
  map<int,vector<int>>mp;
  rep(i,m){
    int x,y;
    cin>>x>>y;
    mp[x].push_back(y);
  }
  set<int>s;
  s.insert(n);
  for(auto p:mp){
    vector<int>add;
    for(auto y:p.second){
      if(s.count(y-1)||s.count(y+1)){
        add.push_back(y);
      }
    }
    for(auto y:p.second) s.erase(y);
    for(auto y:add){
      s.insert(y);
    }
  }
  cout<<s.size()<<endl;
  return 0;
}