公式

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\) だけ減らした値である.

これを \(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;
}

投稿日時:
最終更新: