なんかいろんな解法があるのと、僕の解法が別の問題を解いた時に使った解法と似ていたので記事にします。
このリンク にも問題がいずれ出てくると思います。
続きを読む第22回日本情報オリンピック 春季トレーニング オンラインコンテスト 参加記
AOJ 2375 : CarrotBreeding (jag 冬合宿2010:day3G)
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022の14日目の記事です。
問題概要
整数 $N$ が与えられます。 二次元座標上に $K$ 個の点 $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{K},y_{K})$ を以下の条件を満たすように置きます。
任意の $i$ に対して $0\leq x_{i}\leq 10^{9}$ かつ $0\leq y_{i}\leq 10^{9}$
2点以上通る点がちょうど $N$ 本
この条件を満たす最小の $K$ が存在するならその最小の $K$ とそのときの点を出力。
存在しないなら $-1$ を出力。
例
$N=5$ のとき
$N=6$ のとき
解法
$N$ が大きい場合を先に考えます。 まず、 $K$ 点の中から２つの点を選ぶ方法は $\frac{K^{2}-K}{2}$ 通りあるので、 $A$ を $N\leq \frac{A(A-1)}{2}$ を満たす最小の整数 $A$ とすると、 $A\leq K$ が成り立ちます。
ここで $R=\frac{A(A-1)}{2}-N$ とします。
$R=0$ のときは任意の $3$ 点が同一直線上に存在しなければいいです。
$R=2$ のときは同一直線上にある $3$ 点の組がちょうど1組だけ存在すれば良いです。
$R=5$ のときは同一直線上にある $4$ 点の組がちょうど1組だけ存在すれば良いです。
例えば、上に示した $N=5$ の例は $K=5$ なので何の施しもしないと $N=10$ となりますが、 $4$ 点を同一直線上に並べているので、 $N=10-5$ より 条件を満たすようにしています。
同じような操作をすることである状態から直線の数を $-2$ したり $-5$ したりすることは可能です。
よって、 $R=1,3$ 以外であれば $K=A$ が達成可能です。
凸$K$ 多角形の角を潰すイメージで増やしていくと効率よく(点を重複させながら)同一直線上にある点の組の数を増やしていくことができます。
$R=1,3$ のときは $K=A+1$ として、$-2,-5$ を繰り返すことで達成できます。
$N$ が小さいときは少し例外が出てきます
$N=2$ のとき そもそも達成できません
$N=7$ のとき $A=5,R=3$ なので、 $K=6$ です。
$\frac{K^{2}-K}{2}-N=8$ なので、 $6$ つの点で「同一直線上にちょうど3点が存在する直線」を $4$ つ作る必要があります。
これは後で示すどの方法でも構築するのが難しいので別途で作る必要があります。
以上を実装すればいいです。
実装方法
今回は凸多角形の角を潰すイメージで考えたので実際に凸多角形を作って、その辺上に点をおくことで同一直線上に $3$ つ以上の点が存在する直線を作ります。
例えば $N=29$ のときは $6$ 角形を $N=24$ のときは $4$ 角形を返す関数を用いて、辺上に点を挿入すればいいです。
$R$ の値によって、挿入する点の数や挿入される辺の数が異なりますが、例えば $R=11$ なら $(5,2,2,2)$ を返すような、和が $N$ になる、要素が $5,2$ のみの配列を用意しておけば実装が楽になります。
また、 凸$B$ 角形を作るところを、ランダムに $B$ 個の点 をとり、2点の間を結ぶ直線の間に点を挿入するというやり方でもできます。
前者のメリットは座標が $10^{6}$ 程度で抑えられるので、問題の制約が少し厳しくなっても大丈夫である点と決定的である点で、後者のメリットは実装が楽になる点です。
コード
#include <bits/stdc++.h> using namespace std; #define rep(i,a) for(int i=0;i<a;i++) #define all(p) p.begin(),p.end() int solve(int N); int main(){ int N; cin>>N; solve(N); } int solve(int N){ if(N==7){ cout<<"6\n0 0\n0 3\n3 0\n2 0\n1 2\n0 4\n"; return 0; } if(N==2){ cout<<"-1\n"; return 0; } if(N==1){ cout<<"2\n0 0\n1 1\n"; return 0; } //a個の点を返す auto f=[&](int a)->vector<pair<int,int>>{ /* //ランダムに返す random_device rd; default_random_engine eng(rd()); uniform_int_distribution<int> distr(0,16'666'665); vector<pair<int,int>> ans(a); rep(i,a){ ans[i].first=distr(eng)*6; ans[i].second=distr(eng)*6; } return ans; */ //凸多角形を返す if(a==3){ return {{12,0},{0,0},{0,12}}; } vector<pair<int,int>> order; rep(i,200) rep(j,i+1){ if((int)order.size()==a-2) break; if(__gcd(i,j)==1){ order.push_back({i,j}); } } sort(all(order),[&](pair<int,int> l,pair<int,int> r){ return l.first*r.second>l.second*r.first; }); int H=0; rep(i,a-2) H+=order[i].second; vector<pair<int,int>> ans={{0,0},{0,H}}; rep(i,a-2){ ans.push_back({ans[i+1].first+order[i].first,ans[i+1].second-order[i].second}); } for(auto &x:ans) x.first*=6,x.second*=6; return ans; }; //点lと点rをa:bで内分する点 auto g=[](pair<int,int> l,pair<int,int> r,int a,int b)->pair<int,int>{ swap(a,b); return {(b*l.first+a*r.first)/(a+b), (b*l.second+a*r.second)/(a+b)}; }; int A=1; while(N>(A*(A-1))/2) A++; int K=A; int M=(K*(K-1))/2; int R=M-N; if(R==1||R==3){ M+=K; R+=K; K++; } int a=K; vector<int> cou(K); rep(i,K){ if(R!=8&&R!=6&&R>=5){ cou[i]=2; a-=2; R-=5; }else if(R>=2){ cou[i]=1; a-=1; R-=2; } } auto p=f(a); p.push_back(p[0]); vector<pair<int,int>> ans; rep(i,a){ ans.push_back(p[i]); rep(j,cou[i]){ ans.push_back(g(p[i],p[i+1],j+1,cou[i]-j)); } } // output ans cout<<ans.size()<<"\n"; for(auto x:ans) cout<<x.first<<" "<<x.second<<"\n"; return 0; }
AOJ 2985 : Permutation Score (jag 夏合宿2019:day2H)
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022の7日目の記事です。
問題概要
整数 $N$ が与えられます。 ここで長さ $N$ の順列 $p$ のスコア $f(p)$ を以下のように定義します。
- $N$ 頂点で、 $i\rightarrow p_{i}$ に辺が貼ってあるグラフの連結成分の大きさの総積
$p$ は $N!$ 通りありますが、このとき、 $f(p)$ の分散を $\text{mod} (10^{9}+7)$ で求めてください。
$1\leq N\leq 10^{5}$
分散の公式
$V[f(p)]=E[(f(p))^{2}]-(E[f(p)])^{2}$
つまり、スコアの平均と、スコアの二乗の平均が求まれられればいいです。
例
$N=3$ のとき、
$p=(1,2,3)$ なら $f(p)=1$
$p=(1,3,2)$ なら $f(p)=2$
$p=(2,1,3)$ なら $f(p)=2$
$p=(2,3,1)$ なら $f(p)=3$
$p=(3,1,2)$ なら $f(p)=3$
$p=(3,2,1)$ なら $f(p)=2$
よって、$E[(f(p))^{2}]=\frac{31}{6},(E[f(p)])^{2}=\frac{169}{36}$ より、 $V[f(p)]=\frac{17}{36}$ です。
解法
まず、前提として 二項係数や階乗、階乗の逆数は事前計算 $O(N)$ で $O(1)$ で求まります。
総積の平均、つまり総積の和が求めることができればいいので、いわゆる積の和典型というものを使うことで解くことができます。
積の和典型については他の人の記事に任せます。
スコアの平均
スコアの和が求まればいいです。
積の和典型を用いて一つの連結成分の中から一つ要素を選ぶことを考えます。
要素が $1$ 以上 $N$ 以下の整数の集合 $S$ のうち、空集合でないのは $2^{N}-1$ 個ありますが、これら全てについて、以下の問題の答えを求め、その和がスコアの和と等しくなります。
- 連結成分の数が $|S|$ と等しくて、 $S$ に含まれているどの異なる二つの要素も同じ連結成分に含まれないような $p$ の数を求めなさい。
$N=6,S=(3,4,5)$ のとき、以下のようなグラフがあり得ます。
$N,S$ が決まっているとき、このグラフが何通りあるかを求めばいいです。
このグラフの数が、以下の条件を全て満たす順列 $q$ の数と同じです。
- $q$ の最初の要素は $S$ の要素のうち最小のものと同じ。
- $S$ に含まれている異なる二つの要素 $a,b$ について、 $a<b$ なら $a$ の方が $b$ より早く $q$ に出てくる。
グラフと上記の条件を満たす $q$ は一対一対応しています。例えば、上の図のグラフは $q=(3,2,4,5,6,1)$ と対応しています。
この変換はグラフが $3\rightarrow 2,4,5,\rightarrow 6\rightarrow 1$ の形であるからです。
よって、 $N,S$ が決められたとき、 $q$ の場合の数は $(N-|S|)!\binom{N-1}{|S|-1}$ で、 $N,|S|$ が決められたとき、 $S$ の場合の数は $\binom{N}{|S|}$ なので、スコアの和は $|S|$ を決めると $O(1)$ でもとまるので、合計 $O(N)$ で求まります。
スコアの二乗の平均
スコアの二乗の和が求まればいいです。
一つの連結成分から順番を決めて二つ取ることを考えます。
二つとったときに、同じ要素である連結成分が $a$ 個、違う要素である連結成分が $b$ 個のとき、とった要素の場合の数とグラフの場合の数の積について考えます。
まず、要素の場合の数は、 $\binom{N}{a}\binom{N-a}{b}\frac{(N-(a+b))!}{(N-(a+2b))!}$ です。
グラフの数は前のスコアの平均の際、グラフの数を求める際に $q$ との一対一対応を考えたときと同じように考えると $\binom{N-1}{a+2b-1}$ となります。
これらの積は以下のようになります。
$$\frac{(N-1)!N!}{a!b!(a+2b-1)!(N-(a+2b))!}$$
よって、$1\leq a+2b\leq N$ かつ $0\leq a,b$ を満たす全ての $a,b$ に対して、上記の式の和を求めればいいです。
愚直にやると $O(N^{2})$ なので、これを高速化する必要があります。
例えば $c=a+2b$ を固定して考えることで、多項式 $f(x)=\sum \frac{x^{i}}{i!},g(x)=\sum \frac{x^{2i}}{i!}$ の積を求め、$x^{c}$ の係数に $\frac{1}{(c-1)!(N-c)!}$ をかけたものの総和を計算するという求め方で、任意 mod 畳み込みを用いて $O(N\log N)$ で求まりますが、実は畳み込みを用いないで求めることができます。
まず、$h(x)=(1+x)^{N-1}$ とすると $\frac{(N-1)!}{(c-1)!(N-c)!}=\binom{N-1}{N-c}$ であることから、スコアの二乗の和は $f(x)g(x)h(x)$ の $x^{N}$ の係数に $N!$ をかけたものに等しいです。 $f(x)=e^{x},g(x)=e^{x^{2}}$ なので、以下が成り立ちます。
$f(x)g(x)h(x)=e^{x+x^{2}}(1+x)^{N-1}=\sum\frac{1}{i!}x^{i}(1+x)^{N-1+i}$
$i=1,2,...,N$ に対して、 $x^{N}$ の係数を求めるのは $O(1)$ でできるため、合計 $O(N)$ でスコアの二乗の和を求めることができました。
コード
modint ではないので、計算のたびに mod で割らないといけないのですが、見やすさのため main 関数内では省いています。
#include <bits/stdc++.h> using namespace std; using ll=long long; #define rep(i,a,b) for (ll i=a;i<b;i++) namespace po167{ struct combination{ int upper; long long MOD; std::vector<long long> fact; std::vector<long long> rev; std::vector<long long> fact_rev; combination(int max,long long _mod):upper(max),MOD(_mod),fact(max+1),rev(max+1),fact_rev(max+1){ for(long long i=0;i<=max;i++){ if(i<2){ fact[i]=1; fact_rev[i]=1; rev[i]=1; continue; } fact[i]=(fact[i-1]*i)%_mod; rev[i]=_mod-((_mod/i)*rev[_mod%i])%_mod; fact_rev[i]=(fact_rev[i-1]*rev[i])%_mod; } } void upper_change(int n_upper){ assert(n_upper<MOD); while(upper<n_upper){ upper++; fact.push_back(fact[upper-1]*upper%MOD); rev.push_back(MOD-((MOD/upper)*rev[MOD%upper])%MOD); fact_rev.push_back((fact_rev[upper-1]*rev[upper])%MOD); } } long long Comb(int x,int y){ upper_change(x); if (x<y||y<0||x<0) return 0; return (((fact_rev[y]*fact_rev[x-y])%MOD)*fact[x])%MOD; } long long P(int x,int y){ upper_change(x); if (x<y||y<0||x<0) return 0; return (fact_rev[x-y]*fact[x])%MOD; } }; } using po167::combination; int main() { const ll mod=1e9+7; int N; cin>>N; ll ans=0; combination table(N*2,mod); ll tmp=0; rep(i,1,N+1){ tmp+=(table.fact[N-i]*table.Comb(N,i)*table.Comb(N-1,i-1)); } tmp*=table.fact_rev[N]; ans=-(tmp*tmp); rep(i,1,N+1){ tmp=table.fact_rev[i]*table.Comb(N-1+i,N-i); ans+=tmp; } cout<<ans<<"\n"; }
