ACM ICPC 2015 アジア地区予選 E : Bringing Order to Disorder

,

本番はちょっと見たけど、分からなさそうなので飛ばした。 私の苦手な問題だったように見える。

本番終了後に人に解法を聞くと皆 半分全列挙と答えるものの、具体的にどう半分にするのかよく分からなかった。参加記巡りをしていたら桁DPという文字列が見え、すぐに解法が分かった。 本番の私は桁DPは一切思い浮かべなかったが、時間があって3人で考えていたら桁DPという単語は出ていただろうし、解けていたと思う。

E : Bringing Order to Disorder

問題

数字のみからなる長さ$n$の文字列$s$に、$({\rm sum}(s), {\rm prod}(s), {\rm int}(s))$の辞書式順序による比較で定義される順序を導入する。 ただし、${\rm sum}(s) = \Sigma_{c \in s} c$、${\rm prod}(s) = \Pi_{c \in s} (c+1)$、${\rm int}(s) = ({\rm sを整数として解釈したもの})$、である。

数字のみからなる長さ$n$の文字列$s$が与えられる。文字列$s$は長さ$n$の文字列の中で、上の順序で数えて何番目か。

解法

sumとprodに関してdpし、次にintに関してdp。

まずintを無視して、文字列$t$で、明らかに$s$より小さいものの数を数える。 つまり、${\rm sum}(t) \lt {\rm sum}(s)$あるいは${\rm sum}(t) = {\rm sum}(s) \land {\rm prod}(t) \lt {\rm prod}(s)$なものの数を数える。 dp[何文字目][総和][総乗] = 種類の形のdp。 ${\rm prod}(s)$として現れる数の種類はそう多くないため、連想配列で持ってしまえばよい。

次に、$s$と同じsumとprodを持つもの中での$s$の順位を定める。 つまり、${\rm sum}(t) = {\rm sum}(s) \land {\rm prod}(t) = {\rm prod}(s) \land {\rm int}(t) \le {\rm int}(s)$なものの数を数える。 これはdp[何文字目][ここまでがsと一致しているか][総和][総乗] = 種類というdp。 基本的に先程のdpと同じであるが、$s$より大きくなるようなものは数えない。

反省

  • この問題見て桁DPが出てこないの、冷静に考えて経験が足りなさすぎる

実装

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
    string s; cin >> s;
    int sum = accumulate(s.begin(), s.end(), 0) - '0' * s.length();
    ll prod = 1; for (char c : s) prod *= c + 1 - '0';
    ll acc = 0;
    { // decide for sum and prod
        vector<vector<unordered_map<ll,ll> > > dp(s.length()+1,
               vector<unordered_map<ll,ll> >(sum+1));
        dp[0][0][1] = 1;
        repeat (i,s.length()) {
            repeat (j,sum+1) {
                for (auto it : dp[i][j]) {
                    ll k = it.first;
                    repeat (d,10) {
                        if (j+d < sum or (j+d == sum and k*(d+1) < prod)) {
                            dp[i+1][j+d][k*(d+1)] += dp[i][j][k];
                        }
                    }
                }
            }
        }
        repeat (j,sum+1) {
            for (auto it : dp[s.length()][j]) {
                acc += it.second;
            }
        }
    }
    { // decide for int
        array<vector<vector<unordered_map<ll,ll> > >,2> dp;
        dp[0].resize(s.length()+1, vector<unordered_map<ll,ll> >(sum+1));
        dp[1].resize(s.length()+1, vector<unordered_map<ll,ll> >(sum+1));
        dp[0][0][0][1] = 1;
        repeat (l,2) { // 0 : match, 1 : not
            repeat (i,s.length()) {
                repeat (j,sum+1) {
                    for (auto it : dp[l][i][j]) {
                        ll k = it.first;
                        repeat (d,10) {
                            int nl = 1;
                            if (l == 0 and d >  s[i]-'0') continue;
                            if (l == 0 and d == s[i]-'0') nl = 0;
                            if (j+d >  sum) continue;
                            if (j+d == sum) {
                                if (prod % (k*(d+1)) != 0) continue;
                                if (k*(d+1) >  prod) continue;
                            }
                            dp[nl][i+1][j+d][k*(d+1)] += dp[l][i][j][k];
                        }
                    }
                }
            }
        }
        acc += dp[0][s.length()][sum][prod];
        acc += dp[1][s.length()][sum][prod] - 1;
    }
    cout << acc << endl;
    return 0;
}