目次
AtCoder Beginner Contest 161 D,E,F問題メモ
普通の風邪っぽくても、熱が出ると何となく不安に駆られてしまう今日この頃。
D - Lunlun Number
問題
- 「ルンルン数」を以下で定義する
- 10進数で表記したとき（頭の0は除く）、隣り合う桁の数字の差は0か1
- 1、12332、98などはルンルン数
- 90、12335などはルンルン数で無い
- $K$ 番目のルンルン数を求めよ
- $1 \le K \le 10^5$
- （サンプルより）$10^5$ 番目のルンルン数は3234566667
解法
解説PDFの解法は、Dequeを使って末尾に付け足していく方法。これは考えつかなかった。
桁DP+二分探索で求めた。
「ある数 $N$ 以下のルンルン数の個数」が高速に求められれば、答えを探索する範囲は1～約 $3 \times 10^9$ なので、十分間に合う。
この時、途中で調べる $N$ 自体はルンルン数では無いかも知れないが、 「自分以下のルンルン数の個数が $K$ 以上となる最小の $N$」は必ずルンルン数となるので、境界を求めればよい。
$N$ 以下のルンルン数の個数は、簡単に求められるパターンのようなものが無いかと思ったが、ちょっと見つからなかったので、桁DPを行った。
- $DP[i][j]=$先頭から $i$ 桁目まで見て、末尾が $j$ である $N$ 未満のルンルン数の個数
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の遷移は以下のパターンがある。
- 前の桁の数字からそれぞれ -1, 0, +1 した数字への遷移（前の桁が0,9だった場合はそれぞれ-1,+1が無くなる）
- $DP[i][j] = DP[i-1][j-1]+DP[i-1][j]+DP[i+1][j+1]$
- その桁が最上位である数字
- $DP[i][1～9] += 1$
$N$ ちょうどの部分は、「頭から $i$ 番目までがルンルン数かどうか」「ルンルン数の場合、前の桁は何だったか」を持っておけばよい。
$N$ の $i-1$ 桁目までがルンルン数で無かった場合は、上記のDPの遷移だけでよい。
$N$ の $i-1$ 桁目までがルンルン数で、$i-1$ 桁目が $d$、$i$ 桁目が $e$ だった場合、
- $d-1 \gt e$ なら、ルンルン数でなくなる
- $d-1 \le e \le d+1$ なら、$N$ 以下であることが確定したルンルン数をDPに反映、ルンルン数は継続
- $DP[i][d-1～e-1] += 1$
- $d+1 \lt e$ なら、ルンルン数で無くなるが、$d-1～d+1$ に関してはDPに反映できる
- $DP[i][d-1～d+1] += 1$
$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)
E - Yutori
問題
- 明日から $N$ 日のうち、$K$ 日を選んでアルバイトをする
- 働く日には以下のルールを設ける
- 中 $C$ 日は空ける（$i$ 日目に働いたら、次に働くのは $i+C+1$ 日目以降）
'o','x'からなる長さ $N$ の文字列 $S$ が与えられ、'x' の日は働かない
- 必ず働かなければならない日を全て求めよ
- $1 \le K \le N \le 2 \times 10^5$
- $0 \le C \le N$
- 必ずルールを満たして $K$ 日は働ける
解法
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)))
F - Division or Substraction
問題
- 正整数 $N$ が与えられる
- 以下の条件を満たす、$2～N$ の範囲の整数 $K$ の個数を求めよ
- $N$ が $K$ 未満になるまで以下を繰り返す
- $N$ が $K$ で割り切れるなら、$N←\dfrac{N}{K}$
- $N$ が $K$ で割り切れないなら、$N←N-K$
- この時、最終的な $N$ が1になる
- $2 \le N \le 10^{12}$
解法
割り切れない時、$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通りに分けて考える。
1回以上割り算を行う $K$
当然ながら $N$ の約数である。そして、$K$ を決めれば最終的な $N$ が1になるかどうかは、$O(\log{N})$ で実際にシミュレーションできる。
約数の個数は、まぁ $10^{12}$ 以下の数なら10000個も無いでしょ、くらいの見積もりで、十分に間に合う。
よって、$N$ の約数を求めて、試せばよい。
（実際に試さないで直接個数を求められないか考えたが、よく分からなかった）
1回も割り算を行わない $K$
$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))
