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

解法

yosupo 先生のコードを写経した。

Trie 木を作って、その桁で終わるくじの当選金と、その桁より後ろの桁で終わるくじの当選金の最高値をそれぞれのノードに持たせる。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template <typename T>
class Trie {
 private:
  vector<Trie*> ch;
  T having, max_below;
  char base;
  Trie() {}

 public:
  Trie(int k, char b) {
    this->base = b;
    ch.assign(k, nullptr);
    having = max_below = 0;
  }

  T add(string s, int i, T d) {
    if (i == s.size()) {
      having += d;
      return max_below + having;
    }

    int c = s[i] - base;
    if (ch[c] == nullptr) ch[c] = new Trie(ch.size(), base);
    max_below = max(max_below, ch[c]->add(s, i + 1, d));
    return max_below + having;
  }

  T get() { return max_below + having; }
};

int main() {
  Trie<ll> trie(10, '0');
  int N;
  cin >> N;
  for (int i = 0; i < N; ++i) {
    int a, b;
    cin >> a >> b;
    string a_str = to_string(a);
    reverse(a_str.begin(), a_str.end());
    trie.add(a_str, 0, b);
    cout << trie.get() << endl;
  }
}