AtCoder Beginner Contest 465 D,E,F問題メモ

AtCoder Beginner Contest 465

D - X to Y

問題文

整数 $X,Y$ と $2$ 以上の整数 $K$ が与えられます。
変数 $x$ があり、はじめ $x=X$ です。あなたは $x$ に対して以下の操作を $0$ 回以上何回でも行うことができます：
- $\displaystyle \left\lfloor \frac xK \right\rfloor=y$ または $\displaystyle \left\lfloor \frac yK \right\rfloor=x$ を満たす整数 $y$ を選び、$x$ の値を $y$ に置き換える。
- ここで、実数 $z$ に対し $\displaystyle \left\lfloor z \right\rfloor$ は $z$ 以下の最大の整数として定義されます。
$x=Y$ とするために必要な操作回数の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 2\times 10^5$
$0\le X,Y\le 10^{18}$
$2\le K\le 10^{18}$
入力される値は全て整数

解法

$K$ 進数の数として考えると見通しが良くなる。

$\displaystyle \left\lfloor \frac xK \right\rfloor=y$ は、$K$ 進数で表した $x$ の下1桁を削る行為
$\displaystyle \left\lfloor \frac yK \right\rfloor=x$ は、$K$ 進数で表した $x$ の下1桁に好きな数を付け足す行為

よって、$K$ 進数で表した時の互いの prefix が共通する部分は残してよくて、それ以外は削ったり付け足したりする必要がある。

とはいえ、実装の際には prefix とか考えずとも、「$X=Y$ となるまで $X$ と $Y$ の大きい方を $K$ で割る」操作回数を求めることで正答できる。

Python3

def solve(x, y, k):
    ans = 0
    while x != y:
        if x > y:
            x //= k
        else:
            y //= k
        ans += 1
    return ans


t = int(input())
for _ in range(t):
    x, y, k = list(map(int, input().split()))
    ans = solve(x, y, k)
    print(ans)

E - Digit Circus

問題文

$1$ 以上 $N$ 以下の整数 $x$ であって、以下の $3$ つの条件のうちちょうど $\mathbf{1}$ つだけを満たすものの個数を $998244353$ で割ったあまりを求めてください。
- $x$ は $3$ の倍数である
- $x$ の十進表記には 3 が含まれる
- $x$ の十進表記にはちょうど $3$ 種類の数字が使われる
なお、整数の十進表記は先頭に不要な 0 をつけないものとします。

制約

$N$ は整数
$1 \leq N \lt 10^{500}$

解法

桁DP。1つ1つの条件は桁DPの問題として度々見るが、複数を一気に考えなければならないので落ち着いて処理する。

なお、「1つだけ満たす」などの文言から包除原理っぽくも見えるが、どうせ包除原理でも複数条件を同時に満たすやつを一気に考える必要がある。それなら後述のようなDPで「どの条件を満たしてて、どれを満たしてないか」を個別に判定することができるので、DPは1回でいい。

以下の情報を整理しとけばいい。

$\mathrm{DP}[i,j,k]:=$
- 上から $i$ 桁目まで見て、$N$ 以下であることが確定していて、
- これまでに使った数字の集合bitsetが $j$ で、
- ここまでのmod3が $k$ であるような数字の個数

bitsetは、「十進表記に3が含まれるか」「十進表記は丁度3種類の数字が使われるか」の2つの判定に答えられる。
状態数は $2^{10}=1024$

mod3 は、そのまま $3$ の倍数かの判定に用い、状態数は $3$

遷移では、各状態から末尾に新規に何を置くかで $10$ 通り。

桁は $500$ 桁なので、全体で $1024 \times 3 \times 10 \times 500 = 1.536 \times 10^7$ 程度で、間に合う。

Python3

bitsetを、pop count が $4$ 以上になった時点でバーストと見なして全て同じ値（-1）とし、代わりに'3'が含まれるかを別途boolで保持する実装により、状態数を少し節約しているが、パフォーマンス的に向上してるかは微妙。

from collections import defaultdict


def solve(n):
    MOD = 998244353
    dp = {}
    n_bitset = 0
    n_inc3 = 0
    n_mod3 = 0
    is_first = True
    for c in n:
        ndp = defaultdict(int)
        c = int(c)
        # こっから始まる
        if is_first == False:
            for i in range(1, 10):
                ndp[1 << i, int(i == 3), i % 3] += 1
        # こっから N 以下が確定する。
        for i in range(int(is_first), c):
            bitset = n_bitset | (1 << i)
            inc3 = n_inc3 | int(i == 3)
            mod3 = (n_mod3 * 10 + i) % 3
            if bitset.bit_count() > 3:
                bitset = -1
            ndp[bitset, inc3, mod3] += 1
            ndp[bitset, inc3, mod3] %= MOD
        is_first = False
        # 既に N 以下が確定しているもの
        for (bitset, inc3, mod3), pat in dp.items():
            if bitset == -1:
                for i in range(10):
                    new_mod3 = (mod3 * 10 + i) % 3
                    new_inc3 = inc3 | int(i == 3)
                    ndp[-1, new_inc3, new_mod3] += pat
                    ndp[-1, new_inc3, new_mod3] %= MOD
                continue
            bc = bitset.bit_count()
            for i in range(10):
                new_mod3 = (mod3 * 10 + i) % 3
                new_inc3 = inc3 | int(i == 3)
                if bitset & (1 << i) == 0:
                    if bc == 3:
                        ndp[-1, new_inc3, new_mod3] += pat
                        ndp[-1, new_inc3, new_mod3] %= MOD
                    else:
                        ndp[bitset | (1 << i), new_inc3, new_mod3] += pat
                        ndp[bitset | (1 << i), new_inc3, new_mod3] %= MOD
                else:
                    ndp[bitset, new_inc3, new_mod3] += pat
                    ndp[bitset, new_inc3, new_mod3] %= MOD
        dp = ndp
        n_bitset = n_bitset | (1 << c)
        n_inc3 = n_inc3 | int(c == 3)
        n_mod3 = (n_mod3 * 10 + c) % 3
        # print(f'{c=} {dp=}')

    ans = 0
    for (bitset, inc3, mod3), pat in dp.items():
        bc = bitset.bit_count()
        if int(bc == 3) + inc3 + int(mod3 == 0) == 1:
            ans += pat
            ans %= MOD

    if int(len(set(n)) == 3) + int('3' in n) + int(n_mod3 == 0) == 1:
        ans += 1
        ans %= MOD

    return ans


n = input()
ans = solve(n)
print(ans)

F - Sjeltzer?

問題文

ある冷蔵庫では、ドリンクに $6$ 桁の数字列を ID として割り振っています。
この冷蔵庫には $N$ 個のドリンクが保管されています。
- $i$ 番目のドリンクの ID は $S_i$、サイズは $V_i$ です。$S_1, \dots, S_N$ は相異なります。
$Q$ 個のクエリに答えてください。各クエリは $6$ 桁の数字列 $x, y$ の形式で与えられ、内容は以下の通りです。
- この冷蔵庫にあるドリンクのうち、割り振られた ID $s$ がどの $k = 1, \dots, 6$ についても以下を満たすようなものについて、そのサイズの総和を求めよ。
  - $s, x, y$ の $k$ 桁目の数字が表す値を $s_k, x_k, y_k$ とおいたとき、$x_k \leq s_k \leq y_k$ を満たす。

制約

$N$ は整数
$1 \leq N \leq 3 \times 10^5$
$S_i$ は数字 (0-9) からなる文字列
$|S_i| = 6$
$S_1, \dots, S_N$ は相異なる
$V_i$ は整数
$1 \leq V_i \leq 10^9$
$Q$ は整数
$1 \leq Q \leq 3 \times 10^5$
各クエリにおいて、$x, y$ は数字 (0-9) からなる文字列
各クエリにおいて、$|x| = |y| = 6$

解法

仮にIDの桁が1桁なら、「IDが $x$ 以上 $y$ 以下のドリンクのサイズの総和は？」となって、単純な累積和問題であることはすぐ分かる。

これを6次元でやれ、という問題。

例えば2次元累積和なら以下の4つの点の足し引きで求められる。これは包除原理を使っている。

  →2次元目
↓ (X1-1,X2-1).  …  (X1-1,Y2).
１             ┼───────┼    Acc[Y1,Y2] - Acc[Y1,X2-1] - Acc[X1-1,Y2] + Acc[X1-1,X2-1]
次             │              │
元             │              │
目 ( Y1 ,X2-1).│      (Y1,Y2).│
               ┼───────┼

6次元でも同様に、$2^6$ 個の累積和の位置を参照し、「$x_k-1$ と $y_k$ のうち、$y_k$ の方を採用した個数」が偶数なら答えに正で寄与し、奇数なら負で寄与する、として合計すれば答えが求まる。累積和を計算しておけば、1クエリ当たり $2^6=64$ 個の値の配列参照と加減算で求められる。

各IDを桁毎にバラして $(s_1,s_2,s_3,s_4,s_5,s_6)$ の位置に重み $v$ を加算してから、各次元の累積和を取る。
この際、実際に6次元配列でやってもいいのだが、配列の入れ子は（特にPythonでは）重く・遅くなる上に、for の入れ子をいっぱい書かないといけなくなる。
高速ゼータ変換・メビウス変換のような方法で、1次元配列で管理することもできる。

zeta = [0] * 1000000

// 各IDの位置にドリンクのサイズを加算後、

for d in (次元数,今回は6):
    for _id in (000000から999999まで):
        if _id の d 桁目が"0"でないなら:
            zeta[_id] += zeta[_id の d 桁目を1減らした数]

としていくと、累積和が取れる。

※ただし、累積和では $[L,R]$ の範囲を求める際、$Acc[R]-Acc[L-1]$ を計算する時に $L=0$ の場合でも統一的に実装するため、先頭に $0$ を追加しておく実装もあるが、今回のこのやり方ではそれができなくなる。

各次元のサイズを $11$ に広げ、IDの各桁の数字を1ずつ加えて解釈する。
- 足し込む座標、if の部分等に少し工夫が必要となる。
$L=0$ の場合は引く処理をスキップする

などの回避策が必要となる。

Python3

以下は気合いで実装した版

from itertools import product


def solve(n, drinks, qn, queries):
    acc = [[[[[[0] * 11 for _ in range(11)] for _ in range(11)] for _ in range(11)] for _ in range(11)] for _ in
           range(11)]
    for _id, v in drinks:
        p = int(_id[0]) + 1
        q = int(_id[1]) + 1
        r = int(_id[2]) + 1
        s = int(_id[3]) + 1
        t = int(_id[4]) + 1
        u = int(_id[5]) + 1
        v = int(v)
        acc[p][q][r][s][t][u] += v

    for p, q, r, s, t in product(range(11), repeat=5):
        for u in range(10):
            acc[p][q][r][s][t][u + 1] += acc[p][q][r][s][t][u]
    for p, q, r, s, u in product(range(11), repeat=5):
        for t in range(10):
            acc[p][q][r][s][t + 1][u] += acc[p][q][r][s][t][u]
    for p, q, r, t, u in product(range(11), repeat=5):
        for s in range(10):
            acc[p][q][r][s + 1][t][u] += acc[p][q][r][s][t][u]
    for p, q, s, t, u in product(range(11), repeat=5):
        for r in range(10):
            acc[p][q][r + 1][s][t][u] += acc[p][q][r][s][t][u]
    for p, r, s, t, u in product(range(11), repeat=5):
        for q in range(10):
            acc[p][q + 1][r][s][t][u] += acc[p][q][r][s][t][u]
    for q, r, s, t, u in product(range(11), repeat=5):
        for p in range(10):
            acc[p + 1][q][r][s][t][u] += acc[p][q][r][s][t][u]

    bcs = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3,
           2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6]

    buf = []
    for x, y in queries:
        p1 = int(x[0])
        q1 = int(x[1])
        r1 = int(x[2])
        s1 = int(x[3])
        t1 = int(x[4])
        u1 = int(x[5])
        p2 = int(y[0]) + 1
        q2 = int(y[1]) + 1
        r2 = int(y[2]) + 1
        s2 = int(y[3]) + 1
        t2 = int(y[4]) + 1
        u2 = int(y[5]) + 1

        if p1 >= p2 or q1 >= q2 or r1 >= r2 or s1 >= s2 or t1 >= t2 or u1 >= u2:
            buf.append(0)
            continue

        ans = 0
        for bitset in range(64):
            p = p1 if (bitset & 1) else p2
            q = q1 if (bitset & 2) else q2
            r = r1 if (bitset & 4) else r2
            s = s1 if (bitset & 8) else s2
            t = t1 if (bitset & 16) else t2
            u = u1 if (bitset & 32) else u2
            if bcs[bitset] % 2 == 0:
                ans += acc[p][q][r][s][t][u]
            else:
                ans -= acc[p][q][r][s][t][u]
        buf.append(ans)
    return buf


n = int(input())
drinks = [input().split() for _ in range(n)]
q = int(input())
queries = [input().split() for _ in range(q)]
ans = solve(n, drinks, q, queries)
print('\n'.join(map(str, ans)))

目次

AtCoder Beginner Contest 465 D,E,F問題メモ

D - X to Y

問題文

制約

解法

E - Digit Circus

問題文

制約

解法

F - Sjeltzer?

問題文

制約

解法