beet's soil

競プロのことなど

AtCoder Regular Contest 075

109th 2081 -> 2106 (+25) highest!!
3連続highest更新はうれしいぞい

【C - Bugged】

むずかしい。
総和が10で割り切れないならそれが一番で、割り切れるなら割り切れない中で最小のものを引く。
O(N).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int s[n];
  for(int i=0;i<n;i++) cin>>s[i];
  int x=100000;
  int sum=0;
  for(int i=0;i<n;i++) sum+=s[i];
  for(int i=0;i<n;i++){
    if(s[i]%10) x=min(x,s[i]);
  }
  if(sum%10){
    cout<<sum<<endl;
    return 0;
  }
  if(x==100000) cout<<0<<endl;
  else cout<<sum-x<<endl;
  return 0;
}
【D - Widespread】

こういうのすこ。x回攻撃して倒せるならx+1回攻撃しても倒せる感じがするので二分探索。
x回で倒せるかどうかはbxの全体攻撃の後に(a-b)の単体攻撃を何回かすると考えればO(N)でできる。
O(Nlogh).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,a,b;
  cin>>n>>a>>b;
  int h[n];
  for(int i=0;i<n;i++) cin>>h[i];
  int l=0,r=11111111111;
  while(l+1<r){
    int m=(l+r)/2;
    int t[n];
    int x=m;
    for(int i=0;i<n;i++){
      t[i]=max(0LL,h[i]-b*m);
      x-=(t[i]+(a-b)-1)/(a-b);
    }
    if(x>=0) r=m;
    else l=m;
  }
  cout<<r<<endl;
  return 0;
}
【E - Meaningful Mean】

区間に前処理しといて毎回ずらすやつの気配を感じる。
ぐっと睨むとある区間に対してx以上のものを数えるみたいな操作がlogでできれば解けることがわかる。
setでやりたくなるけどできないいつものやつ。AVL木使おうとしたらkeyの重複を許さないやつでア。
要素にvector持たせるやばいセグ木で常勝!w
O(Nlog^2N).

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct RMQ{
  int n;
  vector<vector<int>> dat;
  RMQ(){}
  RMQ(int n_,int* c){init(n_,c);}
  void init(int n_,int *c){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1);
    construct(n_,c);
  }
  void construct(int n_,int *c){
    for(int i=0;i<n_;i++) dat[n-1+i].push_back(c[i]);
    for(int i=n-2;i>=0;i--){
      for(int j:dat[i*2+1]) dat[i].push_back(j);
      for(int j:dat[i*2+2]) dat[i].push_back(j);
      sort(dat[i].begin(),dat[i].end());
    }
  }
  int query(int a,int b,int x,int k,int l,int r){
    if(r<=a||b<=l) return 0;
    if(a<=l&&r<=b){
      int res=0;
      auto latte=lower_bound(dat[k].begin(),dat[k].end(),x);
      res=dat[k].end()-latte;
      //cout<<res<<endl;
      return res;
    }
    int vl=query(a,b,x,k*2+1,l,(l+r)/2);
    int vr=query(a,b,x,k*2+2,(l+r)/2,r);
    return vl+vr;
  }
  int query(int a,int b,int x){
    return query(a,b,x,0,0,n);
  }
};
signed main(){
  int n,k;
  cin>>n>>k;
  int a[n],c[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int sum=0;
  for(int i=0;i<n;i++){
    sum+=a[i];
    c[i]=sum-k*(i+1);
  }
  RMQ rmq(n,c);
  int ans=0,tmp=0;
  for(int i=0;i<n;i++){
    ans+=rmq.query(i,n,tmp);
    tmp+=a[i]-k;
  }
  cout<<ans<<endl;
  return 0;
}
【F - Mirrored】

下半分だけ考えればいいと思って実装していたけど90みたいなやつがコーナーで終了五分前に気づいてはい。


参加者がどんどん増えている…!
順位がいい感じにばらけるセットで楽しかった。