解きました。最近は良くも悪くも問題の点数に惑わされないようにしたい日々です。

問題概要

'25'を0回以上繰り返した文字列をニコニコ文字列という。
与えられる文字列Tは0~9の数字と?からなる。
?を0~9の好きな数字に置き換える時、与えられた文字列Tの中の最長のニコニコ文字列を求めたい。

制約

1≦|T|≦10⁵

考えたこと

ニコニコ文字列では先頭が必ず2から始まるので文字列の中の25を別の文字の置き換えて、?の部分は2と5の繰り返しになり先頭は2か5の2通りなのでなんとかなるかなと考えていましたが考察に詰まりました。

先輩からアドバイスをもらったところ

1 ?がなく0~9の数字だけの場合をまず考えて見たらどうか
2 文字列のある位置までのニコニコ文字列の長さがわかった時、次の2文字が25だったらニコニコ文字列の長さは2増えるよね

要はDPで解くことができるのではないかということですね。
「dp[ i ] : =i-1文字目までのニコニコ文字列の長さ」といった感じの式です。
?が含まれている場合でも適切に条件分岐をすれば大丈夫です。
文字列のi文字目が2の時、i+1文字目が5または?の時に遷移。
文字列のi文字目が?の時、i+1文字目が5または?の時に遷移。

この条件は一つにまとめられますが僕はACした後に気がつきました。
後はdp配列の中で最大の値を求めればそれが答えとなります。
提出コード:Submission #2947865 - 第3回ドワンゴからの挑戦状予選