技術室奥プログラミングコンテスト G: おおきなかずを作った

問題

tkppc.contest.atcoder.jp

解法

動的計画法で後ろから数字の桁数を決めていく。この時、s[i, k] と s[j, k] の文字列の大小関係を比較したいが、普通にやるとO(N)かかってしまう。

そこでSA-ISを使うのが想定解法っぽい。
mayokoex.hatenablog.com

が、SA-ISは理解できなかったので、ローリングハッシュで文字列の大小関係をO(logN)で計算する。
topcoder.g.hatena.ne.jp

ライブラリはここからコピーした。
algoogle.hadrori.jp

コード

このコードでは安心できないハッシュを使っていて、オーバーフローを利用してmodを省略するなどして無理やりACしている。

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <cassert>
#include <sys/time.h>
using namespace std;

typedef long long ll;
const int INF = 1e9;

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

class RollingHash {
 private:
  vector<long long> mod;
  void init() {
    // mod.push_back(999999937LL);
    mod.push_back(1000000009LL);
  }
  const long long base = 1000000007LL;
  int n;
  vector<vector<long long> > hs, pw;
  RollingHash() {}

 public:
  int cnt = 0;

  RollingHash(const string& s) : n(s.size()) {
    init();
    hs.resize(mod.size()), pw.resize(mod.size());
    for (int i = 0; i < mod.size(); i++) {
      hs[i].assign(n + 1, 0);
      pw[i].assign(n + 1, 0);
      hs[i][0] = 0;
      pw[i][0] = 1;
      for (int j = 0; j < n; j++) {
        // pw[i][j + 1] = pw[i][j] * base % mod[i];
        // hs[i][j + 1] = (hs[i][j] * base + s[j]) % mod[i];
        pw[i][j + 1] = pw[i][j] * base;
        hs[i][j + 1] = (hs[i][j] * base + s[j]);
      }
    }
  }

  inline long long hash(int l, int r, int i) {
    // return ((hs[i][r] - hs[i][l] * pw[i][r - l]) % mod[i] + mod[i]) % mod[i];
    return hs[i][r] - hs[i][l] * pw[i][r - l];
  }

  inline bool match(int l1, int r1, int l2, int r2) {
    bool ret = 1;
    for (int i = 0; i < mod.size(); i++)
      ret &= hash(l1, r1, i) == hash(l2, r2, i);
    return ret;
  }

  int lcp(int i, int j) {
    int l = 0, r = min(n - i, n - j) + 1;
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if (match(i, i + m, j, j + m))
        l = m;
      else
        r = m;
    }
    return l;
  }
};

void solve() {
  int N;
  string s;
  cin >> N >> s;

  RollingHash comic_lo(s);

  vector<int> digits(N + 1, INF);
  digits[N] = 0;
  for (int i = N - 1; i >= 0; i--) {
    digits[i] = min(digits[i], digits[i + 1] + 1);

    int prev = i - digits[i];
    if (prev < 0 || s[i] == '0') continue;

    int k = comic_lo.lcp(prev, i);

    if (k < digits[i] && s[prev + k] > s[i + k]) {
      digits[prev] = min(digits[prev], digits[i]);
    } else if (prev - 1 >= 0) {
      digits[prev - 1] = min(digits[prev - 1], digits[i] + 1);
    }
  }
  cout << digits[0] << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}