DOJ Beginner Contest 9 E - 67
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 9
- 問題
- E - 67
長さ の十進数 が与えられます。 からいくつかの文字を消し、残った文字をそのままの順で並べた数を の倍数か の倍数にしたい問題です。残す文字は 個以上で、先頭が になってもかまいません( も と の倍数です)。消す文字の個数の最小値を求め、できなければ を出力します。
テストケースは 個あり、 の総和は 以下です。
42 で割った余りを見る
Section titled “42 で割った余りを見る”は でも でも割り切れるので、ある数が の倍数か の倍数かは、その数を で割った余り だけで決まります。 が の倍数か の倍数であれば条件を満たします。
を先頭から 1 文字ずつ見ていき、
を更新します。最初は何も残していないので、、それ以外は です。
次の文字が数字 のとき、各 について 2 通りの遷移があります。
- 消す:余りは のままで、消した文字数が 増えます。
- 残す:余りは になり、消した文字数は変わりません。
1 文字以上残す条件
Section titled “1 文字以上残す条件”最後に、 が の倍数か の倍数であるものについて の最小値をとります。
ただし、全部消した場合も「余り 、消した文字数 」として に含まれています。残す文字は 個以上という条件があるので、 のものだけを答えの候補にします。候補がなければ です。
計算量は です。
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)