AtCoder ARC 073 Ball Coloring
細かくコメント書いてみた。
/* 2個の配列u,vを値(u[i], v[i])でソートする。 */ template<class S, class T> void psort(vector<S> &u, vector<T> &v, bool isGreater); int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vll X(N), Y(N); rep(i, N) { cin >> X[i] >> Y[i]; // 簡単のためX[i]<=Y[i]とする if (X[i] > Y[i])swap(X[i], Y[i]); } /* 最大値と最小値が同じ色になるかどうかで場合分けする とりあえず、最大値と最小値が異なる色になる場合について 最大値を含む方は、大きい数を貪欲に 最小値を含む方は、小さい数を貪欲に 選ぶ。 なお、最小値と最大値がそれぞれちょうど1個ずつであってかつ同じ袋に入っている場合は 同じ色にできない。 */ ll rma = 0, rmi = INT_MAX, bma = 0, bmi = INT_MAX; rep(i, N) { smax(rma, X[i]); smin(rmi, X[i]); smax(bma, Y[i]); smin(bmi, Y[i]); } // 解(暫定) ll ans = (rma - rmi)*(bma - bmi); /* (X[i],Y[i])でソートする m, Mが同じ色に含まれる。 (m, M)=(rmi, bma)とする。こちらは、入力全体の最小値と最大値を含んでいる。 他方の最小、最大は (z, Z)とする。 zを昇順で固定する。ただし、Zはできるだけ小さい方がいい。 zより小さい値はどんどん取り除いていく尺取。要するに、(z, Z)に含まれる値hは h>=zかつできるだけ小さいのが好ましい。 しゃくとりみたいな感じでやる。 */ psort(X, Y); // 最小値、最大値の(m, M)内の数 int nm = 0, nM = 0; ll red = bma - rmi; // <値, id> set<pair<ll, int> > st, ts; rep(i, N) { // 袋stには(z, Z)が含まれている。 // (全体)-stには(m, M)が含まれていてほしい st.insert(mp(X[i], i)); // すべてのボールの値をzの候補として昇順で見たいのでtsに突っ込んでいく。ソートされる。 ts.insert(mp(X[i], i)); ts.insert(mp(Y[i], i)); if (Y[i] == rmi)nm++; if (Y[i] == bma)nM++; } /* (z, Z)を含む色について 値aを取り除いてbを挿入 */ auto f = [&](ll a, ll b, int k) { if (X[k] != Y[k] && st.count(mp(a, k))) { st.erase(mp(a, k)); st.insert(mp(b, k)); if (a == rmi)nm++; if (a == bma)nM++; if (b == rmi)nm--; if (b == bma)nM--; } }; [&] { each(p, ts) { /* zを最小値として固定 */ int k = p.second; ll z = p.first, w = X[k] ^ Y[k] ^ z; f(w, z, k); while (sz(st) && st.begin()->first < z) { ll u = st.begin()->first, v; int l = st.begin()->second; v = u ^ X[l] ^ Y[l]; // すべての値をz以上にすることは不可能である。 if (v < z) { return; } f(u, v, l); } /* 他方にm,Mが含まれている場合のみ計算 */ if (nm > 0 && nM > 0) { smin(ans, red*(st.rbegin()->first - st.begin()->first)); } } }(); cout << ans << endl; }
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値の和が奇数になるのは、一方が奇数であり他方が偶数出る場合に限る。なので、辺の端点の一方は偶数、他方は奇数。