C: ウサギとカメ | AtCoder Regular Contest 025

ダイクストラ法っぽいことをする。

(時間、誰(ウサギ、カメ), 場所, 始点)

のようなタプルを優先順位付きキューに入れていく。

まず、

場所=始点、時間0で両者をすべての頂点からスタートさせる。

以降、各始点からの最短経路だけを考える。

今いる場所と始点が異なるとき、カメはその地点のカウンタを1個増やす。

今いる場所と始点が異なるとき、ウサギはカメのカウンタを数える。つまり、先に今いる場所に来た経路を数える。ただし、カメも同じスタート地点から来ている経路だけは取り除く。

全体で

O(NMlog(M))

の時間でなんとか間に合う。

 

広告を非表示にする

C: 蛍光灯 | AtCoder Regular Contest 026

蛍光灯が途切れずに照らしている範囲を左端から右端へ伸ばしていこう。

最適解では、手前で使った蛍光灯をi、次の蛍光灯をjとすると、l[i]<l[j] が成り立つ。なので、事前に蛍光灯をlの昇順にソートしておく。

dp[x] = 0からxまでが途切れずに照らされているときの最小コスト

とする。dp[L]が解。

はじめ

dp[0] = 0である。

蛍光灯をソートされた順にみよう。いま、i番目の蛍光灯の使用を考る。dp[r[i]]が更新されるかもしれない。

蛍光灯は[l[i], r[i]] の範囲を照らすので、

前の範囲 => (重複) => [l[i], r[i]]

のようになっていれば、左端からr[i]まで蛍光灯iを使うことで照らせる。

つまり、その時のコストは

今までのコスト + 蛍光灯iのコスト

= min[l[i]<=x<r[i]](dp[x]) + c

となる。

実装には点更新できるRMQ(セグメント木)で。

広告を非表示にする

yukicoder #563 : 超高速一人かるた large

解説付き

const int MO = (int)1e9 + 7;
string S[2001];
RollingHash rh[2001];
int f[2001][2001];
mint ans[2001], fact[2001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    rep(i, N) {
        cin >> S[i];
    }

    // 接頭辞の問題=>ソート
    // これで、接頭辞が似ている文字列ほど近くになる。
    sort(S, S + N);
    rep(i, N) {
        rh[i] = RollingHash(S[i]);
    }

    // f[i][j]はiとjを区別するのに読み上げる文字数
    // ただし、f[i][i] = 1
    rep(i, N)rep(j, N) {
        if (i == j)f[i][j] = 1;
        else if (i > j)f[i][j] = f[j][i];
        else {
            // ローリングハッシュで接頭辞が何文字一致しているか調べる
            int ok = 0, ng = min(sz(S[i]), sz(S[j])) + 1, mid;
            while (ng - ok > 1) {
                mid = (ok + ng) / 2;
                (rh[i].getHash(0, mid) == rh[j].getHash(0, mid) ? ok : ng) = mid;
            }
            f[i][j] = ng;
        }
    }
    // 都合
    f[N - 1][N] = 1;

    auto C = combinations(N + 10, MO);

    /*
    すべてのカードの集合について、読み上げられる文字数は読み札の順番によらない。
    なので読み札の順番をインデックス順にする。
    */
    for (int ba = 1; ba <= N; ++ba) {
        mint sm;
        // 前に取ってないのがa
        // つまり、a+1,a+2,...,a+ba-1はすべて取った状態。
        // a+baを次に取る
        for (int a = 0; a + ba < N; ++a) {
            // a+baから見て
            // 手前はaが一番近い。なので接頭辞が近い。
            // 後ろはまだ見てないので必ず残っている。これは直後が一番近い。
            sm += max(f[a][a + ba], f[a + ba][a + ba + 1]);
        }
        // 全体でK個取る
        // 少なくともaは取ってないのでK<=N-1
        for (int K = ba; K <= N - 1; ++K) {
            // a+1,a+2,...,a+ba-1,a+baは確定している。
            // それとaは使ってはいけない。
            // このとき
            // N-ba-1個の中からK-ba個選ぶ
            if (ba != N)ans[K - 1] += sm * C[N - ba - 1][K - ba];
        }
    }

    // 前にとっていないカードが存在しない
    // つまり、いまのところすべてのカードをとっている場合
    // 0,1,...,b-1まではすべて取った状態
    // bを取るときのコストをしらべる
    for (int b = 0; b < N; ++b) {
        // 全部でK枚とる
        for (int K = b+1; K <= N; ++K) {
            // 直後のカードとだけ比較。前のカードは残っていないので
            // 0からbまで全部取った状態から残りを選ぶ。(C[N-b-1][K-b-1])
            ans[K - 1] += mint(f[b][b + 1]) * C[N - b - 1][K - b - 1];
        }
    }

    // 解(パターンとの積)には並び順も必要。階乗
    fact[0] = 1;
    rep(i, N)fact[i + 1] = fact[i] * (i + 1);
    rep(i, N)cout << ans[i] * fact[i + 1] << endl;
}
広告を非表示にする

yukicoder #562: 超高速一人かるた small

p(T)を

読み上げられたカードの集合がTであるときのパターン数とする。

p(Φ) = 1

p(T(!=Φ)) = Σ[i ∊ T] ( p(T-{i}) )

で簡単に求まる。

e(T)を読み上げられたカードの集合がTであるときの

期待値 と パターン数の積とする。

E[K] * P[N,K] = Σ[T⊆読み札, |T|=K](e(T))

が成り立つ。

これらは、すべてのパターンについて、読み上げられた文字の数の和をとったもの。

なので、

e(T)

= Σ[j∊T](e[T-{j}] + p[T-{j}] * (T-{j}の後でjの読み札を見たときの読み上げる文字数)

で求まる。

T-{j}の次がjとして、そのとき読み上げられた文字数を求めるには、事前に

f[i][j] = iをjと区別するのに必要な最低の読み上げ文字数

を計算しておけば楽。これは愚直に求められる。

 

L = max(|S[i]|)として

事前計算でO(LN^2), DPの計算にO(2^N * N^2)の時間で間に合う。 

 

広告を非表示にする

yukicoder #557: 点対称

各桁に使える数は0,1,6,8,9のいずれかであってその特徴は以下のようになる。

 

                  先頭可    先頭不可

中心可      1 8           0

中心不可   6 9

 

先頭からceil(N/2)桁が決まると、残りfloor(N/2)桁は1通りに定まる。なので先頭からceil(N/2)桁だけ考える。場合分けする。

<1> Nが偶数の時

先頭の桁は1,8,6,9のいずれかの4通り。

続くceil(N/2)-1 = (N-2)/2 桁は 1,8,0,6,9の5通り。

よって

4*5^((N-2)/2) 通り

 

<2> Nが3以上の奇数の場合

先頭の桁は1,8,6,9のいずれかの4通り。

中心の桁は先頭ではないので1,8,0の3通り。

間の

ceil(N/2)-2 = (N-3)/2 桁は1,8,0,6,9の5通り。

よって

4*3*5^((N-3)/2) 通り

 

<3>Nが1桁の場合

1, 8の2通り

広告を非表示にする

yukicoder #568: じゃんじゃん 落とす 委員会

SAの値が決まっているとする。

f[i](l,r)をB以外の問題について正答数がiとしたときのl<=B[j]<rとなるようなB[j]の数とする。(0<=i<5)

f[i](l,r)はBinary Indexed Treeでもっておく。

 

SAを100001とおくと、誰もA問題に正答できないので、B問題を無視すると参加者iの正答数はx[i]となる。

B問題の難易度を固定すれば各自の正答数は確定する。y問以上正答した人の数は、

(B問題以外でy問以上正答した人の数) + (B問題を正答してちょうどy問正答した人の数)

= Σ[i<=y](f[i](0, 100002)) + f[y-1](b, 100002)

で求められる。

このやり方で、2問以上正答する人がM人以上となるようなB問題の難易度の最小値をもとめる。このときの3問以上正答する人の数が解候補になる。

 

A問題の難易度を変えていこう。

今、A問題の難易度がSA+1とする。A問題の難易度をSAに変えると、

A[i]=SAとなるような回答者iの正答数が1増える。よって

f[X[i]](B[i], B[i]+1)が1減って

f[X[i]+1]](B[i], B[i]+1)が1増える。

あとは同様に解候補を求めればよい。

広告を非表示にする

Palindromic characteristics | Codeforces Round #427 (Div. 2)

const int R = 14;
// isp[k-1][l][r]は
// 部分文字列s[l, r)が
// k-回文であるかどうかを表す
bitset<5001> isp[R][5000];

// 部分文字列s[l, r)のハッシュ値
pii ha[5001][5001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n = sz(s);
    // 長さ1の文字列は1-回文
    rep(i, n)isp[0][i][i + 1] = isp[0][i][i] = 1;
    RollingHash rh(s);
    rep(i, n)FOR(j, i + 1, n + 1)ha[i][j] = rh.getHash(i, j);
    // ans[k-1]はk-回文の個数
    vi ans(n);
    // とりあえずながさ1の文字列はを1-回文として数える
    ans[0] = n;
    // 1-回文を全部調べる。すでにある回文の左右が同じ文字なら、更に長い回文を作れる
    for (int len = 0; len <= n-2; ++len) {
        for (int i = 1; i + len <= n - 1; ++i) {
            if (isp[0][i][i + len] && s[i - 1] == s[i + len]) {
                isp[0][i - 1][i + len + 1] = 1;
                ans[0]++;
            }
        }
    }

    // 実はk-回文に対してk+1回文の長さは2倍以上になるから
    // 2^(k-1) <= 文字列の長さ
    // くらいまで見ればいい。
    for (int k = 1; k < R; ++k)rep(i, n)FOR(j, i + 2, n + 1) {
        int len = (j - i) / 2;
        // 条件をそのまま見る。部分文字列の比較はローリングハッシュで
        if (isp[k - 1][i][i + len] && isp[k - 1][j - len][j] && ha[i][i + len] == ha[j - len][j]) {
            isp[k][i][j] = 1;
            ans[k]++;
        }
    }

    rep(i, n)cout << ans[i] << (i != n - 1 ? ' ' : '\n');
}
広告を非表示にする