AOJ 2884 Tanka Number

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2884

解法

二分探索 + 桁DP ……ではなく貪欲に解く。
基本的に上の桁から順番に数字を確定させていって、
n 番目を超えないギリギリを選択する、というよくあるやり方。
当然だが各桁は小さい数字から順番に選択していくようにする。

まず、ちょうど d 桁の短歌数は 81 * (2^(d-1) - 1) 個あるので、答えが何桁かは簡単に決定できる。
（2つの数字の決め方で 9 * 9 通り、2桁目以降の数字の割り当て方で 2^(d-1) 通りで、すべてが1桁目と同じ数になる 1通りを省くと先の式になる）
あとは数字を決めるだけ。

上から1桁目は簡単で、1桁目を決めたら、そのような短歌数は 9 * (2^(d-1) - 1) 個あるわけだから、これを超えないギリギリが1桁目で確定する。

2桁目以降は、小さい数字から（同じように）順番に見ていくのだが、

• これまでにすでに2つの異なる数字を選んでいるか
• まだ1つの数字しか選んでいないなら、今の桁に割り当てようとしている数字が1桁目と同じかどうか

に注意して短歌数の個数を数える必要がある。

計算量は O(logN)

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ll n;
    while(cin >> n, n) {
        ll keta = 2, cnt = 0;
        while(cnt + 9 * 9 * ((1LL << (keta - 1)) - 1) < n) {
            cnt += 9 * 9 * ((1LL << (keta - 1)) - 1);
            keta += 1;
        }
        cnt = n - cnt;

        string ans;
        function<void(int, int, int)> solve = [&] (int d, int a, int b) {
            if(d == keta) return;
            if(a == -1) {
                for(a = 1; a <= 9; ++a) {
                    if(cnt > 9 * ((1LL << (keta - 1)) - 1)) {
                        cnt -= 9 * ((1LL << (keta - 1)) - 1);
                        continue;
                    }
                    break;
                }
                ans += '0' + a;
                solve(d + 1, a, b);
            } else if(b == -1) {
                for(b = 0; b <= 9; ++b) {
                    if(a != b) {
                        if(cnt > (1LL << (keta - d - 1))) {
                            cnt -= 1LL << (keta - d - 1);
                            continue;
                        }
                        break;
                    } else {
                        if(cnt > 9 * ((1LL << (keta - d - 1)) - 1)) {
                            cnt -= 9 * ((1LL << (keta - d - 1)) - 1);
                            continue;
                        }
                        break;
                    }
                }
                ans += '0' + b;
                if(a == b) solve(d + 1, a, -1);
                else       solve(d + 1, a, b);
            } else {
                const int ma = max(a, b), mi = min(a, b);
                if(cnt > (1LL << (keta - d - 1))) {
                    cnt -= 1LL << (keta - d - 1);
                    ans += '0' + ma;
                } else {
                    ans += '0' + mi;
                }
                solve(d + 1, a, b);
            }
        };
        solve(0, -1, -1);

        cout << ans << endl;
    }
}

感想

模擬国内本番では二分探索 + 桁DP (数が大きいので文字列同士の足し算をする) で解いてしまったので、まともなほうで解き直した。