beet's soil

競プロのことなど

AtCoder Regular Contest 069

☀️した後に出た

【C - Scc Puzzle】

貪欲で解くの怖すぎたので二分探索した。
できるかできないかはO(1)で判定できて、
k個作れるならk-1個も当然作れるよねみたいな。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m;
  cin>>n>>m;
  ll l=0,r=n+m;
  while(l+1<r){
    ll mid=(l+r)/2;
    if(mid<=n){
      if(mid*2<=m) l=mid;
      else r=mid;
      continue;
    }
    ll t=mid-n;
    if((mid+t)*2<=m) l=mid;
    else r=mid;
  }
  cout<<l<<endl;
  return 0;
}
【D - Menagerie】

思考停止SCCしようとしてあーよくあるやつってなった。
自分と片方の隣が確定すればもう片方も決まるので、
0番目と1番目を4パターン決め打ちすればいい。
頭がなかったので判定パートが冗長(ア。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  string s;
  cin>>n>>s;
  int dp[n];
  for(int x=0;x<2;x++){
    dp[0]=x;
    for(int y=0;y<2;y++){
      dp[1]=y;
      for(int i=1;i<n-1;i++){
	if(s[i]=='o'){
	  if(dp[i]) dp[i+1]=dp[i-1];
	  else dp[i+1]=!dp[i-1];
	}else{
	  if(dp[i]) dp[i+1]=!dp[i-1];
	  else dp[i+1]=dp[i-1];
	}
      }
      bool f=1;
      for(int i=1;i<n+1;i++){
	if(s[i%n]=='o'){
	  if(dp[i%n]) f&=dp[(i+1)%n]==dp[(i-1)%n];
	  else f&=dp[(i+1)%n]!=dp[(i-1)%n];
	}else{
	  if(dp[i%n]) f&=dp[(i+1)%n]!=dp[(i-1)%n];
	  else f&=dp[(i+1)%n]==dp[(i-1)%n];
	}
      }
      if(f){
	for(int i=0;i<n;i++) cout<<(dp[i]?'S':'W');
	cout<<endl;
	return 0;
      }
    }
  }
  cout<<-1<<endl;
  return 0;
}
【E - Frequency】

背が高いやつを後ろから取っていくのが辞書順最小になるのは割とすぐわかった。
それぞれのaiについて区間加算と値取得ができれば解ける。
座圧して遅延セグ木でできるやんってなったけど
2
3 1
みたいので落ちて区間更新も必要なことに気づいてRUPセグ木を足した。
構造体にしてなかったので色々バグって時間を溶かしてしまった。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX=1<<18;
const int MAX_N=1<<18;
typedef pair<int,int> P;
int n,dat[2*MAX-1],laz[2*MAX-1];
P datp[2*MAX_N-1];
int query(int k){
  k+=n-1;
  P p=datp[k];
  while(k>0){
    k=(k-1)/2;
    p=min(p,datp[k]);
  }
  return p.second;
}
void update(int a,int b,P p,int k=0,int l=0,int r=n){
  if(r<=a||b<=l) return;
  if(a<=l&&r<=b) {
    datp[k]=min(p,datp[k]);
  }else{
    update(a,b,p,k*2+1,l,(l+r)/2);
    update(a,b,p,k*2+2,(l+r)/2,r);
  }
}
void init(int n_){
  n=1;
  while(n<n_) n*=2;
  for(int i=0;i<2*n-1;i++) dat[i]=laz[i]=0;
  for(int i=0;i<2*n-1;i++) datp[i].first=INT_MAX,datp[i].second=INT_MAX;
}
inline void eval(int len,int k){
  if(k*2+1<n*2-1){
    laz[k*2+1]+=laz[k];
    laz[k*2+2]+=laz[k];
  }
  dat[k]+=laz[k]*len;
  laz[k]=0;
}
int update(int a,int b,int x,int k=0,int l=0,int r=n){
  eval(r-l,k);
  if(r<=a||b<=l) return dat[k]+laz[k]*(r-l);
  if(a<=l&&r<=b) return dat[k]+(laz[k]+=x)*(r-l);
  eval(r-l,k);
  return dat[k]=update(a,b,x,k*2+1,l,(l+r)/2)+update(a,b,x,k*2+2,(l+r)/2,r);
}
int query(int a,int b,int k=0,int l=0,int r=n){
  eval(r-l,k);
  if(r<=a||b<=l) return 0;
  if(a<=l&&r<=b) return dat[k];
  int vl=query(a,b,k*2+1,l,(l+r)/2);
  int vr=query(a,b,k*2+2,(l+r)/2,r);
  return vl+vr;
}

signed main(){
  int N;
  cin>>N;
  int a[N];
  for(int i=0;i<N;i++) cin>>a[i];
  vector<int> v(N);
  for(int i=0;i<N;i++) v[i]=a[i];
  v.push_back(0);
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  int M=v.size();
  init(M);
  map<int,int> m;
  for(int i=0;i<M;i++) m[v[i]]=i;
  for(int i=0;i<N;i++){
    //cout<<i<<":"<<m[a[i]]+1<<endl;
    update(0,m[a[i]]+1,P(i,i));
    update(0,m[a[i]]+1,1);
  }
  int o[N];
  memset(o,0,sizeof(o));
  for(int i=M-1;i>0;i--){
    //cout<<i<<" "<<query(i)<<endl;
    o[query(i)]+=(v[i]-v[i-1])*query(i,i+1);
  }
  for(int i=0;i<N;i++) cout<<o[i]<<endl;
}
【全体】

ooox 121st
1899 -> 1935 (+36) highest
Eはライブラリをちゃんと整備してればもっと速く解けたなあと言う気持ちになった。
遅延セグ木を教えてくれたうくさんに圧倒的感謝👊