Codeforces Round #260 (Div. 2) - tubo28のブログ

ooo-- = 1630 (+90), expert Rank: 382 でした。それなりの速度でコンスタントに3問解ければDiv1に行ける雰囲気ですね。

Cをもっと速く解いてEに時間を掛けたかったです。Dは解ける気がしなかったので無視しましたがTrie木(トライ木と読む)というデータ構造を使えれば良かったらしいです。

A

読解に苦労したけど ${a_i \le a_j}$ かつ ${b_i > b_j}$ になるような組があるか見ればばいい。

int main(){
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    rep(i, n){
        int a, b;
        scanf("%d %d", &a, &b);
        v[i] = make_pair(a, b);
    }
    sort(all(v));

    bool ans = true;
    rep(i, n - 1){
        if (v[i].second >= v[i + 1].second){
            ans = false;
            break;
        }
    }
    if (ans){
        cout << "Poor Alex";
    }
    else{
        cout << "Happy Alex";
    }
    cout << endl;
}

B

以下 ${\mod 5}$ で考えます。フェルマーの小定理より ${x = 1,2,3,4}$ に対して ${x^{n} = x^{n\%4} }$ です。

${n \% 4 = 0 }$ のとき ${ 1^{0} + 2^{0} + 3^{0} + 4^{0} = 4 }$
${n \% 4 = 1 }$ のとき ${ 1^{1} + 2^{1} + 3^{1} + 4^{1} = 10 = 0 }$
${n \% 4 = 2 }$ のとき ${ 1^{2} + 2^{2} + 3^{2} + 4^{2} = 1^{2} + 2^{2} + (-2)^{2} + (-1)^{2} = 0 }$
${n \% 4 = 3 }$ のとき ${ 1^{3} + 2^{3} + 3^{3} + 4^{3} = 1^{3} + 2^{3} + (-2)^{3} + (-1)^{3} = 0 }$

制約が異様に大きいですが4で割った余りを調べるには下2桁だけ見ればいいです。

int solve(string s){
    if (s.size() >= 2){
        s = s.substr(s.size() - 2);
    }
    stringstream ss(s);
    int t; ss >> t;
    if (t % 4 == 0){
        return 4;
    }
    else{
        return 0;
    }
}

int main(){
    string s;
    while(cin >> s)
        cout << solve(s) << endl;
}

C

数列 ${ a_i }$ の中に ${ k }$ が現れる回数を ${ c_k }$ とし、 ${a_i}$ が小さい順に取っていくことにします。 ${k}$ を取るか判断するとき、 ${(k+1) \times c_{k+1} }$ を取るのと ${k \times c_k}$ を取るのとで最終的に得られるスコアの大きい方を選べば良いことになります。

${ f(i,false) := }$ ${i-1}$ 番目を取ったときの ${i}$ 番目以降で取れるスコアの最大値
${ f(i,true) := }$ ${i-1}$ 番目を取らなかったときの ${i}$ 番目以降で取れるスコアの最大値

という漸化式の ${ f(0,true) }$ をメモ化再帰で求めました。

1次元配列のループDPで求める方法もあるようです。

ll cnt[100000 + 100];
ll dp[100000 + 100][2];

ll M;

ll solve(ll k, bool f){
    if (i == M + 2) return 0;

    ll & res = dp[k][f];
    if (res != -1) return res;
    res = 0;

    // kを取る場合
    // k+1は取れなくなるので 一旦cnt[k+1]を0にする。
    ll t = cnt[k + 1];
    cnt[k + 1] = 0;
    res = max(res, cnt[k] * k + solve(k + 1, 0));
    cnt[k + 1] = t;

    // kを取らない場合
    res = max(res, solve(k + 1, 1));

    return res;
}

int main(){
    ll n;
    while (cin >> n){
        memset(cnt, 0, sizeof(cnt));
        memset(dp, -1, sizeof(dp));
        M = 0;
        rep(i, n){
            ll t; cin >> t;
            cnt[t]++;
            M = max(M, t);
        }
        cout << solve(0, 1) << endl;
    }
}