コンテンツにスキップ

DOJ Beginner Contest 9 E - 67

サイト
DOJ
コンテスト
DOJ Beginner Contest 9
問題
E - 67

長さ NN の十進数 SS が与えられます。SS からいくつかの文字を消し、残った文字をそのままの順で並べた数を 66 の倍数か 77 の倍数にしたい問題です。残す文字は 11 個以上で、先頭が 00 になってもかまいません(00 も 66 と 77 の倍数です)。消す文字の個数の最小値を求め、できなければ −1-1 を出力します。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

42=6×742 = 6 \times 7 は 66 でも 77 でも割り切れるので、ある数が 66 の倍数か 77 の倍数かは、その数を 4242 で割った余り mm だけで決まります。mm が 66 の倍数か 77 の倍数であれば条件を満たします。

SS を先頭から 1 文字ずつ見ていき、

dp[m]=残した文字が表す数を 42 で割った余りが m になるときの、消した文字数の最小値\mathrm{dp}[m] = \text{残した文字が表す数を } 42 \text{ で割った余りが } m \text{ になるときの、消した文字数の最小値}

を更新します。最初は何も残していないので、dp[0]=0\mathrm{dp}[0] = 0、それ以外は ∞\infty です。

次の文字が数字 xx のとき、各 mm について 2 通りの遷移があります。

  • 消す:余りは mm のままで、消した文字数が 11 増えます。
  • 残す:余りは (10m+x) mod 42(10m + x) \bmod 42 になり、消した文字数は変わりません。

最後に、mm が 66 の倍数か 77 の倍数であるものについて dp[m]\mathrm{dp}[m] の最小値をとります。

ただし、全部消した場合も「余り 00、消した文字数 NN」として dp[0]\mathrm{dp}[0] に含まれています。残す文字は 11 個以上という条件があるので、dp[m]<N\mathrm{dp}[m] < N のものだけを答えの候補にします。候補がなければ −1-1 です。

計算量は O(42∑N)O(42 \sum N) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
dp = [float("inf")] * 42
dp[0] = 0
for c in S:
x = int(c)
ndp = [float("inf")] * 42
for i in range(42):
ndp[i] = dp[i] + 1
for i in range(42):
j = (i * 10 + x) % 42
ndp[j] = min(ndp[j], dp[i])
dp = ndp
ans = float("inf")
for i in range(42):
if i % 6 == 0 or i % 7 == 0:
if dp[i] < N:
ans = min(ans, dp[i])
if ans == float("inf"):
ans = -1
print(ans)