SRM 692 div2 medium Dubs

問題

問題概要

LとRが与えられる。LとRの間に、2桁以上で、最後の２桁の数字が同じで数がいくつあるか。

解法

桁dpで解いた。dp[i][j][k] := 整数p(L, R)を考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 kは前回の数字 としてdpで数えあげていった。漸化式はコード参照。0の時も数えあげているが、与えられているLRがどちも0より大きいので問題ない。
これより単純な解法がある。下２桁が同じ数字ということは、下２桁が、00,11,...99であればよい。つまり、下２桁が、00から99で10個存在する。この周期性を利用して、 周期がいくつあるかをx/100で計算してその数だけまず存在する。あとは、残りの部分を全探索でどれだけあるかを探す。

ミス

2桁以上を、2つ以上の数字を含んでいると思って、めんどくさい桁dpを書いていた。

コード

桁dp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

//dp[i][j][k]
//整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。
//kは前回の数字
long long dp[15][2][10];

class Dubs{
public:

    long long slove(string s){
        rep(i, 15)rep(j, 2)rep(k, 10)dp[i][j][k] = 0;
        dp[0][0][0] = 1;

        ll ret  = 0;
        rep(i, s.size()){
            rep(j, 2){
                int lim;
                if(j == 1) lim = 9;//i桁目までですでに未満が決まっていればi+1桁目の数字は何でもよい
                else lim = s[i] - '0';
       
                rep(k, 10)rep(l, lim + 1){
                    if(i < s.size() - 1){
                        dp[i + 1][j || (l < lim)][l] += dp[i][j][k];
                    }else{
                        if(k == l){//下二桁が同じ数(00もカウントしてしまっているが大丈夫)
                            dp[i + 1][j || (l < lim)][l] += dp[i][j][k];
                            ret += dp[i][j][k];//答えに加える
                        }else{//下二桁が異なる数
                            dp[i + 1][j || (l < lim)][l] += dp[i][j][k];
                        }
                    }
                }            
            }
        }

        return ret;
    }


    long long count(long long L, long long R){
        L--;
        string SL = to_string(L), SR = to_string(R);
        return slove(SR) - slove(SL);
    }
};

周期性を利用して計算

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

class Dubs{
public:
    ll cnt(ll x){
        ll sum = 0;
        //10 (= 00, 11, .., 99)
        sum += 10 * (x / 100);
        int t = x % 100;
        for (int i = 0; i <= t; ++i){
            //下２桁が一致
            if(i % 10 == i / 10){
                sum++;
            }
        }
        return sum;
    }

    long long count(long long L, long long R){
        return cnt(R) - cnt(L - 1);
    }
};