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

beet's soil

競プロのことなど

8VC Venture Cup 2017 - Elimination Round

ARCの調子が良かったので出た

【A. PolandBall and Hypothesis】

問題文の通りに書く。
hackしようとしていたらn+2またはn-2でいいことがわかって天才かってなった。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool isprime(ll x){
  for(ll i=2;i*i<=x;i++) if(x%i==0) return 0;
  return 1;
}
int main(){
  ll n;
  cin>>n;
  for(ll i=1;i<=1000;i++){
    if(!isprime(n*i+1)){
      cout<<i<<endl;
      return 0;
    }
  }
  return 0;
}
【B. PolandBall and Game】

共通のやつから使っていった方がよくて、言える数が多い方の勝ち。
setで殴る。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,m;
  cin>>n>>m;
  set<string> ss[2],c;
  string s;
  for(int i=0;i<n;i++){
    cin>>s;
    ss[0].insert(s);
  }
  for(int i=0;i<m;i++){
    cin>>s;
    ss[1].insert(s);
  }
  for(auto i:ss[0]) if(ss[1].count(i)) c.insert(i);
  int x=ss[0].size()-c.size(),y=ss[1].size()-c.size(),z=c.size();
  x+=z-z/2;
  y+=z/2;
  if(x>y) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}
【C. PolandBall and Forest】

直径の性質的に一番遠いやつと繋いでいけばいい。
UnionFindで殴る。

#include<bits/stdc++.h>
using namespace std;
struct UnionFind{
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int size){init(size);}
  void init(int size){
    r.resize(size,0);
    p.resize(size,0);
    for(int i=0;i<size;i++) r[i]=1,p[i]=i;
  }
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};
int main(){
  int n;
  cin>>n;
  UnionFind u(n);
  for(int i=0;i<n;i++){
    int p;
    cin>>p;
    u.unite(i,p-1);
  }
  int ans=0;
  for(int i=0;i<n;i++) ans+=u.find(i)==i;
  cout<<ans<<endl;
  return 0;
}
【D. PolandBall and Polygon】

BITで交差するエッジの数+1を足していけばいい。
2周文持って置けば実装が楽。
k>n/2のときバグるのでk=min(k,n-k)としなくてはいけない。
(system testに落ちた人の顔

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 1 << 22;
int bit[MAX_N+1],n;
//1-indexed
int sum(int i){
  int s=0;
  while(i>0){
    s+=bit[i];
    i-=i&-i;
  }
  return s;
}
void add(int i,int x){
  while(i<=2*n){
    bit[i]+=x;
    i+=i&-i;
  }
}
signed main(){
  memset(bit,0,sizeof(bit));
  int k;
  cin>>n>>k;
  k=min(k,n-k);
  int c=1,p=1;
  for(int i=0;i<n;i++){
    c+=sum(p+k-1)-sum(p)+1;
    add(p,1);
    add(p+n,1);
    p+=k;
    if(p>n) p-=n;
    add(p,1);
    add(p+n,1);
    //cout<<p<<" "<<sum(p)<<" "<<p+n<<" "<<sum(p+n)<<" "<<c<<endl;
    cout<<c<<" \n"[i==n-1];
  }
  return 0;
}
【全体】

ooox--- 2880 point 602nd
1834 -> 1863 (+29) highest
Dをコンテスト中に通せてればdiv1いけてそう、、
まあ眠かったのでしょうがないね(言い訳