Google KickStart 2020H-B "Boring Numbers"

ABC-Eぐらいでありそう

問題リンク：

codingcompetitions.withgoogle.com

問題概要

ある正整数Xが"boring"である、とは次のように定義される：「Xを文字列として見た時、左から数えてi(1-index)桁目の偶奇がiの偶奇と一致する」。L以上R以下の"boring"な数は何通りあるか？(1 <= L < R <= 1e18)

解法

func(X) := 「X以下の"boring"な数の個数」とします。桁DPをすれば良いですが、len := (Xの桁数）として1以上len未満桁の数については、必ずX以下になるので、これらの桁数については、あり得る"boring"な数全部を試せばよく、それは明らかに(5^{桁数})の1からlen-1までの和になります。以下、len桁の数のみ考えます。

dp[dig][num][less] := dig桁目をnumにするとき、この値がX未満になることが確定するか？ として、Xの大きい桁から順に決めていけば解くことができます。この手のDP遷移は典型ですね。

次のように実装することができます。

// solution for KickStart2020H-B
// author : lynmisakura
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int len;
string s;
ll dp[20][20][2];
ll func2(int len){
  ll res = 1;
  for (int i = 0; i < len; i++) {
    res *= 5;
  }
  return res;
}
ll func(ll X){

  memset(dp,0,sizeof(dp));

  s = to_string(X);
  len = int(s.size());

  dp[0][0][0] = 1;
  for (int i = 0; i < len; i++) {
    int x = (s[i] - '0');
    for (int from_dig = 0; from_dig < 10; from_dig++) {
      for (int to_dig = 0; to_dig < 10; to_dig++) {
        if((i + 1 - to_dig) % 2 == 0){
          for (int less = 0; less < 2; less++) {
            if(!less){
              if (to_dig < x) {
                dp[i+1][to_dig][1] += dp[i][from_dig][0];
              } else if(to_dig == x){
                dp[i+1][to_dig][0] += dp[i][from_dig][0];
              }else{
                continue;
              }
            }else{
              dp[i+1][to_dig][1] += dp[i][from_dig][1];
            }
          }
        }
      }
    }
  }

  ll res = 0;
  for (int i = 1; i < len; i++) {
    res += func2(i);
  }
  for (int dig = 0; dig < 10; dig++) {
    for (int less = 0; less < 2; less++) {
      res += dp[len][dig][less];
    }
  }

  return res;

}

/*=====================================================*/

void main2(){
  ll L,R;
  cin >> L >> R;
  cout << func(R) - func(L-1) << '\n';
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(20);

  int tt;cin >> tt;
  for(int i=1;i<=tt;i++){
    cout << "Case #" << i << ": ";
    main2();
  }
}