2018-07-10

E1. Median on Segments (Permutations Edition) | Codeforces Round #496 (Div. 3)

数列なので中央値mはちょうど1つだけある。mの位置に注目すると、条件を満たす部分文字列は、mから左へ0以上、右へ0以上の長さだけ伸ばしたものに限られる。

部分文字列がmの左側へl, 右側へrだけ伸ばしたものであるとする。また、m以外の値はmとの大小関係だけわかればよい。

q[i] = 1 (p[i] > mのとき)
q[i] = -1(p[i] < mのとき)

とおく。mの位置をtとおくと $f(a, b) = \sum_{i=a}^{b-1}q_i$ とおくと $0 \leq f(t-l, t) + f(t+1, t+1+r) \leq 1$ であれば条件を満たす。これは、部分文字列の左側と右側合わせて、

(mより大きい値の数) - (mより小さい値の数) = 0 または 1

ということ。

少し変形して $- f(t-l, t) \leq f(t+1, t+1+r) \leq 1 - f(t-l, t)$ と得る。よって事前にf(t +1, t+1+r)をrの総当たりで固定して数えておく。あとはf(t-l, t)も総当たりして、各lについて条件を満たす $f(t+1, t+1+r)$ を数えればいい。

map<int, int> L, R;
    
int N, M;
cin >> N >> M;
vi A(N);
int p = -1;
rep(i, N) {
    cin >> A[i];
    if (A[i] == M)p = i;
}

L[0] = 1;
R[0] = 1;

int x = 0;
for (int i = p - 1; i >= 0; --i) {
    if (A[i] > M)x++;
    else if (A[i] < M)x--;
    L[x] += 1;
}
x = 0;
for (int i = p + 1; i < N; ++i) {
    if (A[i] > M)x++;
    else if (A[i] < M)x--;
    R[x] += 1;
}

ll re = 0;
each(l, L) {
    // l + r = 0
    if (R.count(-l.first)) {
        re += (ll)l.second * R[-l.first];
    }
    // l + r = 1
    if (R.count(1 - l.first)) {
        re += (ll)l.second * R[1 - l.first];
    }
}
cout << re << endl;

2018-07-10

D. Polycarp and Div 3 | Codeforces Round #496 (Div. 3)

ある非負整数が3の倍数かどうかは、各桁の値の和が3の倍数かどうかを調べればいい。なので

dp[i][j] := 「もとの数字の上位i桁まで確定して、今作っている数の桁の和を3で割ったあまりがjであるときの最大の仕切りの数」

のようなDPを解く。

int dp[200005][3];

int main() {
    MEM(dp, -1);
    dp[0][0] = 0;

    string S;
    cin >> S;
    int N = sz(S);

    rep(i, N) {
        int a = S[i] - '0';
        rep(j, 3) if(dp[i][j]!=-1){
            smax(dp[i + 1][(j + a) % 3], dp[i][j] + ((j+a)%3==0));
            smax(dp[i + 1][a % 3], dp[i][j] + (a % 3 == 0));
        }
    }
    int re = -1;
    rep(j, 3)smax(re, dp[N][j]);
    cout << re << endl;
}

2018-07-06

B. Sonya and Exhibition | Codeforces Round #495 (Div. 2)

一人しかいない場合を考えてみる。その人が見る花壇の長さをa, その花壇に含まれるバラの数をx, ユリの数をyとおく。 x+y=aの条件でxyを最大にしたい。 $xy = x(a-x) = -x^{2} + ax = -(x - \frac{a}{2})^{2} + a^{2}/4$ を得る。よってaが偶数の時 $x = \frac{a}{2}$ で最大。 aが奇数のとき $x = \frac{a\pm 1}{2}$ で最大。簡単のため $x \leq y$ とすると、x, yの値は $x = \lfloor a/2 \rfloor , y = \lceil a/2 \rceil$ となる。要するに、バラとユリをできるだけ均等な数にするのが最適。

単純な構成。バラとユリを交互に置くことで、この条件を一人だけでなくすべての人が満たすことができる。

2018-07-04

No.269 見栄っ張りの募金活動 | yukicoder

愚直なDPを考えてみる。

f(i, j, k) = 「i人目まで確定して、前の人がj円払った時、合計金額がk円である場合の数」

これでは間に合わない。

とりあえず、最初の人の募金額を0~Sの範囲で総当たりして固定し見てよう。先の人も含めて、少なくともその額を支払う必要がある。つまり、下図の斜線部は必ず支払われる。

f:id:parukii:20180704140039j:plain

後の人々についても、その時点での支払確定の合計金額について注目することにする。先のDPの合計金額を、先の人も含む斜線部の支払い確定の金額に置き換えれば、前の人の支払った金額j円は情報として不要になる。というのは、この置き換えによって、（前の人の支払った金額+K）円以上ではなく、K円以上の範囲で支払い額を決めればよくなったため。

よって以下のようなDPを得る。

g(i, j) = 「i人目まで確定して、支払い確定の合計金額がj円である場合の数」

$g(i, j) = \sum_{k*(N-i) \leq j} g(i-1, j-k(N-i))$ で求まる。一見したところ全体でO(NS²)ほどの計算量がありそうだが、実際には最悪ケースで10⁹程度の計算量で済み、時間制限が5秒もあるので間に合う。

int N, S, K, M = (int)1e9+7;
cin >> N >> S >> K;
vi cu(S + 1), ne(S + 1);
int p = 0;
while (p*N <= S)cu[p++*N] = 1;
FOR(i, 1, N) {
    fill(all(ne), 0);
    rep(j, S + 1) {
        FOR(k, K, S + 1) {
            int l = j + k * (N - i);
            if (l > S)break;
            ne[l] += cu[j];
            if (ne[l] >= M)ne[l] -= M;
        }
    }
    swap(cu, ne);
}
cout << cu[S] << endl;

2018-07-03

AOJ1132 : Circle and Points

幾何

最適解が2点以上含む場合は、そのうちの2点を通る円でその最適解を必ず構成できる。

最適解を構成する頂点の集合をSとする。(|S|>=2)。Sの外側の点だけを拾って凸包を構成する。ただし、Sの点が一直線上に並ぶ場合は線分を構成する。これをTとおく。Sの点をすべて含むような円で、円周上には点が2個未満であるものを考えてみる。このとき、Tの隣接する2点以上に接してかつ、T上の点がすべて円の外側に出ないように円を動かすことができるはず。よって、この場合も最適解は|S|である。

そこで、与えられた頂点のうち2個を総当たりで選んで固定し、それらを通る円の中心を求め、そこからの距離が1以下の頂点を数えればいい。全体で計算量はθ(N³)となる。

2点A, Bを通る円の中心の求め方は以下の通り。A, Bの中点をMとする。また円の中心をCする。点Cから点Aへの距離は半径の1。線分AMの長さは、線分ABの長さの半分。よって、三角形AMCに三平方の定理を使ってCMの長さが求まる。ABの法線で長さが1であるものを $\vec{n}$ とおく。すると中心Cの座標は $\vec{OC} = \vec{OM} + CM\vec{n}$ より求まる。

2018-07-03

Marked Ancestor (AOJ 2170, JAG Summer 2009)

HL分解 Binary Indexed Tree

ライブラリがあれば楽にとけるやつ。HL分解して、マークしたかどうかはBinary Indexed Treeなどを使うだけ。

vector<vi> G(N);
FOR(i, 1, N) {
    int p;
    cin >> p;
    --p;
    G[p].push_back(i);
}

HLDecomposition hld(G);
// 0ならばマークされていない。
// そうでなければマークされている。
BIT bit(N);
bit.add(hld.id[0], 1);
// 解
ll re = 0;
rep(i, Q) {
    char c;
    int v;
    cin >> c >> v;
    --v;
    if (c == 'M') {
        // マークする
        bit.add(hld.id[v], 1);
    } else {
        // 根までの経路を半開区間の集合として得る
        auto H = hld.goUpToLCA(0, v);
        int p = 0;
        // 半開区間は頂点の深さの降順に並んでいる。
        // どの半開区間(経路の一部)に含まれるかを調べる
        // そのうち、深いもの
        for (; !bit.sum(H[p].first, H[p].second); p++);
        // この半開区間(経路の一部にふくまれている。)
        // 半開区間内では頂点は深さの昇順に並んでいる。
        // マークされている頂点を二分探索で求める。
        int ok = H[p].first, ng = H[p].second;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            // 計算量はO(Nlog(N^2))
            (bit.sum(mid, H[p].second) ? ok : ng) = mid;
        }
        re += hld.ver[ok] + 1;
    }
}
cout << re << endl;

2018-07-02

E: Or Plus Max - AtCoder Regular Contest 100

集合

K番目の解をanswer(K)と表すことにする。

$f(x) = max_{i \lor j = x}(A_{i}+A_{j})$ とおくと $answer(K) = max_{1 \leq x \leq K}f(x)$ が解。

f(x)の条件の部分をもう少し緩くしてみる。

$g(x) = max_{i \lor j \subseteq x}(A_{i}+A_{j})$ とおくと、後者の(i, j)の集合は、前者のそれを含むので $f(x) \leq g(x)$ が成り立つ。更に、 $i \lor j \neq x かつ i \lor j \subseteq x$ のとき $i \lor j \lt x$ が成り立つ。したがって以下が成り立つ。

$answer(K) = max_{1 \leq x \leq K} g(x)$

g(x)が簡単に求まるとしてanswer(K)は $answer(K) \gets max(g(K), answer(K-1))$

g(x)の求め方を考えてみよう。和を最大にするには、 $i \subseteq x$ であるようなA[i]について大きい方から2個を選んで使えばいい。そのためには、単にxの部分集合を列挙しながら2値を更新していく。部分集合の列挙は計算量3^Nなので間に合う。ただし、定数倍が厳しいので注意。2値の更新を雑に書いたらTLEした。あと出力が多いのでprintfを使ってもいいかも。

auto upd = [](pii &a, int x) {
    if (x > a.second) {
        a.second = x;
        if (a.first < a.second)swap(a.first, a.second);
    }
};

int N;
cin >> N;
int M = 1 << N;
vi A(M);
rep(i, M) cin >> A[i];
int re = 0;
FOR(S, 1, M) {
    pii ma(0, 0);
    int T = S;
    do {
        upd(ma, A[T]);
        T = (T - 1)&S;
    } while (S != T);
    smax(re, ma.first + ma.second);
    cout << re << endl;
}