AtCoder Regular Contest 101 参加記

1ヶ月ぶりくらいかつ8月最後のrated,久しぶりのコンテストでめちゃくちゃ緊張してた

C問題 Candles

問題

C - Candles

解法

sortedなので全部の[x,x+m)について距離を求めていけば良い.O(N)
デバッグ出力は消しましょう(何回目だおい

D問題 Median of Medians

解法

  • 素数Nの数列の中央値は,x以上の値がN/2個ある数のうち最小のもの

→二分探索で探せる形

  • 区間の中央値がx以上であるということは,その区間に存在するx以上の要素の個数がx未満の要素の個数より少なくないということ.

x以上のものを+1,x未満のものを-1として累積和を取ると(区間のx以上の要素数)-(区間のx未満の要素数)が求まる
ここまででオーダーをO(N^2log N)に落とすことができた.(まだTLE)

  • 区間(区間のx以上の要素数)-(区間のx未満の要素数)が非負であればよいので,各終端についてそれより前でそれ以下のものを探せば良い.これはBITで可能.

ここまでやるとオーダーがO(N log^2N)になって通る.

結果

f:id:SugarDragon5:20180825231520p:plain
青コーダーになりました.まじで時間かかった.嬉しい

yukicoder No.727 仲介人moko

概要

品物を売りたい人と買いたい人がそれぞれN人いる.
売りたい人は来ると品物を1つ売り,買いたい人は売っているものからなにか1つ買う.
売買の組み合わせは何通りあるか

解法

愚直DPしか思いつかないしそのままだとOEISに出てこなくて(階乗で割ると出るらしい)辛かった.

  • 品物を買いたい人それぞれについて誰の品物を買うか決める([tex;N!]通り)
  • 売る人買う人の配置を考える(1\times 3\times 5\times ...\times (2N-1)通り) ※詳しくは下で
  • 配置にペアを当てはめる(N!通り)

なので,1\times 3\times 5\times ...\times 2N-1 \times (N!)^2とかになる.

配置について

配置の場合の数は1\times 3\times 5\times ...\times (2N-1)になるらしい.これは2N頂点の完全グラフの完全マッチングの個数らしいがよくわからないのでなぜこうなるかまとめてみる.
まずN=1は明らかに1通り.
N=2はこんな感じで
f:id:SugarDragon5:20180825000737p:plain
N=1の最初とそれに対応するどこかに挿入したものなので,a_2=a_1\times 3
N=3も,
f:id:SugarDragon5:20180825001035p:plain
みたいな感じにN=2の最初と対応する箇所に挿入したもので,a_3=a_2\times 5
こんな感じで以下のような漸化式が立って
 a_1=1,a_{n+1}=a_n\times (2n-1)
これを解けばいい.

TopCoder SRM 621 Div1 Easy RadioRange

概要

(0,0)から半径r (0\lt r\lt z)の電波を飛ばす.
n個の街があり,i個目は中心(X_i,Y_i)で半径R_iの円形である.
すべての街について電波が全く届かないか完全に届くかのどちらかであるようなzの範囲の割合を求めよ.

解法

余事象を考えると,街iに対し良くない範囲は[max(0,sqrt(X_i^2+Y_i^2)-R_i,min(sqrt(X_i^2+Y_i^2)*R_i,z)]である.
これを各街についてとってそれらをマージし,割合を求めれば良い.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class RadioRange{
public:
    double dist(double x,double y){
        return sqrt(x*x+y*y);
    }
    double RadiusProbability(vi x,vi y,vi r,int z){
        using Pd=pair<double,double>;
        int n=x.size();
        vector<Pd> vec;
        REP(i,n){
            if(dist(x[i],y[i])-r[i]>z){
                continue;
            }
            vec.pb(Pd(max(0.0,dist(x[i],y[i])-r[i]),min(1.0*z,dist(x[i],y[i])+r[i])));
        }
        while(1){
            bool f=false;
            vector<Pd> t;
            sort(all(vec));
            int m=vec.size();
            REP(i,m){
                int r=i;
                double ma=vec[i].se;
                while(r+1<m&&vec[r+1].fi<vec[r].se){
                    r++;
                    f=true;
                    chmax(ma,vec[r].se);
                }
                t.pb(Pd(vec[i].fi,ma));
                i=r;
            }
            vec=t;
            if(!f){
                break;
            }
        }
        double res=0.0;
        REP(i,vec.size()){
            res+=vec[i].se-vec[i].fi;
        }
        return 1.0-res/z;
    }
};

TopCoder SRM620 Div1 easy Easy PairGame

概要

正の整数の組(p,q)に対して次の操作を考える.

  • (p+q,q),(p,p+q)のどちらかに置き換える.

この操作を何回か繰り返した結果(a,b)にも(c,d)にもすることができる(x,y)のうちx+yの最大値を求めよ.

解法

(x,y)になるのは,x\lt yのとき(x,y-x)x\gt yのとき(x-y,y)なので(a,b),(c,d)に対して逆回しして得られるものを調べる

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class PairGame{
    set<P> f(int x,int y){
        set<P> res;
        queue<P> que;
        res.insert(P(x,y));
        que.push(P(x,y));
        while(que.size()){
            P p=que.front();que.pop();
            if(p.fi>p.se){
                p.fi-=p.se;
            }else{
                p.se-=p.fi;
            }
            if(!p.fi||!p.se){
                continue;
            }
            if(!res.count(p)){
                res.insert(p);
                que.push(p);
            }
        }
        return res;
    }
public:
    int maxSum(int a,int b,int c,int d){
        set<P> p=f(a,b);
        set<P> q=f(c,d);
        int ans=-1;
        for(auto itr:p){
            if(q.count(itr)){
                chmax(ans,itr.fi+itr.se);
            }
        }
        return ans;
    }
};

JOI'14 春1-2 愉快なロゴデザイン

問題文

https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d1.pdf
ある日 K 理事長は,円状に ‘J’, ‘O’, ‘I’ の文字を並べたものをロゴとすることを思いついた.これには JOI を楽
しんで (enjoy) もらいたい
とする思いが込められている.

解法

同じ文字列を後ろにつなげて各文字累積和をとって始点決めて再帰で計算

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int n;
string st;
vvi sum;
string joi("JOI");
int f(int x,int level){
    if(!level){
        return 0;
    }
    //xから始まるlevel列のコスト
    int len=1<<((level-1)*2);
    //J[x,x+len-1]
    int p=len-sum[x+len-1][0];
    if(x){
        p+=sum[x-1][0];
    }
    //O[x+len,x+len*2-1]
    int q=len-sum[x+len*2-1][1]+sum[x+len-1][1];
    int r=len-sum[x+len*3-1][2]+sum[x+len*2-1][2];
    return p+q+r+f(x+len*3,level-1);
}
int main(){
    cin>>n;
    int len=1<<(n*2+1);
    cin>>st;
    st+=st;
    sum.resize(len,vi(3));
    REP(i,len){
        REP(j,3){
            if(st[i]==joi[j]){
                sum[i][j]=1;
            }
        }
    }
    REP(i,len-1){
        REP(j,3){
            sum[i+1][j]+=sum[i][j];
        }
    }
    int ans=INF;
    REP(i,len/2){
        chmin(ans,f(i,n));
    }
    cout<<ans<<endl;
    return 0;
}

TopCoder SRM 619 Div1 Easy SplitStoneGame

問題概要

N要素の数列で次の操作を交互に繰り返す.

  • 2以上の要素xを選んで,和がxの正の2数a,bに分ける.
  • x以外に要素2つをp,qとし,p+=x,q+=bする.

この操作ができなくなったほうが負け.先手が勝つならWINを,負けるならLOSEを返す

解法

xは2以上の要素からしか選ぶことができないし,それさえ満たしていれば操作できる回数は変わらないためどれを選んでも良い.
逆に,p,qはできるだけ1の要素から選びたい.2以上の要素が増えると操作回数は増えるからである.またこれも1であればどれを選んでもよい.
数列の要素のうち,2以上のものの個数をt,1のものの個数をuとする.
f(t,u)=(2以上がt個,1がu個ある盤面が渡されたとき勝てるか)とすると,
f(t,u) = 
\begin{cases}
false & (t+u<3 \lor t=0) \\
!f(t-1,0) & (u=0)\\
!f(t,0) &(u=1)\\
!f(t+1,u-2) &(otherwise)
\end{cases}
となる.これを再帰で解けばよい.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;

class SplitStoneGame{
public:
    bool dfs(int p,int q){
        if(p+q<3){
            return false;
        }
        if(!p){
            return false;
        }
        if(!q){
            return !dfs(p-1,0);
        }else if(q==1){
            return !dfs(p,0);
        }else{
            return !dfs(p+1,q-2);
        }
    }
    string winOrLose(vi vec){
        int n=vec.size();
        int p=0,q=0;
        REP(i,n){
            if(vec[i]>1){
                p++;
            }else{
                q++;
            }
        }
        return dfs(p,q)?"WIN":"LOSE";
    }
};

TopCoder SRM 618 Div1 easy Family

概要

N人に対し,その両親の情報が与えられる.両親はそれぞれ性別が異なる必要があるが,そのような組み合わせはあるか

解法

親同士を結んだグラフが二部グラフかどうか判定すれば良い.
二部グラフの判定手法としてUnionFindで行うのが良いというのをどこかで聞いたので以下を参考にした.
noshi91.hatenablog.com

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
struct UnionFind{
    vector<int> data;
    UnionFind(int size):data(size,-1){}
    bool unite(int x,int y){
        x=root(x);y=root(y);
        if(x!=y){
            if(data[y]<data[x])swap(x,y);
            data[x]+=data[y];data[y]=x;
        }
        return x!=y;
    }
    bool find(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0?x:data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};
class Family{
public:
    string isFamily(vi a,vi b){
        int n=a.size();
        UnionFind uf(n*2);
        REP(i,n){
            if(a[i]!=-1){
                uf.unite(a[i],b[i]+n);
                uf.unite(a[i]+n,b[i]);
            }
        }
        REP(i,n){
            if(uf.find(i,i+n)){
                return "Impossible";
            }
        }
        return "Possible";
    }
};