yukicoder No.528 : 10^9と10^9+7と回文
No.528 10^9と10^9+7と回文 - yukicoder
愚直に頑張って数えました。
文字列をs、長さをnとします。
前処理として、[1, n)桁までの回文数を数えます。
これは一番左の桁が[1, 10)、他が[0, 10)の個数を数えれば良いです。
次にn桁ある場合、
左からi番目の桁がdだったとします。
n桁目（i==0）を除き、この桁が[0, d)の値を持つ場合は下の桁がどんな値も取り得ます（n未満になるので）。
残った桁 n - 2 * (i + 1) は[0, 10)の回文数を作れるので、
d * 10 ^ ((n + 1) / 2 - (i + 1)) を足していきます。
n桁目については[1, d)の範囲で数えます。
最後に、n以下の最大回文数を考えます（各桁でdを含めていないので）。
中央から左右を比較したときに、
左 > 右の場合はすでに数えているので無視します。
左 < 右があった場合は数えていないので1を足します。
すべて左 = 右（つまりnが回文数）の場合は数えていないので1を足します。
こうして数えてきた回文数を出力すればACします。
http://yukicoder.me/submissions/179185
数え間違えたりで時間内に書けなかったのですが、
桁DP解法が分からなかったので自分の方法を信じて実装しました。
どなたか桁DPの解説を書いていただけると幸いです……。
追記
桁DP解法について調べていたら、もっと簡単に求まることが分かりました。
http://yukicoder.me/submissions/179227
これを皮切りに短縮を図って下さった方々がいたようで、
golf熱が再燃しました。
しかしこれ、やめどころが分からない…。
肝心の桁DPについての理解はなんとなくでしか理解できませんでした。
また時間を置いて桁DPに出会ったときに考えたいと思います。
てけてけに、少しずつ。
