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値の和が奇数になるのは、一方が奇数であり他方が偶数出る場合に限る。なので、辺の端点の一方は偶数、他方は奇数。