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');
}
広告を非表示にする

Star sky | Codeforces #427 (Div. 2)

// 思いつき方
// 明るさが最大11種類しかないことに注目

// s, x, y
// 部分和sm[s][x][y2]-sm[s][x][y1]は
// 初期の明るさsの星のうち、
// (x, y1), (x, y1+1), ... , (x, y2-1)
// にある星の数
int sm[11][101][101];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q, c;
    cin >> n >> q >> c;
    rep(i, n) {
        int x, y, s;
        cin >> x >> y >> s;
        sm[s][x][y]++;
    }
    // sm[i][x]ごとに部分和を計算する
    rep(i, c + 1)rep(x, 101)rep(y, 100)sm[i][x][y + 1] += sm[i][x][y];

    while (q--) {
        int t, X1, Y1, X2, Y2, ans = 0;
        cin >> t >> X1 >> Y1 >> X2 >> Y2;

        for (int x = X1; x <= X2; ++x) { // 矩形内のすべてのx座標について
            rep(s, c + 1) {
                // 初期の明るさがsである星は
                // t秒後には
                // (s+t) % (c+1)の明るさになる。
                int bri = (s + t) % (c + 1);
                // 明るさ * 星の数
                ans += bri * (sm[s][x][Y2] - sm[s][x][Y1 - 1]);
            }
        }
        cout << ans << endl;
    }
}
広告を非表示にする

Round Subset | Educational Codeforces #26

f(i, x, y) 

をi番目までの値のうちx個を使って

z * 5^x * 2^y を作れるとして、その最大のy

ただし、2∤zかつ5∤z

これをDPで解く。

つまり、素因数分解したときの形で

5の次数は添え字として、2の次数は最大値として計算していけばいい。

 

ちなみに5の次数は

log5(10^18) < 26 より

25 * 200 = 5000 が最大

 

広告を非表示にする

Restricted Permutations | CS Academy #40 (Div. 2 only)

値1からNまで順にみていき、もともと空の配列のどこかに1つずつ挿入する。

今、1~K-1の値からなる順列のどこかにKを挿入したい。Kが挿入できる位置は、K-1の位置だけに依存する。(K+1は順列内にはないので)

よって、以下のようなDPを考えればよい。

dp[i][j]

= 値iまで含む順列であって値iがjにあるような順列の数

広告を非表示にする

Switch the Lights | CS Academy #40 (Div. 2 only)

まず1番目のスイッチを押すかどうか決める。1番目のライトをON/OFFするのは1番目のスイッチだけなので、1番目のライトがONならば押さない。OFFならばスイッチをおす。これで1番目のスイッチを押すかどうか決めて処理した。以後、1番目のスイッチは考えない。

2番目のスイッチを押すかどうか考える。1番目のスイッチを除けば2番目のライトのON/OFFするのは2番目のスイッチだけなので、2番目のライトを見て決める。

以下、同様にN番目のライトまで見ていけばいい。

広告を非表示にする

Move the Bishop | CS Academy #40 (Div. 2 only)

 

(1) (R1+C1) ≢ (R2+C2) (mod 2) の場合

移動できない。市松模様の同じ色しか移動できない。

以下、(1)でないと仮定する。

(2)  (R1,C1) = (R2,C2)の場合

0回

(3) (R1, C1)が(R2,C2)の対角線上にある場合

1回

(4) (R1, C1)が(R2,C2)の対角線上にない場合

まず、(R2,C2)の対角線上にある(R2,C2)でないある点まで移動する。次に、(R2,C2)まで移動する。

2回

広告を非表示にする

SRM 717 DIV1 250: ScoresSequence

i!=jとしたとき辺(i, j)または(j, i)のどちらか1つだけを必ず使いたい。すべての異なる2値{i, j}でそうしたい。最大フローっぽいが、出次数の制約も考えなければならない。出次数の制約より、x!=iとして(x, i)であるような辺はs[i]個以下でなければならない。このようにiへ向かう辺を使う場合というのを1個の頂点で表し、そこへ辺(x, i)を向ける。下の図のようなグラフで最大フローをやる。

f:id:parukii:20170701102811j:plain

広告を非表示にする