技術室奥プログラミングコンテスト G - おおきなかずを作った (I made a huge number)

技術室奥プログラミングコンテストに参加しました。ABCDEだけ解くという普通の人でした。
蟻本の chapter 4 (上級編)まともに読んでないので suffix array とか言われてもさっぱりで, 満点解法を紹介するのは時間がかかりそうなのでとりあえず部分点解法だけ紹介しときます。

問題

G: おおきなかずを作った (I made a huge number) - 技術室奥プログラミングコンテスト | AtCoder

解法

dp で解きます。

dp[i] = (i 番目の文字から N 番目の文字列のみを考える場合, i 番目の文字列で最低限必要な桁の数)

とします。すると, dp の遷移(N, N-1, ..., 0 と dp を更新する)は

・i+1 番目の文字列からそのまま桁数を増やす
dp[i] = min(dp[i], dp[i+1]+1)

以下は i 番目の文字が 0 でない場合に可能(i 番目を区切りに新しい数を作る)
・i 番目からの dp[i] 文字が, i-dp[i] 番目からの dp[i] 文字より小さい場合は, i-dp[i] 番目から先の数字の桁数を dp[i] にすることが可能で,
dp[i-dp[i]] = min(dp[i], dp[i-dp[i]])

・i 番目からの dp[i] 文字よりも i-dp[i]-1 番目からの dp[i]+1 文字のほうが必ず数として大きいので,
dp[i-dp[i]-1] = min(dp[i-dp[i]-1], dp[i]+1)

これを使って dp を更新していきます。

const int MAXN = 10010;
int N;
const int INF = 1e9;
string s;
int dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    if (N > MAXN) return 0;
    cin >> s;
    for (int i = 0; i < N; i++) dp[i] = INF;
    for (int i = N-1; i >= 0; i--) {
        dp[i] = min(dp[i], dp[i+1]+1);
        if (i-dp[i] >= 0 && s[i] != '0') {
            if (s.substr(i-dp[i], dp[i]) > s.substr(i, dp[i])) {
                dp[i-dp[i]] = min(dp[i-dp[i]], dp[i]);
            } else if (i-dp[i]-1 >= 0) {
                dp[i-dp[i]-1] = min(dp[i-dp[i]-1], dp[i]+1);
            }
        }
    }
    cout << dp[0] << endl;
    return 0;
}