問題概要

ある n+1 ($ n \leq 2000 $) 桁以下の数値について，隣あった桁の数字の大小関係が "=!><" の文字を含む長さ n の文字列で与えられる．

このとき，「ある n+1 桁以下の数値」としてありうる最小の数を求めよ．leading zero(s) を含んではいけない．

解法概要

(何桁目まで決定したか, 最後に決定した桁の数) の組を状態として，上の桁から順に見ていく．最小の数を求めたいので小さい数字から順番に試していき，その数字にしてもその後 (それよりも下の桁で) 矛盾が出ないとなったら OK．

全ての状態について，もう計算した/してないを管理しておけば (ソースコード中の visited)，状態の数は高々 2000 * 10 通りなので余裕で間に合う．

小さい順に試すだけではなく，「この状態はもう計算済み？」「計算済みだとしたら，この状態を使って条件を満たす数値は作れる？」この2つをフィードバックさせることが大事．

ソースコード

#include <string>
#include <iostream>

using namespace std;

bool visited[2001][10], ok[2001][10]; // true で初期化されているので注意
int next_digit[2001][10];

class ReconstructNumber {
    public:

    int n;
    string s;

    // i桁目をjと決めたとき，(i+1)桁めを決める
    bool solve(int i, int j) {
        if(i == n) return true;
        if(visited[i][j]) return ok[i][j];
        
        visited[i][j] = true;

        if(s[i] == '=') {
            if(solve(i+1, j)) {
                ok[i][j] = true;
                next_digit[i][j] = j;
                return true;
            }
        } else if(s[i] == '!') {
            for(int k=0;k<10;++k) {
                if(j == k) continue;
                if(solve(i+1, k)) {
                    ok[i][j] = true;
                    next_digit[i][j] = k;
                    return true;
                }
            }
        } else {
            int k_min = ((s[i] == '<')?j+1:0), k_max1 = ((s[i] == '<')?10:j);
            for(int k=k_min;k<k_max1;++k) {
                if(solve(i+1, k)) {
                    ok[i][j] = true;
                    next_digit[i][j] = k;
                    return true;
                }
            }
        }
        return false;
    }
    
    string smallest(string comparisons) {
        s = comparisons;
        n = s.length();
        fill(visited[0], visited[n+1]+10, false);
        fill(ok[0], ok[n+1]+10, false);
        
        for(int j=1;j<10;++j) {
            if(solve(0, j)) {
                string ans = "";
                int d = j;
                for(int i=0;i<n;++i) {
                    ans += char('0' + d);
                    d = next_digit[i][d];
                }
                ans += char('0' + d);
                return ans;
            }
        }
        return "";
    }
};

所感

tourist 氏に撃墜してもらった思い出の問題．

再帰で実装するとスマートに解けるタイプのDP，要精進．

NoiminのNoise

TopCoder SRM 752 Div 1 Easy - ReconstructNumber

問題概要

解法概要

ソースコード

所感