beet's soil

競プロのことなど

AtCoder Grand Contest 012

272nd 1958 -> 1957 (-1)
コンテスト中はAとBの部分点だけ。解説を見てCDも通した。

【A - AtCoder Group Contest】

3*N人をNグループに分けてそれぞれのグループ内の中央値の和を最大化したい。

常に2位の人を選びたい気分になる。
ソートして上から選んでいけばいい。O(NlogN)

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int a[3*n];
  for(int i=0;i<n*3;i++) cin>>a[i];
  sort(a,a+3*n);
  reverse(a,a+3*n);
  int ans=0;
  for(int i=0;i<n;i++) ans+=a[i*2+1];
  cout<<ans<<endl;
  return 0;
}
【B - Splatter Painting】

N頂点のグラフが与えられてQ回色を塗る操作をする。
一回の操作ではある頂点からd_i以内の距離にある頂点をc_i色に塗る。
それぞれの頂点の最終的な色を求める。

クエリを先読みして逆順に考えれば塗られていない部分を塗る問題になる。
d_i<=10なのでその頂点からk以内を塗ったかどうかをフラグで持っておくと
全体でO(Q+Nd)になって間に合う。

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> G[114514];
typedef pair<int,int> P;
signed main(){
  int n,m;
  cin>>n>>m;
  for(int i=0,a,b;i<m;i++){
    cin>>a>>b;
    a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  int q;
  cin>>q;
  int v[q],d[q],c[q];
  for(int i=0;i<q;i++){
    cin>>v[i]>>d[i]>>c[i];
    v[i]--;
  }
  int p[n];
  memset(p,-1,sizeof(p));

  bool used[11][n];
  memset(used,0,sizeof(used));

  reverse(v,v+q);
  reverse(d,d+q);
  reverse(c,c+q);
  for(int i=0;i<q;i++){
    if(used[d[i]][v[i]]) continue;
    queue<P> qu;
    qu.push(P(v[i],d[i]));
    used[d[i]][v[i]]=1;
    while(!qu.empty()){
      P pp=qu.front();qu.pop();
      int u=pp.first,di=pp.second;
      if(p[u]<0) p[u]=c[i];
      for(int k=0;k<=di;k++) used[k][u]=1;
      if(!di) continue;
      for(int j=0;j<(int)G[u].size();j++){
	if(used[di-1][G[u][j]]) continue;
	qu.push(P(G[u][j],di-1));
      }
    }
  }
  for(int i=0;i<n;i++) cout<<(p[i]<0?0:p[i])<<endl;
  return 0;
}
【C - Tautonym Puzzle】

ある文字列を二回繰り返した文字列を"いい文字列"とする。
文字列Sの部分列のうち、いい文字列であるものがN個であるようなSを求める。

解説を見てその通り実装した。
1~kまでを使って作った数列をTとすると、Tの後ろに1~kを並べた数列Uを考える。
Uの部分列のうち、いい文字列の個数はTの増加部分列の個数と一致する。
よってちょうどN個の増加部分列を含む文字列を構築できれば良い。
1~kまでを並べた数列の増加部分列の個数は、自明に2^k-1個。
この数列のi番目(0-origin)にk+1を挿入すると、増加部分列の個数は2^iだけ増加する。
これはなんかいい感じに選ぶことで独立にできるので、やるとできる。
O(logN).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int p=0,q=1;
  while(q*2-1<=n) q*=2,p++;
  vector<int> ans;
  for(int i=0;i<p;i++) ans.push_back(i+1);
  q=n-(q-1);
  int x=1;
  for(int i=p-1;i>=0;i--){
    if((q>>i)&1){
      ans.insert(ans.begin()+i,p+x);
      x++;
    }
  }
  q=ans.size();
  for(int i=0;i<q;i++) ans.push_back(i+1);
  cout<<ans.size()<<endl;
  for(int i=0;i<(int)ans.size();i++)
    cout<<ans[i]<<" \n"[i==(int)ans.size()-1];
  return 0;
}
【D - Colorful Balls】

N個の色がついたボールが並んでいる。
それぞれのボールには重みがついている。
任意の2つのボールについて、
色が同じで重さの和がX以下
色が異なり重さの和がY以下
のいずれかの時に場所を入れ替えることができる。
あり得るボールの並び方の総数をMOD1e9+7で求めよ。

色の種類が1種類の時は1。
ABCというボールがあって、ABとBCが交換可能ならACも交換可能である。
よってUnionFind的なデータ構造で扱えそう。
あるボールについて、そのボールと同じ色のボールについては、最も軽いものだけと試せばいい。
(なぜなら、最も軽いものと交換できないなら他のものとも交換できず、
最も軽いものと交換できるならそれを通じて他のボールとも交換できるので。)
他の色のボールに関しても、同様に最も軽いボールについてだけ考えればよい。
最後に、集合の大きさの順列組み合わせの数を、各色の数の順列組み合わせの数で割ったものを
掛け合わせれば答えがもとまる。
UnionFindだとこのパートがめんどくさいので、QuickFindを用いた。
QuickFindはデータ構造をマージする一般的なテクでuniteがならしO(logN)、sameがO(1)でできる。
あと集合そのものをvectorで持てるので集合に含まれる要素を調べる時に楽。
O(NlogN).

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

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

struct UnionFind{
  vector<int> r,p;
  vector<vector<int> > v;
  UnionFind(){}
  UnionFind(int size){init(size);}
  void init(int size){
    r.resize(size,0);
    p.resize(size,0);
    v.resize(size);
    for(int i=0;i<size;i++){
      r[i]=1,p[i]=i;
      v[i].resize(1,i);
    }
  }
  bool same(int x,int y){
    return p[x]==p[y];
  }
  void unite(int x,int y){
    x=p[x];y=p[y];
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    for(int i=0;i<(int)v[y].size();i++){
      p[v[y][i]]=x;
      v[x].push_back(v[y][i]);
    }
    v[y].clear();
  }
};


signed main(){
  int n,x,y;
  cin>>n>>x>>y;
  int c[n],w[n];
  for(int i=0;i<n;i++) cin>>c[i]>>w[i];
  UnionFind uf(n);
  map<int,int> m;
  for(int i=0;i<n;i++)
    if(!m.count(c[i])||w[i]<w[m[c[i]]]) m[c[i]]=i;
  if((int)m.size()==1){
    cout<<1<<endl;
    return 0;
  }
  int s1=0;
  for(int i=0;i<n;i++)
    if(w[i]<w[s1]) s1=i;
  int s2=-1;
  for(int i=0;i<n;i++){
    if(c[i]==c[s1]) continue;
    if(s2<0||w[i]<w[s2]) s2=i;
  }
  for(int i=0;i<n;i++){
    if(w[m[c[i]]]+w[i]<=x)
      uf.unite(i,m[c[i]]);
    if(c[i]!=c[s1]&&w[i]+w[s1]<=y)
      uf.unite(i,s1);
    if(c[i]!=c[s2]&&w[i]+w[s2]<=y)
      uf.unite(i,s2);
  }
  init(MOD);
  int ans=1;
  for(int i=0;i<n;i++){
    if(uf.p[i]!=i) continue;
    //cout<<uf.r[i]<<":"<<endl;
    (ans*=fact[uf.r[i]])%=MOD;
    map<int,int> m2;
    for(int j=0;j<(int)uf.v[i].size();j++)
      m2[c[uf.v[i][j]]]++;
    for(auto j:m2) (ans*=fact_i[j.second])%=MOD;//,cout<<j.second<<endl;
  }
  cout<<ans<<endl;
  return 0;
}