Codeforces Round #263 (Div. 2)

http://codeforces.com/contest/462 日本人writer回でした。

結果は ooo-- で 1577 (-53), expert Rank: 551 でした。ここ数ヶ月間安定してしまっています。

A

グリッドにoかxが書かれている。上下左右に隣り合うoのマスの数が全てのマスで偶数になっているか判定しなさい。

グリッドは小さいので普通に数えた。

int main(){
    int n;
    while (cin >> n){
        vector<string> g(n);
        rep(i, n){
            cin >> g[i];
        }

        bool res = true;
        rep(y, n)rep(x, n){
            int dx[] = { 1, 0, -1, 0 };
            int dy[] = { 0, 1, 0, -1 };
            int t = 0;
            rep(i, 4){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n){
                    if (g[ny][nx] == 'o') t++;
                }
            }
            if (t & 1) res = false;
        }

        cout << (res ? "YES" : "NO") << endl;
    }
}

B

長さ の文字列 が与えられる． 番目の文字 に割り振られるスコアは、 に含まれる の個数とする。文字列から 個の文字をとるとき、それらのスコアの合計を最大化せよ。

読解に時間がかかった。無駄にpairにしたけど、どの文字を選ぶかという情報は不要でその個数さえわかればよい。個数がそのまま得点になるので貪欲に大きいもの 個とる。

typedef pair<char, ll> mci;
ll n, k;
int main(){
    while (cin >> n >> k){
        string s; cin >> s;
        map<char, ll> m;
        rep(i, n){
            m[s[i]]++;
        }
        vector<mci> v;
        for (char i = 'A'; i <= 'Z'; i++){
            v.push_back(make_pair(i, m[i]));
        }
        sort(all(v), [](mci const& a, mci const& b){
            if (a.second != b.second) return a.second > b.second;
            return a.first < b.first;
        });
        ll ans = 0;
        rep(i, v.size()){
            if (k == 0) break;
            ll t = min(v[i].second, k);
            ans += t * t;
            k -= t;
            // cout << k << endl;
        }
        // cout << "lsfkj";
        cout << ans << endl;
    }
}

C

はじめのスコアを0として、入力される整数のグループをTとAで交互に受け渡しする。

• Tは受け取ったグループに含まれる整数の和をスコアに足し、それをそのままAに渡す。
• Aは受け取ったグループを2つに分割する。分けた後のグループの要素数が1だったらそれを捨てる。1より大きいならAに渡す。

初めにTに渡される。最適な操作をし続けたとき、全ての整数を捨てるまでに得られるスコアの最大値を求めよ。

最終的にグループ内のすべての数字は、それだけを含む要素1のグループに分割される。それを併合するときにスコアが得られると考え、グループが1つだけになって併合できなくなるまでこれを続ける。和の大きなグループは先に併合して再利用したほうが得なので大きい方からグループを2つ選んで併合するという貪欲法をとる。これはハフマン符号化のアルゴリズムと全く同じなのでpriority_queueを使って全く同じように実装する。

最近たまたま二分ヒープを実装したのもあって（競技プログラミング以外で！）それを使うアルゴリズムがまず思いついた。けど上位の人はソートしてループ回すだけの方法で解いてます。

int型のオーバーフローで大量に落ちていたけど自分は提出直後に気づいて再提出したので大丈夫だった ≡( ε:)

ll n;

ll solve(vi v){
    priority_queue<ll> q;
    rep(i, v.size())q.emplace(v[i]);
    ll ans = 0;
    while (q.size()){
        if (q.size() == 1){
            ans += q.top();
            q.pop();
            break;
        }
        else{
            ll t = 0;
            t += q.top(); q.pop();
            t += q.top(); q.pop();
            ans += t;
            q.push(t);
        }
    }
    return ans;
}

int main(){
    while (cin >> n){
        vi v(n); rep(i, n)cin >> v[i];
        sort(all(v));
        cout << solve(v) << endl;
    }
}

D

木DPを書くのは初めてだったから実装が間に合わなかった…