F - Sjeltzer? 解説
by
sheyasutaka
印刷ページ
\(x\) が 000000 の場合の下位問題
この下位問題において,求める \(s\) の範囲は,すべての \(k\) で \(s_k \leq y_k\) を満たす \(s\) です.
\(10^6\) 通りのあり得るすべての \(y\) について,その答えを求めることを考えます. これは,累積和を \(6\) 次元に拡張したアルゴリズムによって求まります.
\(\mathrm{zeta}_m[y]\) を,以下を満たす \(s\) の範囲に対応するサイズ総和をもつものとします.
- すべての \(k \leq m\) で \(s_k \leq y_k\).
- すべての \(k > m\) で \(s_k = y_k\).
\(\mathrm{zeta}_0[y]\) は \(s = y\) に対応し,\(\mathrm{zeta}_6[y]\) は最終的に求めたい範囲に対応します.
このとき,以下の累積和によって \(\mathrm{zeta}_{m-1}\) から \(\mathrm{zeta}_{m}\) を求めることができます.
- \(y\) の昇順に,以下のように求まる.
- \(y\) の \(k\) 桁目が
0ならば,\(\mathrm{zeta}_m[y] = \mathrm{zeta}_{m-1}[y]\) である. - \(y\) の \(k\) 桁目が
0でないならば,\(\mathrm{zeta}_m[y] = \mathrm{zeta}_m[y'] + \mathrm{zeta}_{m-1}[y]\) である.ここで \(y'\) は,\(y\) の \(k\) 桁目を \(1\) だけ減らした値である.
- \(y\) の \(k\) 桁目が
これを \(m=1,\dots,6\) について行うことで,任意の \(y\) に対する答えが得られます.
元の問題を下位問題に帰着
\(x_k > y_k\) となる \(k\) が存在する場合の答えは \(0\) です.以降はそうでない場合を考えます.
求める \(s\) の範囲は,すべての \(k\) で \(s_k \leq y_k\) を満たす \(s\) のうち,追加で以下の \(6\) 条件をすべて満たすものとして言い換えられます.
- 条件 \(c_1\): 「\(s_1 \leq x_1 - 1\) でない」.
- 条件 \(c_2\): 「\(s_2 \leq x_2 - 1\) でない」.
- \(\vdots\)
- 条件 \(c_6\): 「\(s_6 \leq x_6 - 1\) でない」.
上の \(6\) 条件からなる集合 \(\{c_1,c_2,\dots,c_6\}\) の部分集合 \(T\) について,\(F(T)\) を「\(T\) に属する条件は満たさず,ほかの条件は満たしても満たさなくてもよいときの \(s\) の範囲」とし,\(F(T)\) に属する ID に対応するサイズの総和を \(g(T)\) とします.このとき包除原理から,求める個数は以下に等しいことが分かります.
\[\sum_{T \subseteq \{c_1,\dots,c_6\} } (-1)^{|T|} g(T)\]
それぞれの \(T\) において,\(F(T)\) が表す範囲は「すべての \(k\) で \(s_k \leq \begin{cases} y_k & (c_k \notin T) \\ x_k - 1 & (c_k \in T) \end{cases}\) を満たす \(s\)」であり,これは解説冒頭で述べた下位問題で考えた範囲と同じ形です.したがって,前処理で求めた値をそのまま使うことができます.
時間計算量は \(B=10,\ D=6\) とおいて,前処理 \(O(D \cdot N + B^D D)\),各クエリ \(O(2^D D)\) です.
実装例 (C++)
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
#include <string>
using std::string;
using std::to_string;
typedef long long int ll;
const ll BITLEN = 6;
const ll BASE = 10;
vector<ll> make_pow (ll base, ll maxv) {
vector<ll> ans(maxv+1, 0);
ans[0] = 1;
for (ll i = 1; i <= maxv; i++) {
ans[i] = ans[i-1] * base;
}
return ans;
}
const vector<ll> pow10 = make_pow(BASE, BITLEN);
ll idtoidx (const string s) {
ll x = 0;
for (ll i = 0; i < BITLEN; i++) {
x += (ll)(s[i] - '0') * pow10[i];
}
return x;
}
inline ll idxdigit (const ll x, const ll d) {
return (x / pow10[d]) % BASE;
}
void output (const ll x) {
cout << x << "\n";
}
ll n;
vector<string> s;
vector<ll> v;
ll q;
void solve () {
vector<ll> zeta(pow10[BITLEN], 0);
for (ll i = 0; i < n; i++) {
zeta[idtoidx(s[i])] += v[i];
}
for (ll bi = 0; bi < BITLEN; bi++) {
for (ll i = 0; i < pow10[BITLEN]; i++) {
if (idxdigit(i, bi) > 0) {
zeta[i] += zeta[i - pow10[bi]];
}
}
}
cin >> q;
for (ll qi = 0; qi < q; qi++) {
string sx, sy;
cin >> sx >> sy;
ll vx = idtoidx(sx);
ll vy = idtoidx(sy);
ll ans = 0;
vector<ll> wx(BITLEN), wy(BITLEN);
bool isnonzero = true;
for (ll i = 0; i < BITLEN; i++) {
wx[i] = idxdigit(vx, i);
wy[i] = idxdigit(vy, i);
if (wx[i] > wy[i]) isnonzero = false;
}
if (!isnonzero) {
ans = 0;
output(ans);
continue;
}
for (ll bi = 0; !(bi >> BITLEN); bi++) {
ll zidx = 0;
ll bcnt = 0;
bool isok = true;
for (ll i = 0; i < BITLEN; i++) {
if (bi & (1LL << i)) {
// -
bcnt += 1;
if (wx[i] <= 0) isok = false;
zidx += (wx[i] - 1) * pow10[i];
} else {
// +
bcnt += 0;
zidx += wy[i] * pow10[i];
}
}
if (!isok) continue;
if (bcnt % 2 == 0) {
ans += zeta[zidx];
} else {
ans -= zeta[zidx];
}
}
output(ans);
}
return;
}
int main (void) {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
cin >> n;
s.resize(n);
v.resize(n);
for (ll i = 0; i < n; i++) {
cin >> s[i] >> v[i];
}
solve();
return 0;
}
投稿日時:
最終更新:
