普通の風邪っぽくても、熱が出ると何となく不安に駆られてしまう今日この頃。
解説PDFの解法は、Dequeを使って末尾に付け足していく方法。これは考えつかなかった。
桁DP+二分探索で求めた。
「ある数 $N$ 以下のルンルン数の個数」が高速に求められれば、答えを探索する範囲は1~約 $3 \times 10^9$ なので、十分間に合う。
この時、途中で調べる $N$ 自体はルンルン数では無いかも知れないが、 「自分以下のルンルン数の個数が $K$ 以上となる最小の $N$」は必ずルンルン数となるので、境界を求めればよい。
$N$ 以下のルンルン数の個数は、簡単に求められるパターンのようなものが無いかと思ったが、ちょっと見つからなかったので、桁DPを行った。
i 0 1 2 3 ----------------- N 3 3 2 8 j 0 1 4 13 1 1 3 9 25 2 1 4 10 29 3 2 8 25 4 1 5 18 5 1 4 14 6 1 4 13 7 1 4 13 8 1 4 12 9 1 3 8 ~~→この和 498 が、3328以下のルンルン数の個数
ただし $N$ 以下であることが確定した個数を上記のDPで管理し、$N$ ちょうどの部分は別に管理する。
DPの遷移は以下のパターンがある。
$N$ ちょうどの部分は、「頭から $i$ 番目までがルンルン数かどうか」「ルンルン数の場合、前の桁は何だったか」を持っておけばよい。
$N$ の $i-1$ 桁目までがルンルン数で無かった場合は、上記のDPの遷移だけでよい。
$N$ の $i-1$ 桁目までがルンルン数で、$i-1$ 桁目が $d$、$i$ 桁目が $e$ だった場合、
$N$ が最後までルンルン数であった場合は、最終的なDPの和に $N$ 自身の1を足す。
import numpy as np k = int(input()) def check(n): digits = [] while n: n, m = divmod(n, 10) digits.append(m) digits.reverse() dp = np.zeros(10, dtype=np.int64) dp[1:digits[0]] = 1 edge = digits[0] for d in digits[1:]: odp = dp.copy() dp[:-1] += odp[1:] dp[1:] += odp[:-1] dp[1:] += 1 if edge != -1: if edge - 1 > d: edge = -1 elif edge + 1 >= d: dp[max(0, edge - 1):d] += 1 edge = d else: dp[max(0, edge - 1):edge + 2] += 1 edge = -1 result = dp.sum() if edge != -1: result += 1 return result >= k l = 0 r = 3234566667 while l + 1 < r: m = (l + r) // 2 if check(m): r = m else: l = m print(r)
'o','x
'からなる長さ $N$ の文字列 $S$ が与えられ、'x
' の日は働かないF問題より正答者が少ない。
必ず働かなければいけない日とは、その日にもし働かないと($S$ 上でもし'x'だと)日数が $K$ に足りなくなる日である。
よって、頑張って詰めれば $K+1$ 日以上働けるような入力の場合、答えは無し。
以下、頑張って $K$ 日しか働けないとする。
K=3 C=3 oooxxxooxxxoxo ~~~ ~~ ~~~ こんなケースだと、~~~で区切ったところから1つずつ選べばよいので、 「必ず」働かなければならない、という日は無い。 oooxxxoxxxxoxo ~~~ ~ ~~~ こんなケースだと、真ん中の日は働かざるを得ない。
「ある日をo→xに変えると、全体の個数がどう変わるか」なので、前と後ろから累積和で「$i$ 日で働ける最大日数」を計算しとくとよいような感じがする。
変えた日を挟んで以前と以降の働ける日数を足し合わせたいが、結合する前と後ろの間も $C$ 日以上空いていないといけないので、
oooxxxooxxxoxo 前 011111122222333 働ける最大日数 後 333222221111110 oooxxxXoxxxoxo 'X'の位置をxにしたら? |---1 2------| → 3 それを挟むような、間がC=3個空いた区間を全て考え、 |----1 1-----| → 2 前からの日数と後からの日数の和の最大値が、働ける日数となる |-----1 1----| → 2 (この場合は3) 前 後
これが $K$ 未満なら、その日は必ず働かなければいけない日。これを調べるとよい。
実装を頑張ればこのままでも解けるが、上手く計算をまとめないとTLEとなる程度には頑張る必要がある。
もう少し、これがどういう点なのかを考えると、 もともとは全体で働ける日数が $K$ であったはずで、それが1つでも左右にずれると $K$ 未満となるような点である。
X 働ける日数 |--| |--------| K |---| |-------| K未満 |----| |------| K未満 |-----| |-----| K未満 |------| |----| K
つまり、条件を満たすのは、前から数えても後ろから数えても新たにカウントが1増える箇所である、ということがわかる。
def solve(n, k, c, s): ls = set() lp = -c - 1 lc = 0 for i, w in enumerate(s): if w == 'o' and i > lp + c: ls.add(i) lp = i lc += 1 if lc > k: return [] rp = n + c ans = [] for i in range(n - 1, -1, -1): w = s[i] if w == 'o' and i < rp - c: if i in ls: ans.append(i + 1) rp = i ans.reverse() return ans n, k, c = map(int, input().split()) s = input() ans = solve(n, k, c, s) print('\n'.join(map(str, ans)))
割り切れない時、$N←N-K$ の操作によって割り切れるようになることは無い。
よって、「最初、$N$ を $K$ で割り切れるだけ割って、以降は $K$ を引き続ける」、さらにこの後半を言い換えると「$K$ で割った余りを取る」操作となる。
1に至る経路を逆算して樹形図のように表すと、以下のようになる。
1 ←-- K ←-- K^2 ... ↑ 1+ K ←-- K+ K^2 ←-- K^2+ K^3 ... ↑ 1+2K ←-- K+2K^2 ←-- K^2+2K^3 ... ...
上図に出てくるような $K$ の式が、$N$ と等しくなるような $K$ の個数が、答えとなる。
ここで、以下の2通りに分けて考える。
当然ながら $N$ の約数である。そして、$K$ を決めれば最終的な $N$ が1になるかどうかは、$O(\log{N})$ で実際にシミュレーションできる。
約数の個数は、まぁ $10^{12}$ 以下の数なら10000個も無いでしょ、くらいの見積もりで、十分に間に合う。
よって、$N$ の約数を求めて、試せばよい。
(実際に試さないで直接個数を求められないか考えたが、よく分からなかった)
$N-1$ の約数である。2以上の約数でありさえすれば、条件を満たす。
$N$ と $N-1$ は互いに素なため、上と重複することは無い。(厳密には $N=2$ の時成り立たないが、その場合 $N-1$ の2以上の約数は存在しない)
def divisor(n): i = 1 res = set() while i * i <= n: if n % i == 0: res.add(i) res.add(n // i) i += 1 return res def solve(n): pf1 = divisor(n - 1) ans = len(pf1) - 1 pf2 = divisor(n) pf2.remove(1) for y in pf2: m = n while m % y == 0: m //= y if m % y == 1: ans += 1 return ans n = int(input()) print(solve(n))