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

AtCoder Beginner Contest 161

普通の風邪っぽくても、熱が出ると何となく不安に駆られてしまう今日この頃。

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))

目次