Codeforces Round 861 (Div. 2) - C. Unlucky Numbers (1900)

C. Unlucky Numbers

Digit DP 로 풀 수 있고, 정해는 그리디이다.

$l$이 한자리 수라면 $l$ 그자체가 정답이고 $\vert l \vert \neq \vert r \vert$ 이라면 $l$ 길이만큼 $99\dots99$ 를 정답으로 내면 된다.

이제 $l$과 $r$의 정답이 같다고 가정하자.

모든 수의 boundary $(d_1, d_2), ~ d_1 \le d_2$ 쌍을 고려한다.

이 경우마다 모두 $dp[i][B][S]=i$ 번째 수를 채울 차례이고 $l$보다 이미 큰지와 $r$보다 이미 작은지 여부를 들고다니면 Digit DP + 역추적으로 풀 수 있다.

int len(int n) {
   int ret = 1;
   n /= 10;
   while (n) ret++, n /= 10;
   return ret;
}
 
void solve() {
   int l, r;
   cin >> l >> r;
 
   int len_low = len(l);
   int len_high = len(r);
 
   if (len_low == 1) {
      cout << l << endl;
      return;
   }
   if (len_low != len_high) {
      cout << string(len_low, '9') << endl;
      return;
   }
 
   if (l == r) {
      cout << l << endl;
      return;
   }
 
   int mn_diff = 1e9;
   string ans_str;
   auto resolve = [&](int n) {
      char mx = '0';
      char mn = '9';
      for (char c: to_string(n)) mina(mn, c), maxa(mx, c);
      if (mn_diff > mx - mn) {
         ans_str = to_string(n);
         mn_diff = mx - mn;
      }
   };
 
   if (r - l <= 100) {
      int mn_ans = 1e9;
      for (int i = l; i <= r; i++) resolve(i);
      cout << ans_str << endl;
      return;
   }
   resolve(l);
   resolve(r);
 
   string L = to_string(l), R = to_string(r);
   string ans;
   vi used(10);
 
   for (int d = 0; d < mn_diff; d++) {
      for (int d1 = 0; d1 + d < 10; d1++) {
         int d2 = d1 + d;
 
         int impossible = 10;
         vector<vvi> dp(20, vvi(2, vi(2, -1)));
         function<int(int, int, int)> fn = [&](int i, int bigger, int smaller) -> int {
            if (i == len_low) return 0;
            int s = d1, e = d2;
            int &ret = dp[i][bigger][smaller];
            if (~ret) return ret;
            if (!bigger) maxa(s, int(L[i] -'0'));
            if (!smaller) mina(e, int(R[i] -'0'));
            for (int d = s; d <= e; d++) {
               int tmp = fn(i + 1, bigger || d > L[i] - '0', smaller || d < R[i] - '0');
               if (tmp != impossible) return ret = d;
            }
            return ret = impossible;
         };
         if (fn(0, 0, 0) != impossible) {
            string ans;
            function<void(int, int, int)> track = [&](int i, int bigger, int smaller) -> void {
               if (i == len_low) return;
               int d = fn(i, bigger, smaller);
               ans += char(d + '0');
 
               int s = d1, e = d2;
               if (!bigger) maxa(s, int(L[i] -'0'));
               if (!smaller) mina(e, int(R[i] -'0'));
 
               track(i + 1, bigger || d > L[i] - '0', smaller || d < R[i] - '0');
            };
            track(0, 0, 0);
            cout << ans << endl;
            return;
         }
      }
   }
   cout << ans_str << endl;
}

에디토리얼 풀이

위에서 말한대로 $(d_1,d_2)$ 쌍을 잡고 일단 $l, r$ 의 prefix 중 $d_1 \sim d_2$ 범위에 들어가며 동일한 것들은 모두 제거하자.

동일한데 저 범위에 안들어가면 이번 쌍은 skip한다.

이제 처음으로 다른 수가 $l$에서 $a$, $r$에서 $b$라고 한다면 $a \le b$ 이고 $a + 1 < b$ 라면 $a+1$ 도 $d_1,d_2$ 범위에 들어간다는 소리이므로 $(a+1)d_1d_1d_1\dots$ 처럼 채워주면 된다.

만약 $a+1=b$ 라면 $ad_2d_2d_2\dots$ 와 $(a+1)d_1d_1d_1d_1\dots$ 가 유효한지($l \sim r$범위에 있는지) 따져본다.

저렇게 선택하는것이 가장 $l$ 이상일 확률이 높고 가장 $r$ 이하일 확률이 높은 그리디가 성립하기 때문이다.

이렇게 모두 완탐하여 정답을 구하면 된다.