ABC161-D: Lunlun Number

問題: https://atcoder.jp/contests/abc161/tasks/abc161_d

でも解けるDP解を紹介する。

(桁で最上位桁の値がとなる、前の桁との絶対値の差が1以内の数の総和)を で計算する。 の場合はルンルン数ではないが、ここでは気にせず計算していく。

小さい順にルンルン数を足していき、総和が 以上になるタイミングで足すのをやめる(ここで はルンルン数ではないのでスキップする)。ここで、 番目のルンルン数は桁で、一番上の桁の値はであることがわかる。ここからは逆戻りしていき、 を順番に足して総和が 以上になるタイミングで足すのをやめる。さらに次の桁は... と戻り続けると解が求まる。

計算量は 程度。

    void solve(istream& cin, ostream& cout) {
      ll k; cin >> k;
      vector<vector<ll>> dp(30, vector<ll>(10));
      for(int i=0; i<=9; i++) {
        dp[0][i] = 1;
      }
      for(int i=1; i<30; i++) {
        for(int j=0; j<10; j++) {
          if (j+1<10) dp[i][j+1] += dp[i-1][j];
          dp[i][j] += dp[i-1][j];
          if (j>0) dp[i][j-1] += dp[i-1][j];
        }
      }

      ll now = 0;
      int x, y;
      bool fin = false;
      for(int i=0; i<30; i++) {
        if (fin) break;
        for(int j=1; j<10; j++) {
          now += dp[i][j];
          if (now >= k) {
            now -= dp[i][j];
            x = i; y = j;
            cout << y;
            fin = true;
            break;
          }
        }
      }

      for(int i=x-1; i>=0; i--) {
        for(int j=max(0, y-1); j<=min(9, y+1); j++) {
          now += dp[i][j];
          if (now >= k) {
            now -= dp[i][j];
            y = j;
            cout << y;
            break;
          }
        }
      }
      cout << endl;

コンテスト中の提出: https://atcoder.jp/contests/abc161/submissions/11524117