beet's soil

競プロのことなど

SnackDown 2017 Online Elimination Round (解法編)

6完 151st Tシャツget!!(無事届くとは言っていない
うしslack編をそのうち書きます とりあえず担当した問題の方を。

【Mex division】

n要素からなる数列が与えられる。
これをいくつかの連続部分列にそれぞれのmexがk以下になるように分割する。
可能な分割の場合数をmod 1e9+7 で答える。

 dp[idx] :=idxまで使った時の場合の数
 b[idx] :=b[idx]からidxまでのmexがk以下であるような最小なb[idx]
とすると、
 dp[idx] = \sum_{j=b[idx]}^{idx-1} dp[j] となる。

 b[idx] は前計算でしゃくとりっぽくやると
O(NlogN)で求めることができるので求める。
idxを1つずつ進めていってmexがk以下になるまで後ろを進めると全体でO(N).
(setのlogがつくので実際はO(NlogN).
mexを求めるにはsetに1~5*10^5までぶち込んでおいて、
ないものの集合として考えるとmexは*s.begin()になる。
同じ数が複数出現するとめんどくさいので、
mapである数が最後に現れたところみたいなのを保持した。
あとは区間sum点addができればいいのでBITでえいってやる。

定数倍がきつくて大変だった。
区間sum点addを遅延セグ木は定数倍がア。BITを使いましょう。
mod 1e9+7 をとり忘れてうしさんにえぇ…と言われたのは内緒だゾ☆

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
struct BIT{
  vector<int> bit;
  int n;
  //1-indexed
  BIT(){init();}
  BIT(int n):n(n){init();}
  void init(){
    bit.clear();
    bit.resize(n+1,0);
  }
  int sum(int i){
    int s=0;
    while(i>0){
      (s+=bit[i])%=MOD;
      i-=i&-i;
    }
    return s;
  }
  void add(int i,int x){
    while(i<=n){
      (bit[i]+=x)%=MOD;
      i+=i&-i;
    }
  }
  int sum0(int i){
    return sum(i+1);
  }
  void add0(int i,int x){
    add(i+1,x);
  }
};

signed main(){
  int n,k;
  //cin>>n>>k;
  scanf("%lld %lld",&n,&k);
  int a[n];
  //for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) scanf("%lld",a+i);
  if(k==0){
    for(int i=0;i<n;i++){
      if(a[i]==0){
	cout<<0<<endl;
	return 0;
      }
    }
  }
  set<int> s;
  int ma=min(n,k);
  for(int i=0;i<=ma+1;i++) s.insert(i);
  int b[n],j=0;
  map<int,int> m;
  for(int i=0;i<n;i++){
    if(a[i]<=ma&&s.count(a[i])) s.erase(a[i]);
    m[a[i]]=i;
    //cout<<a[i]<<endl;
    //cout<<"s:";for(int p:s) cout<<" "<<p;cout<<endl;
    while(j<=i&&*s.begin()>k){
      if(m[a[j]]==j&&a[j]<=ma) s.insert(a[j]);
      j++;
    }
    b[i]=j;
  }
  BIT bit(n+10);
  bit.add0(0,1);
  for(int i=0;i<n;i++){
    int x=bit.sum0(i)-bit.sum0(b[i]-1);
    bit.add0(i+1,x%MOD);
    //cout<<i<<" "<<b[i]<<":"<<x<<endl;
  }
  printf("%lld\n",(bit.sum0(n)+MOD-bit.sum0(n-1))%MOD);
}
【Chef and Pairs】

C,Dをそれぞれn要素、m要素の配列、eを定数とする。
maxMatching(C, D, e)をCとDからなる二部グラフで、
差の絶対値がe以下になるものにエッジを張った場合の最大マッチングとする。
Cの各要素に適切なoffsetを加算して最大マッチングを最大化した時の値を求める。

あるタイミングでCiとDjがマッチング可能になるとすると、
そのタイミングは各(i,j)の組に対しO(1)で求められる。
イベント点がCとDの各要素に対してO(nm)個で、
マッチングはあらかじめソートしておくとO(n+m)でできる。
全体としてO(nm(n+m))となって微妙だけどまあなんかいい感じになって通る(ア。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int match(int *c,int *d,int e,int n,int m){
  int res=0;
  int j=0;
  for(int i=0;i<n;i++){
    while(j<m&&d[j]+e<c[i]) j++;
    if(j==m) break;
    if(abs(c[i]-d[j])<=e) res++,j++;
  }
  return res;
}
signed main(){
  int T;
  cin>>T;
  while(T--){
    int n,m,e;
    cin>>n>>m>>e;
    int c[n],d[m];
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<m;i++) cin>>d[i];
    sort(c,c+n);
    sort(d,d+m);
    set<int> s;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
	if(abs(c[i]-d[j])<=e) continue;
	if(c[i]<d[j]) s.insert(d[j]-(c[i]+e));
	else s.insert(d[j]-(c[i]-e));
      }
    }
    int ans=match(c,d,e,n,m);
    for(int i:s){
      for(int j=0;j<n;j++) c[j]+=i;
      ans=max(ans,match(c,d,e,n,m));
      for(int j=0;j<n;j++) c[j]-=i;
    }
    cout<<ans<<endl;
  }
  return 0;
}
【Four Points】

4点が与えられる。全ての点がある三角形の辺上にあるような三角形をつくれるならどれか一つ、
できないならNOを出力する。

(that is, all three of its vertices can be collinear).
と書いてあって三角形とは?(哲学)という気持ちになる。

4点を2本の直線に分けると三角形にできるかできないかみたいなことがまあわかる。
できない場合は平行四辺形かある点が他の三点からなる三角形の内部にあるみたいな状態。
後者はどうやっても無理で、前者はなんか二辺を倍の長さにするとうれしい(図を描くとはい。

残り10分ちょいくらいで通って熱かった。
うしさんがコーナー見つけてくれなかったら無理だった。(いえいえい

幾何パートは省略

signed main(){
  int T;
  cin>>T;
  while(T--){
    Polygon s(4);
    for(int i=0;i<4;i++) cin>>s[i];
    bool flg=0;
    for(int i=0;i<4;i++){
      for(int j=0;j<4;j++){
	if(i==j) continue;
	for(int k=0;k<4;k++){
	  if(i==k||j==k) continue;
	  for(int l=0;l<4;l++){
	    if(i==l||j==l||k==l) continue;
	    //if(isParallel(s[i],s[j],s[k],s[l])) continue;
	    Polygon q(3);
	    q[0]=getCrossPointLL(Line(s[i],s[j]),Line(s[k],s[l]));
	    if(abs(q[0].x)>1e6||abs(q[0].y)>1e6) continue;
	    q[1]=abs(s[i]-q[0])>abs(s[j]-q[0])?s[i]:s[j];
	    q[2]=abs(s[k]-q[0])>abs(s[l]-q[0])?s[k]:s[l];
	    bool tmp=1;
	    for(int z=0;z<4;z++){
	      bool ff=0;
	      for(int x=0;x<3;x++){
		for(int y=0;y<3;y++){
		  if(x==y) continue;
		  ff|=equals(abs(q[x]-q[y]),abs(q[x]-s[z])+abs(q[y]-s[z]));
		}
	      }
	      tmp&=ff;
	    }
	    if(!tmp) continue;
	    cout<<"YES "<<q[0]<<" "<<q[1]<<" "<<q[2]<<endl;
	    flg=1;
	    goto END;
	  }
	}
      }
    }
    
    for(int i=0;i<4;i++){
      for(int j=0;j<4;j++){
	if(i==j) continue;
	for(int k=0;k<4;k++){
	  if(i==k||j==k) continue;
	  Polygon q(3);
	  q[0]=s[i];
	  q[1]=s[i]+(s[j]-s[i])*2.0;
	  q[2]=s[i]+(s[k]-s[i])*2.0;
	  bool tmp=1;
	  for(int z=0;z<4;z++){
	    bool ff=0;
	    for(int x=0;x<3;x++){
	      for(int y=0;y<3;y++){
		if(x==y) continue;
		ff|=equals(abs(q[x]-q[y]),abs(q[x]-s[z])+abs(q[y]-s[z]));
	      }
	    }
	    tmp&=ff;
	  }
	  if(!tmp) continue;
	  cout<<"YES "<<q[0]<<" "<<q[1]<<" "<<q[2]<<endl;
	  flg=1;
	  goto END;
	}
      }
    }
    
  END:
    if(!flg) cout<<"NO"<<endl;
  }
  return 0;
}

チーム戦たのしいな〜〜〜〜!!!
詳しい感想はうしslack編で書きまつ!w