beet's soil

競プロのことなど

AtCoder Regular Contest 076

112th 2151 -> 2170 (+19) highest!!
5連続highest そろそろ大爆死しそう


無駄に長いのでライブラリは省略。
GitHub - beet-aizu/library: ライブラリ群


【C - Reconciled?】

abs(N-M)で場合分けするだけ。

signed main(){
  init(MOD);
  int n,m;
  cin>>n>>m;
  if(abs(n-m)>1){
    cout<<0<<endl;
    return 0;
  }
  int ans=(fact[n]*fact[m])%MOD;
  if(n==m) (ans*=2)%=MOD;
  cout<<ans<<endl;
  return 0;
}
【D - Built?】

min(|a−c|,|b−d|)をマンハッタン距離だと勘違いして無理!wと思った。
O(N^2)が間に合わないからエッジを減らすんだろうなあという気持ちになる。
なんかある点については一番近い点にだけ張ればいい気分になる。
なぜか本番中ではx軸とy軸の点を列挙してえいってやってしまった。

typedef pair<int,int> P;
typedef pair<int,P> PP;
bool used[314514];
signed main(){
  int n;
  cin>>n;
  vector<P> v(n),u(n);
  for(int i=0;i<n;i++) cin>>v[i].first>>v[i].second;
  for(int i=0;i<n;i++) u[i]=P(v[i].second,v[i].first);
  sort(v.begin(),v.end());
  sort(u.begin(),u.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  u.erase(unique(u.begin(),u.end()),u.end());
  //for(P p:v) cout<<p.first<<" "<<p.second<<endl;
  n=v.size();
  map<P,int> m;
  for(int i=0;i<n;i++) m[v[i]]=i;
  map<int,int> mx,my;
  int cx=0,cy=0;
  priority_queue<PP,vector<PP>,greater<PP> > q;
  for(int i=0;i<n;i++){
    if(!mx.count(v[i].first)) mx[v[i].first]=cx++;
    if(!my.count(u[i].first)) my[u[i].first]=cy++;
  }
  for(int i=0;i<n;i++){
    //cout<<mx[v[i].first]<<" "<<my[v[i].second]<<endl;
    q.push(PP(0,P(i,n+mx[v[i].first])));
    q.push(PP(0,P(i,n+cx+my[v[i].second])));
  }
  for(int i=0;i<n-1;i++){
    if(v[i].first==v[i+1].first) continue;
    q.push(PP(abs(v[i].first-v[i+1].first),
	      P(n+mx[v[i].first],n+mx[v[i+1].first])));
  }
  for(int i=0;i<n-1;i++){
    if(u[i].first==u[i+1].first) continue;
    q.push(PP(abs(u[i].first-u[i+1].first),
	      P(n+cx+my[u[i].first],n+cx+my[u[i+1].first])));
  }
  //cout<<n<<" "<<cx<<" "<<cy<<endl;
  int ans=0;
  UnionFind uf(n+cx+cy);
  while(!q.empty()){
    PP pp=q.top();q.pop();
    P p=pp.second;
    int d=pp.first,s=p.first,t=p.second;
    //cout<<d<<" "<<s<<" "<<t<<endl;
    if(uf.same(s,t)) continue;
    //cout<<d<<" "<<s<<" "<<t<<endl;
    ans+=d;
    uf.unite(s,t);
  }
  cout<<ans<<endl;
  return 0;
}
【E - Connected?】

少し考えると片方でも壁から離れていれば無視できることがわかる。
両方壁についていて交差しているやつがある<=>NO になる。
解法がわかってから実装終わるまで時間がかかった。

signed main(){
  cin>>r>>c>>n;
  vector<P> v;
  for(int i=0;i<n;i++){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    //cout<<in(x1,y1)<<" "<<in(x2,y2)<<endl;
    if(in(x1,y1)||in(x2,y2)) continue;
    //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
    //cout<<po(x1,y1)<<" "<<po(x2,y2)<<endl;
    P p(po(x1,y1),po(x2,y2));
    if(p.first>p.second) swap(p.first,p.second);
    v.push_back(p);
    /*
      v.push_back(P(p.first+2*(r+c),p.second+2*(r+c)));
      swap(p.first,p.second);
      p.second+=2*(r+c);
      v.push_back(p);
      v.push_back(P(p.first+2*(r+c),p.second+2*(r+c)));
    */
  }
  //sort(v.begin(),v.end());
  n=v.size();
  vector<int> comp;
  for(int i=0;i<n;i++){
    comp.push_back(v[i].first);
    comp.push_back(v[i].second);
  }
  sort(comp.begin(),comp.end());
  comp.erase(unique(comp.begin(),comp.end()),comp.end());
  int sz=comp.size();
  //for(int i=0;i<sz;i++) cout<<i<<" "<<comp[i]<<endl;
  map<int,int> m;
  for(int i=0;i<sz;i++) m[comp[i]]=i;
  RMQ rmq(sz);
  for(int i=0;i<n;i++){
    
    rmq.update(m[v[i].first],m[v[i].second]);
  }
  bool ans=1;
  for(int i=0;i<n;i++){
    //cout<<v[i].first<<" "<<v[i].second<<endl;
    //cout<<m[v[i].first]<<"m"<<m[v[i].second]<<endl;
    //cout<<rmq.query(m[v[i].first],m[v[i].second])<<":"<<m[v[i].second]<<endl;
    ans&=(rmq.query(m[v[i].first],m[v[i].second])<=m[v[i].second]);
  }
  cout<<(ans?"YES":"NO")<<endl;
  return 0;
}


橙、遠いなあ…