読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

University CodeSprint 2

$75、ゲットだぜ!(うれしい

【 Breaking the Records 】

もう覚えてない(ア。
なにかを数えてる?O(N)っぽい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;
  cin>>n;
  ll s[n];
  for(ll i=0;i<n;i++) cin>>s[i];
  ll a=0,b=0;
  ll l=s[0],h=s[0];
  for(ll i=1;i<n;i++){
    ll t=s[i];
    if(t>h) a++,h=t;
    if(t<l) b++,l=t;
  }
  cout<<a<<" "<<b<<endl;
  return 0;
}
【 Separate the Numbers 】

最初のn文字決めうちしてシミュレーション。O(logN)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
signed main(){
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    string s;
    cin>>s;
    int n=s.length();
    bool f=0;
    for(int i=1;i<=n/2;i++){
      string t=s.substr(0,i);
      int x=stol(t);
      while((int)t.length()<n) {x++;t+=to_string(x);}
      if(t!=s) continue;
      f=1;
      cout<<"YES "<<s.substr(0,i)<<endl;
      break;
    }
    if(!f) cout<<"NO"<<endl;
  }
  return 0;
}
【 Game of Two Stacks 】

累積和が単調増加になるので片方決めうちして二分探索する。O(NlogM)。
lower_boundでk以下の最大値求めるのめんどくさい(いい方法ないかな。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll g;
  cin>>g;
  while(g--){
    ll n,m,x;
    cin>>n>>m>>x;
    ll a[n],b[m];
    for(ll i=0;i<n;i++) cin>>a[i];
    for(ll i=0;i<m;i++) cin>>b[i];
    ll sa[n+1],sb[m+1];
    sa[0]=sb[0]=0;
    for(ll i=0;i<n;i++) sa[i+1]=sa[i]-a[i];
    for(ll i=0;i<m;i++) sb[i+1]=sb[i]-b[i];
    reverse(sb,sb+m+1);
    ll ans=0;
    for(ll i=0;i<=n;i++){
      ll t=-sa[i];
      if(t>x) break;
      ll d=m-(lower_bound(sb,sb+m+1,-(x-t))-sb);
      ans=max(ans,i+d);
    }
    cout<<ans<<endl;
  }
  return 0;
}
【 The Story of a Tree 】

木を潰すと各質問に対して増える部分が区間になるのでセグ木でえいする。O(GlogN)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX=1<<18;
int n,dat[2*MAX-1],laz[2*MAX-1];
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;
}
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;
}

#define MAX_V 114514
vector<int> G[MAX_V];
int depth[MAX_V],pos;
int st[MAX_V],en[MAX_V],N;
void dfs(int v,int p=-1,int d=0){
  depth[v]=d;
  st[v]=pos++;
  for(int u:G[v]) if(u!=p) dfs(u,v,d+1);
  en[v]=pos;
}
void update(int k,int a){
  //cout<<k<<":"<<st[k]<<" "<<en[k]<<" "<<a<<endl;
  update(st[k],en[k],a);
}

signed main(){
  int q;
  cin>>q;
  while(q--){
    for(int i=0;i<MAX_V;i++) G[i].clear();
    cin>>N;
    init(N);
    for(int i=0;i<N-1;i++){
      int u,v;
      cin>>u>>v;
      u--;v--;
      G[u].push_back(v);
      G[v].push_back(u);
    }
    pos=0;
    dfs(0);
    assert(pos==N);
    int g,k;
    cin>>g>>k;
    int a[g],b[g];
    for(int i=0;i<g;i++){
      cin>>a[i]>>b[i];
      a[i]--;b[i]--;
      if(depth[a[i]]<depth[b[i]]){
	update(0,N,1);
	update(b[i],-1);
      }else{
	update(a[i],1);
      }
    }
    int ans=0;
    //for(int i=0;i<N;i++) cout<<query(i,i+1)<<endl;
    for(int i=0;i<N;i++) ans+=query(i,i+1)>=k;
    if(ans) cout<<ans/__gcd(ans,N)<<"/"<<N/__gcd(ans,N)<<endl;
    else cout<<"0/1"<<endl;
  }
  return 0;
}
Sherlock's Array Merging Algorithm 】

どこまで取ったかと一度に何個取るかを引数にしてメモ化再帰
遷移はC(前回取った数,次に取る数)倍していく感じ。
定数が軽いので気合で通す(ア。
logが重いので前計算しておく。O(NlogN+N^3)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define MAX_N 100000
#define MAX_P 200005
ll fact[MAX_P];
ll fact_i[MAX_P];
ll extgcd(ll a,ll b,ll& x,ll& y){
  ll d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
ll mod_inverse(ll a,ll m){
  if(a==0) return 1;
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}

ll euler_phi(ll n){
  ll res=n;
  for(ll i=2;i*i<=n;i++){
    if(n%i==0){
      res=res/i*(i-1);
      for(;n%i==0;n/=i);
    }
  }
  if(n!=1) res=res/n*(n-1);
  return res;
}

ll euler[MAX_N];

void euler_phi2(){
  for(ll i=0;i<MAX_N;i++) euler[i]=i;
  for(ll i=2;i<MAX_N;i++){
    if(euler[i]==i){
      for(int j=i;j<MAX_N;j+=i) euler[j]=euler[j]/i*(i-1);
    }
  }
}


ll mod_pow(ll x,ll n,ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*x%mod;
    x=x*x%mod;
    n>>=1;
  }
  return res;
}

void init(ll p){
  fact[0]=1;
  for(ll i=1;i<MAX_P;i++) fact[i]=(fact[i-1]*i)%p;
  for(ll i=0;i<MAX_P;i++) fact_i[i]=mod_inverse(fact[i],p);
}

ll mod_fact(ll n,ll p,ll& e){
  e=0;
  if(n==0) return 1;
  ll res=mod_fact(n/p,p,e);
  e+=n/p;
  if(n/p%2!=0)return res*(p-fact[n%p]) %p;
  return res*fact[n%p]%p;
} 
ll mod_comb(ll n,ll k,ll p){
  if(n==k||k==0) return 1;
  ll e1,e2,e3;
  ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
  if(e1>e2+e3) return 0;
  return a1*mod_inverse(a2*a3%p,p)%p;
}

ll dp[1250][1250];
ll n,m[1250];
ll dfs(ll pos,ll len){
  //cout<<pos<<" "<<len<<endl;
  if(~dp[pos][len]) return dp[pos][len];
  if(pos==n) return 1;
  if(len==1) return 1;
  ll res=0;
  for(ll i=1;i<=len;i++){
    ll t=1;
    if(pos) t=(fact[len]*fact_i[len-i])%MOD;
    t*=dfs(pos+i,i);
    (res+=t)%=MOD;
    if(pos+i>=n||m[pos+i-1]>m[pos+i]) break; 
  }
  //cout<<pos<<" "<<len<<":"<<res<<endl;
  return dp[pos][len]=res;
}
int main(){
  cin>>n;
  for(ll i=0;i<n;i++) cin>>m[i];
  init(MOD);
  memset(dp,-1,sizeof(dp));
  cout<<dfs(0,n)<<endl;
  return 0;
}
【 Querying Sums on Strings 】

部分点だけ。
ロリハで5点でえぇ…ってなったのでダメ元でSA試したら27.50点になってえぇ…ってなった。
なんかkの大小で解法を変えるらしい?オーダーわからず(やばい)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_N 100050
int n,k;
int r[MAX_N+1],r2[MAX_N+1];
int t[MAX_N+1];
bool compare_sa(int i,int j){
  if(r[i]!=r[j]) return r[i]<r[j];
  else{
    int ri=i+k<=n?r[i+k]:-1;
    int rj=j+k<=n?r[j+k]:-1;
    return ri<rj;
  }
}
void constract_sa(string &S, int *sa){
  n=S.length();
  for(int i=0;i<=n;i++){
    sa[i]=i;
    r[i]=i<n?S[i]:-1;
  }
  for(k=1;k<=n;k*=2){
    sort(sa,sa+n+1,compare_sa);
    t[sa[0]]=0;
    for(int i=0;i<=n;i++){
      t[sa[i]]=t[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
    }
    for(int i=0;i<=n;i++){
      r[i]=t[i];
    }
  }
}

int count(string &S,int *sa,string T){
  int a1=0,b1=S.length();
  while(b1-a1>1){
    int c=(a1+b1)/2;
    if(S.compare(sa[c],T.length(),T)<0) a1=c;
    else b1=c;
  }
  if(S.compare(sa[b1],T.length(),T)) return 0;
  int a2=0,b2=S.length()+1;
  while(b2-a2>1){
    int c=(a2+b2)/2;
    if(S.compare(sa[c],T.length(),T)<=0) a2=c;
    else b2=c;
  }
  return a2-b1+1;
}

char buf[MAX_N];
int main(){
  int n,m,q,k;
  string s;
  cin>>n>>m>>q>>k>>s;
  int sa[MAX_N+1];
  constract_sa(s,sa);
  for(int i=0;i<(int)s.size();i++) cout<<sa[i]<<endl;
  int l[m],r[m];
  for(int i=0;i<m;i++) scanf("%d %d",l+i,r+i);
  for(int i=0;i<q;i++){
    int a,b,c=0;
    scanf("%s %d %d",buf,&a,&b);
    string w=buf;
    for(int j=a;j<=b;j++){
      string t=w.substr(l[j],r[j]-l[j]+1);
      c+=count(s,sa,t);
    }
    printf("%d\n",c);
  }
  return 0;
}
【 Minimum MST Graph 】

部分点をDPで解いて実験して法則を探した。
なんか凹関数になってそうと思ったらなってた(嘘かも)ので三分探索。
三分探索のやり方よくわからないのでコードが汚い。O(Glog(S/N))。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
ll n,m,s,e,p,v;
ll check(ll i){
  if(s-(e-1)*i<=i||!i) return 1<<25;
  ll c=s-(e-1)*i,u=m-v;
  ll q=v-e;
  ans=min(ans,s+q*i+c*u);
  return s+q*i+c*u;
}
int main(){
  ll g;
  cin>>g;
  for(int cnt=1;cnt<=g;cnt++){
    cin>>n>>m>>s;
    e=n-1;
    p=m-e;
    v=(n-1)*(n-2)/2+1;
    if(m<=v){
      cout<<s+p<<endl;
      continue;
    }
    ans=0;
    ll k=s/(n-1);
    ll x=s%(n-1);
    ll y=(n-1)-x;
    ans+=s;
    ll z=min((m-(n-1)),y*(y+1)/2-y);
    ans+=k*z;
    ans+=(k+1)*(m-(n-1)-z);
    ll l=1,r=s/e;
    check(l);check(r);
    while(l+1<r){
      ll m1=l+(r-l)/3,m2=l+(r-l)*2/3;
      ll t1=check(m1),t2=check(m2);
      check(m1+1);check(m1-1);
      check(m2+1);check(m2-1);
      if(t1>t2) l=m1+1;
      else r=m2-1;
    }
    cout<<ans<<endl;
  }
  return 0;
}
【 Parallelogram Connectivity 】

これも部分点だけ。
愚直解を書いてscanfにしたら31.37 点になった。
小さい範囲から求めるようにすればならしNMになりそうな気もしたけど、
明らかに実装がやばそうなので諦めた(。
Time Limit for C/C++ is 1 seconds って書いてあるけどC++14は2秒だった(えぇ…。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
bool in(int y,int x,int y1,int x1,int y2,int x2){
  return y1<=y&&y<y2&&x1<=x&&x<x2;
}
bool used[900][900];
char s[900][900];
signed main(){
  int h,w;
  scanf("%d %d\n",&h,&w);
  for(int i=0;i<h;i++) scanf("%s\n",s[i]);
  int q;
  cin>>q;
  while(q--){
    int x1,y1,x2,y2;
    scanf("%d %d %d %d\n",&y1,&x1,&y2,&x2);
    x1--;y1--;
    int cnt=0;
    memset(used,0,sizeof(used));
    int ax[]={1,0,-1,-1,0,1};
    int ay[]={0,1,1,0,-1,-1};
    for(int i=y1;i<y2;i++){
      for(int j=x1;j<x2;j++){
	if(used[i][j]) continue;
	cnt++;
	queue<P> q;
	q.push(P(i,j));
	used[i][j]=1;
	//cout<<i<<" "<<j<<endl;
	while(!q.empty()){
	  P p=q.front();q.pop();
	  int y=p.first,x=p.second;
	  for(int k=0;k<6;k++){
	    int ny=y+ay[k],nx=x+ax[k];
	    if(!in(ny,nx,y1,x1,y2,x2)) continue;
	    if(s[ny][nx]!=s[y][x]) continue;
	    if(!used[ny][nx]){
	      used[ny][nx]=1;
	      q.push(P(ny,nx));
	    }
	  }
	}
      }
    }
    printf("%d\n",cnt);
  }
  return 0;
}
【全体】

99th(93th) やったぜ
うしさんとのチキンレース楽しかった(結果論(落ちてたら楽しくなかったと思う
ハッカーランクはペナルティがないのが僕の性に合ってるなあと思いました(KONAMI
レートはまだ変化してないみたい。
ガヴドロを買うぞ〜!