300 点！？？？

問題概要

'0' 〜 '9' および '?' からなる文字列 S が与えられる。

文字列のニコニコレベルとは、連続部分列であって "2525... 25" となっているものの最長の長さとして定義される。

S の '?' に '0' 〜 '9' を当てはめる方法をすべて考えたとき、ありうるニコニコレベルの最大値を求めよ。

制約

$1 \le |S| \le 10^{5}$

考えたこと

嫌なケースとして

252?52525

みたいなものもありうる。左側の "252" 的には ? = 5 であってほしいが、右側の "52525" 的には ? = 2 であってほしい。この場合は右側からの要望をかなえる方がよくなる。

つまり、こういう嫌な状況があるから雑な Greedy だと簡単に嘘になってしまいそうである。

こういうときは何も考えずに DP するのがいい感じではある。

dp[ i ][ 2 か 5 か ] := i 文字目を '2' か '5' にしたときについて (2 のとき二番目の添字を 0、5 のとき 1 とする)、i 文字目以降が最長で何文字分について 2 と 5 を交互に続けられるか

とする。

S[ i ] == '2' なら、chmax(dp[ i ][ 0 ], dp[ i + 1 ][ 1 ] + 1)
S[ i ] == '5' なら、chmax(dp[ i ][ 1 ], dp[ i + 1 ][ 0 ] + 1)
S[ i ] == '?' なら、上の 2 つの更新を両方やる

という感じで DP テーブルを更新できる。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
    string S; cin >> S;
    int N = (int)S.size();
    vector<vector<int> > dp(N+1, vector<int>(2, 0));
    for (int i = N-1; i >= 0; --i) {
        if (S[i] == '2') chmax(dp[i][0], dp[i+1][1] + 1);
        else if (S[i] == '5') chmax(dp[i][1], dp[i+1][0] + 1);
        else if (S[i] == '?') {
            chmax(dp[i][0], dp[i+1][1] + 1);
            chmax(dp[i][1], dp[i+1][0] + 1);
        }
    }
    int res = 0;
    for (int i = 0; i < N; ++i) chmax(res, dp[i][0]/2*2);
    cout << res << endl;
}