mayoko’s diary

プロコンとかいろいろ。

東京大学プログラミングコンテスト2014 E:宝くじ

東京大学プログラミングコンテスト2014に参加してきました。結果はAとCが通ってFが微妙な点数になって後適当に部分点とかなり酷い結果でした。辛い・・・

問題:E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder

解法:Trie木というのがあるらしいのでそのライブラリをちょっと改変すると答えを求めてくれる。こういうのなんとなくわかっても知らないとできないな・・・
以下ソースコード

struct Trie {
    ll value;
    ll cmax;
    Trie *next[10];
    Trie() {fill(next, next+10, (Trie*)0);}
};

Trie *root = new Trie;

ll getValue(ll a, ll b, Trie* r) {
    if (a == 0) {
        r->value += b;
        return r->value + r->cmax;
    }
    ll d = a%10;
    if (!r->next[d]) r->next[d] = new Trie;
    ll m = getValue(a/10, b, r->next[d]);
    r->cmax = max(r->cmax, m);
    return r->cmax+r->value;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        cout << getValue(a, b, root) << endl;
    }
    return 0;
}