[Baltic OI 2013 Day 1] Palindrome-Free Numbers(무-팰린드롬 숫자) ★

문제 링크

질문은 언제나 환영입니다.

풀이

딱히 발상이 어려운 문제라고 보기는 힘들다.

특별한 알고리즘이 있는 문제도 아니다.

그냥 열심히 풀면 풀리는 문제다.

 

중요한 관찰은 하나뿐이다.

동적계획법처럼 귀납적으로 무-팰린드롬을 확장시키려는 시도를 해야 한다.

이 때, 확장하는 경계로부터 2칸 정도만 고려해도 충분하다. 왜냐하면 길이가 4 이상인 팰린드롬은 이미 길이가 2 이상인 팰린드롬을 포함하고 있기 때문이다. 예를 들어, $2$와 무-팰린드롬인지 알고 있는 $432$를 이어 붙이는 상황에서는 $2432$를 확인할 필요가 없는 것이다. 왜냐하면 $43$이 애초에 팰린드롬이 아니기 때문이다. 따라서 $24$와 $243$을 확인하는 것으로 충분하다.

이 관찰을 통해서 풀이를 이끌어 낼 수 있다.

 

무-팰린드롬 수 $S$에 $T=\overline{ab\cdots}$를 연결시켜 확장시키는 상황을 가정하자.

• $S$의 길이가 1인 경우: $S=\overline x$라고 하면, $x\neq a\wedge x\neq b$일 때 $\overline{xab\cdots}$로 확장시킬 수 있다.
• $S$의 길이가 2 이상인 경우: $S=\overline {\cdots xy}$라고 하면, $x\neq a\wedge y\neq a\wedge y\neq b$일 때, $\overline{\cdots xyab\cdots }$로 확장시킬 수 있다.

이제 케이스에 따라 노가다를 해주면 된다.

책 페이지라는 문제가 있는데, 이 문제랑 노가다하는 흐름이 비슷하다.

코드

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

ll pw(ll x, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e%2) r *= x;
        e /= 2, x *= x;
    }
    return r;
}

ll calc(vector<int> &v, int n, int k = 0) {
    if (v[k] == v[k+1]) return 0;
    if (n == 2) return 1;
    ll r = 0;
    rep(i,0,v[k+2]-1) if (i != v[k] and i != v[k+1]) {
        r += pw(8,n-3);
    }
    if (v[k] != v[k+2]) r += calc(v,n-1,k+1);
    return r;
}

ll f(ll x) {
    if (x <= 9) return x+1;
    ll c = 10;
    vector<int> v; //digits
    for (int i = 0; i < siz(to_string(x)); ++i) {
        v.push_back(to_string(x)[i]-'0');
    }
    rep(i,1,v[0]-1) rep(j,0,9) if (j != i)
        c += pw(8,siz(v)-2); //first case - (1)
    rep(j,0,v[1]-1) if (j != v[0])
        c += pw(8,siz(v)-2); //first case - (2)
    rep(i,1,siz(v)-2) c += pw(8,siz(v)-2-i)*9*9; //suffix is $...
    return c+calc(v,siz(v)); //calc upper cases
}

int main() {
    ll a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld", f(b)-f(a-1));
}