読者です 読者をやめる 読者になる 読者になる

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

要復習 AtCoder 競技プログラミング

解法

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;
  }
}