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

Educational Codeforces #20 F: Coprime Subsequences

事前に1~max(a[1],a[2],...,a[n])の約数を求めておく。
次に、約数qをもつ数を数えて
cnt[q]
のように表す。
部分列のgcdをgとしたときq|gを満たす空でない部分列を数えよう。
これは簡単で、qを約数にもつ数すべてについて、部分列に含むかどうかを考えて
cnt[q]^2-1
となる。
GCDがgであるような部分列の数をdp[g]とする。
dp[1]が解である。
dp[g]
= (gを約数に持つ部分列の数) - (gを約数に持つが最大公約数がgより大きいg'である部分列の数)
= cnt[g]^2-1 - Σ[g'はgの倍数](dp[g'])
この式の前半部分は先に説明した。
後半部分の計算を考えよう。
g'はgの倍数である。
⇔gはg'の約数
なのであるdp[g']が求まったとき、g'のg'以外の約数gについて、dp[g]からdp[g']を引く。g'>gが成り立つので
dpを値の大きい順に計算していけばいい。

計算量について
約数を計算する前処理は
θ(Σ√a[i])
dpは遷移は
約数の個数の最大値をmとしたとき
O(m*max(a))
10^5以下で最も約数が多いのは
83160であり約数の個数はたかだか128個なので間に合う。

Educational Codeforces #20 C: Maximal GCD

a[1]~a[k]のGCDをgとする。

g | a[i]なので
b[i] = a[i]/g
のような数列bを定められる。(b[i]>=1)
Σa[i] = n
より
gΣb[i] = n
g | n
よって
gの候補はnの約数のみ。すべて試す。
総和を考慮せずに、とりあえず一番和の小さい数列を作ると
a[i]=gi
その和は
Σgi
=gΣi
=gi*(i+1)/2
これはn以下でなければならないから、
gk*(k+1)/2<=n
逆にこのとき、
足りないn-gi(i+1)/2 をa[k]に加えればよい。

SRM 658 DIV1 Med: Mutalisk

/*

思いつき方
二分探索
チェック関数を書く
bool のDPになった。
boolのDPは次元を一つ減らせるかも。
intで残りの1を使える回数の最大値をもたせればいい。
*/
/*
dp[i][j][k]
:=
i番目まで破壊し、残りj回9の攻撃、k回3の攻撃ができるとき、残りの1の攻撃回数の最大値
*/

/*
K回の攻撃でOKか調べたい。

ある要素に対して
S = 9を使った回数 + 3を使った回数 + 1を使った回数 <= K
でなければならない。
S > K
とすると、
K+1回以上の操作が必要になってしまう。
S<=K
とすると、残りの操作回数は他に配ればいい。これはDPの条件そのまま。
*/

広告を非表示にする

SRM 712 DIV1 Easy: LR

操作後のA[i]をA'[i]のように表記する。
(1)LRの操作
Lの操作により
A'[i] = A[i-1]+A[i]
A'[i+1] = A[i]+A[i+1]
更にRの操作により
A''[i]
= A'[i] + A'[i+1]
= (A[i-1]+A[i]) + (A[i]+A[i+1])
= A[i-1]+2A[i]+A[i+1]
(2)RLの操作
Rの操作により
A'[i] = A[i]+A[i+1]
A'[i-1] = A[i-1]+A[i]
更にLの操作により
A''[i]
= A'[i-1]+A'[i]
= (A[i-1]+A[i])+(A[i]+A[i+1])
= A[i-1]+2A[i]+A[i+1]

以上から、LRの操作とRLの操作は等しいことがわかる。
なので、L,Rのそれぞれの操作回数だけが問題であり、操作の順番はどうでもいい。
L,Rの操作回数を総当りしてシミュレーションしても間に合う。
n=|A|、操作回数の最大値をmとして
O(n*m^2)で間に合う。

広告を非表示にする

AtCoder ARC D: 見たことのない多項式

ガウスジョルダンの消去法などを知っていればO(n^3)で部分点40(/100)、ラグランジュ補間を知っていればO(n^2)で部分点80(/100)をとれる。

ラグランジュ補間を工夫する。

ラグランジュ補間

一般に多項式P(x)についてi!=jのときx[i]!=x[j]ならば

P(x) = Σ[i=0...n]( P(x[i]) * f[i](x)/f[i](x[i]) )

が成り立つ。

ただし、

f[i](x)

= (Π[j=0..n](x-x[j])) / (x-x[i])

= (x-0)*(x-1)*...*(1)*(-1)*...*(x-n)

とする。

この問題は特殊でx[i]の値が0<=x[i]<=nで与えられていると考えればいい。

よってx[i]をiと置き換えて

P(x) = Σ[i=0...n]( P(i) * f[i](x)/f[i](i) )

ただし

f[i](x)

= (Π[j=0..n](x-j)) / (x-i)

= (x-0)*(x-1)*...*(1)*(-1)*...*(x-n)

となる。

とりあえず、自明だが厄介なケースを取り除いておく。

T<=Nとする。このときP(T)は入力として与えられているので、それを出力するだけ。

なので、以下はT>Nを仮定する。

f[i](T)とf[i](i)がすべてのiについて求まればよい。

f[i](T) = (Π[j=0...n](T-j)) / (T-i)

である。

T>NよりT-j>0が成り立つ。

S=Π[j=0...n](T-j)

として総乗を事前に計算しておけば

f[i](T) = S/(T-i)

のようにO(log(mod))でf[i](T)を求めることができる。

次に、f[i](i)について考えてみる。

f[0](0)をO(N)で求めておく。

f[i](i)からf[i+1](i+1)を計算したい。

f[i](i)

= (i-0)*(i-1)*(i-2)*...*1*(-1)*...*(i-(n-1))*(i-n)

f[i](i+1)

= ( (i+1)-0)*( (i+1)-1)*...*1*(-1)*...*( (i+1)-(n-1))*( (i+1)-n)

f[i](i)とf[i](i+1)の共通点を見てみると、n値の積になっていて、0を除くすべての要素が連続して存在する。

よって1*(-1)から両端にどう延びていくかだけが違いになるが、

前者は左にiまで右にi-nまで、後者は左にi+1まで右にi+1-nまでとなっている。

ここから

f[i](i+1) = f[i]*(i+1) / (i-n)

となる。

これにより、O(log(mod) )でf[i](i+1)を求まる。

以上から、全体で

O(nlog(mod) )

で間に合う。

CS Academy #23 (Div. 2 only) No Prime Sum

Sに含まれる数を頂点とし、その和が素数になるような2値の間に辺を張ったグラフを考える。すべての辺について、端点の少なくとも一方にある数は使わない。いいかえると、使わない数の集合はすべての辺の端点の少なくとも一方を含む。これは頂点被覆。

使わない数を最小にしたいのであった。よって、最小頂点被覆問題が解ければいい。最小頂点被覆問題は簡単に解ける場合がある。二部グラフの最小頂点被覆問題は、二部グラフの最大マッチングをフローで解いたときの残余グラフから簡単に解ける。作ったグラフが二部グラフになっていることを示す。

与えられた数はすべて異なるので2値の和は1+2=3以上であり、3以上の素数は奇数。2値の和が奇数になるのは、一方が奇数であり他方が偶数出る場合に限る。なので、辺の端点の一方は偶数、他方は奇数。

 

配列のswapとvectorのswap

vectorのswap

vector<int> a(N), b(N);
swap(a, b);

このswapの実体はvector::swapでswap(a,b)はO(1)で終わる。DPでメモリを節約するのによくやる。

配列のswap

int a[N] = {}, b[N] = {};
swap(a, b);

先程のコードを配列に変えただけ。実はこちらのswap(a,b)にはO(N)かかる。 この要素数が等しい配列のswap(a,b)は配列の各値を交換している。 ちなみに

int a[N] = {}, b[N+1] ={};
swap(a, b);

のように、2個の配列の要素数が異なる場合、コンパイルエラーになった。