AtCoder Regular Contest 202 (Div. 1) A,B,C問題メモ

AtCoder Regular Contest 202 (Div. 1)

A - Merge and Increment

• 次の条件を満たす整数列を 良い数列 と呼びます。
  • 次の マージ操作 を $0$ 回以上自由な回数繰り返して、数列の長さを $1$ にすることができる。
    • 値の等しい要素が $2$ 個連続している箇所を選ぶ。その要素の値を $x$ とする。
    • $2$ 個の要素を両方取り除き、要素があった場所に $x+1$ を挿入する。
  • 例えば $(1, 3, 3, 5)$ という数列の前から $2$ 番目と $3$ 番目の要素を選んでマージ操作を行うと、操作後の数列は $(1, 4, 5)$ になる。

• 長さ $N$ の整数列 $A = (A_1, A_2, \dots, A_N)$ があります。
• あなたは以下の 挿入操作 を $0$ 回以上自由な回数繰り返すことができます。
  • 整数 $x$ を自由に選ぶ。$A$ の自由な位置に $x$ を $1$ 個挿入する。(位置は先頭および末尾でもよい)
• $A$ を良い数列にするには最小で何回挿入操作を行う必要がありますか？

• $T$ 個のテストケースが与えられるので、それぞれについて問題を解いてください。

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 全てのテストケースに対する $N$ の総和は $2 \times 10^5$ 以下
• 入力される値は全て整数

挿入操作は「マージ相手のいない要素に相手を与える」役割でしか使う意味は無い。
その要素はマージ後 $+1$ されるので、挿入操作は「任意のタイミングで任意の要素をインクリメント（$+1$）する操作」と言い換えることができる。要素数を固定できるので、少し考えやすくなる。（$N$ 個の要素を $N-1$ 回マージする）

値が減ることは無い以上、谷になっている箇所は、とりあえず両隣の近い方の要素までインクリメントするしかない。
より一般化して、谷底が平たい（同じ値が続く、例: $(...,5,1,1,1,4,...)$）場合も考慮すると、 左右の小さい方（$5,4$ のうちの $4$）と同じ値になるまでは、左端から貪欲にペアにしてマージ、1個余ったらインクリメント、という操作を繰り返すのがよい。$c$ 個の $x$ が、$\lceil \frac{c}{2} \rceil$ 個の $x+1$ になる。
$x$ の2箇所にインクリメントするのは、マージ後の $x+1$ の連続の1箇所へのインクリメントで代用でき、得しない。

以上を踏まえて、スタック $S$ を用いて管理する。
スタックには、各 $i=1,2,...,N$ の時点で、$A_1～A_i$ を最適と確定できる部分までマージした暫定結果が入っているとする。

スタックの中身は常に狭義単調減少となる。
そうでない箇所（$i \lt j, S_i \le S_j$ なる $(i,j)$）があると、$S_i$ は、$S_j$ より左の要素とのマージ操作やインクリメントを繰り返し、$S_j$ となるまで操作して損しない。
「最小値区間をまとめてマージする」ということを繰り返すのが最適のため、どこかで $i$ 周辺～$j-1$ のマージ結果が、全て1個以上の $S_j$ に揃うタイミングがあり、スタックにはそこまで処理した（そして、マージできるならした）結果を積んでいくことになる。

$i=1,2,3,...$ の順に、$A_i$ をスタックに追加しようとする際、スタックの末尾を $t$ として、以下のようになる。

• a) スタックが空 → スタックに追加
• b) $t \lt A_i$ → （後で更に場合分け）
• c) $t = A_i$ → マージして再帰
  • $t$ をpop、$A_i+=1$ し、最初に戻る
• d) $t \gt A_i$ → スタック末尾に追加
  • $t$ と、$i+1$ 以降に出てくる $A_j$ の大小関係によって、最適な処理がこの時点では決められないため

これで、b) 以外の処理は完了した。

b) の場合はスタックをさらに遡ってゆき、はじめて $S_j \ge A_i$ となる $j$ を探す。

• $j$ が存在しない（全て $A_i$ 未満）
  • スタックの値は全て1個の $A_i$ になるまで操作される。
  • コストは $A_i - t - |S|+1$（$t$ を $A_i$ までインクリメントする操作の内、$|S|-1$ 個はマージ相手がいる）
  • 空のスタックに $A_i+1$ を追加する。
• $S_j \gt A_i$
  • $j+1～t$ を1個の $A_i$ になるまで操作し、$A_i$ とマージする。
  • スタックは、$S_j$ が末尾になるまでpopし、その後、$A_i+1$ を末尾に追加する処理をおこなう。（ c) の場合も考慮）
  • コストは $A_i - t - (popした要素数) + 1$
• $S_j = A_i$
  • $j+1～t$ を1個の $A_i$ になるまで操作した後、（$A_i$ でなく）$S_j$ の方とマージする。
  • スタックは、$S_j$ までpopし、その後、$S_j+1$ を末尾に追加する処理をおこなう。
  • 更にその後、$A_i$ をappendする。
  • コストは $A_i - t - (popした要素数) + 2$

$i=N$ まで処理した後、狭義単調減少のスタックが残る。これも1つになるまでマージする。

• コストは $S_1-S_{tail} - |S| + 2$

以上のコストの総計が答えとなる。

Python3

def naive(n, aaa, print_debug=True):
    ans = 0
    while len(aaa) > 1:
        m = min(aaa)
        found = False
        for i in range(len(aaa) - 1):
            if aaa[i] == aaa[i + 1] == m:
                aaa = aaa[:i] + [m + 1] + aaa[i + 2:]
                found = True
                break
        if print_debug:
            print(f'{aaa=} {m=} {found=} {ans=}')
        if found:
            continue
        i = aaa.index(m)
        ans += 1
        aaa[i] += 1
    return ans


def solve(n, aaa):
    def delete_same_value(stack, a):
        while stack and stack[-1] == a:
            stack.pop()
            a += 1
        return a

    ans = 0
    stack = []
    for a in aaa:
        a = delete_same_value(stack, a)
        if len(stack) == 0:
            stack.append(a)
            continue
        if stack[-1] > a:
            stack.append(a)
            continue
        # stack[-1] < a 確定
        x = stack[-1]
        y = stack[-1]
        cnt = 0
        while stack and stack[-1] <= a:
            y = stack.pop()
            cnt += 1

        if y < a:
            ans += a - x - (cnt - 1)
            a = delete_same_value(stack, a + 1)
            stack.append(a)
            continue

        # y==a
        ans += a - x - (cnt - 2)
        b = delete_same_value(stack, y + 1)
        stack.append(b)
        stack.append(a)

    if len(stack) >= 2:
        ans += stack[0] - stack[-1] - len(stack) + 2

    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(ans)

B - Japanese "Knight's Tour"

• 縦 $H$ マス、横 $W$ マスの将棋盤と $1$ 個の桂馬の駒があります。
• 将棋盤の上から $i$ 行目、左から $j$ 列目にあるマスを $(i-1, j-1)$ と表します。(値が $1$ ずれている点に注意してください。)
• この将棋盤はトーラス、すなわち上と下および左と右がつながっています。$(i, j)$ にある桂馬は $((i-2) \bmod H, (j-1) \bmod W)$ または $((i-2) \bmod H, (j+1) \bmod W)$ に動かすことができます。
• 次の条件を満たすように桂馬を将棋盤の上で動かすことを ツアー と呼びます。
  • はじめ、$(0, 0)$ に桂馬を置く。
  • その後、桂馬が全てのマスにちょうど $1$ 回ずつ移動するように $H \times W$ 回桂馬を動かす。
  • 最終的に桂馬が $(0, 0)$ に戻ってくる。

• ツアーが何通りあるかを $998244353$ で割った余りを求めてください。ただし、$2$ つのツアーはある整数 $i$ $(1 \leq i \leq H\times W)$ が存在して $i$ 回目の移動先が異なる場合に異なるとみなします。

• $3 \leq H \leq 2 \times 10^5$
• $3 \leq W \leq 2 \times 10^5$
• 入力される値は全て整数

$H$ が偶数の時、奇数行目に行けないので $0$ 通り。以下、$H$ は奇数とする。

行 $(0,1,2,3,4,...,H-1)$ を、$(0,2,4,...,H-1,1,3,5,...,H-2)$ のように並べ替えて考える。
こうすると、桂馬の動きは「左斜め下か、右斜め下にのみ進む」と見なせ、考えやすくなる。

ある周回で $(i,j)$ に止まった桂馬が↘方向の $(i+1,j+1)$ に動いたとして、 別の周回で $(i,j+2)$ に止まった時の次の動きは、同じマスは踏めないので追従して↘に動くしかない。

(  i,   j)  (  i, j+1)  (  i, j+2)
          ↘                      ↘
(i+1,   j)  (i+1, j+1)  (i+1, j+2)  (i+1, j+3)  ...

この追従の連鎖はループして $i$ 行目の全てのマスに及ぶ。
各行から次の行への移動は全ての周回で同じ向きにならないといけない。

また、1周して次に $(0,j)$ を訪れたとき、$\gcd(W,j) = 1$ でないと、 全てのマスを巡る前に $(0,0)$ に戻ってしまう。

以上を踏まえ、1周後に訪れる列 $j$ （本来はループするので $\mod{W}$ するが、それをする前の値）を固定して、

• $j=-H,-H+2,...,-1,1,3,...,H$ のそれぞれに対し、
• $\gcd(W,j)=1$ ならば、
• ${}_H \mathrm{C}_{(H+j)/2}$ を答えに加算する

とすれば求められる。

偶数ループ目と奇数ループ目の進む方向は独立に決められる。同じ偶奇での方向は全て同じにならないといけない。

$W$ 奇数の時の議論を、2周分の方向をまとめて決めるように適用すればよい。

• $j=-2H,-2H+2,...,-2,2,...,2H$ のそれぞれに対し、
• $\gcd(W,j)=2$ ならば、
• ${}_{2H} \mathrm{C}_{(2H+j)/2}$ を答えに加算する

Python3

from math import gcd


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(h, w):
    MOD = 998244353
    if h % 2 == 0:
        return 0

    facts, finvs = precompute_factorials(h * 2, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] * finvs[n - r] % MOD

    if w % 2 == 1:
        ans = 0
        for i in range(1, h + 1, 2):
            if gcd(w, i) != 1:
                continue
            a = (h - i) // 2
            tmp = ncr(h, a)
            ans += tmp * 2
            ans %= MOD
        return ans

    ans = 0
    for i in range(2, 2 * h + 1, 2):
        if gcd(w, i) != 2:
            continue
        a = (2 * h - i) // 2
        tmp = ncr(h * 2, a)
        ans += tmp * 2
        ans %= MOD
    return ans


h, w = map(int, input().split())
ans = solve(h, w)
print(ans)

C - Repunits

• 正整数 $n$ に対して $R_n$ を「$1$ を $n$ 個並べてできる文字列を $10$ 進表記された整数と解釈したもの」として定義します。例えば $R_3 = 111$ です。
• 正整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。
• $k = 1, 2, \dots, N$ について $\mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353$ を計算してください。ここで $\mathrm{LCM}$ は最小公倍数を計算する関数とします。

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$
• 入力される値は全て整数

例えば、111111 は 11 でも 111 でも割り切れるように、$R_n$ は、$R_{nの約数}$ を全て因数に持つ。
$R_n,R_m$ は、共通して $R_{\gcd(n,m)}$ を因数に持つことはわかる。

では、$\gcd(R_n,R_m)=R_{\gcd(n,m)}$ は成り立つか？
$R_n$ の約数にも $R_m$ の約数にも表れる $R_{\gcd(n,m)}$ を構成する以外の素因数が絶対にないと言えるか？

結果的には成り立つが、証明が必要。
$R_n$ は $2$ と $5$ を素因数に持たないことから、 差を考慮することで、$\gcd(R_n,R_m)=\gcd(R_{n-m},R_m)$ を示せる。
これを繰り返し、ユークリッドの互除法に似たアルゴリズムを適用すれば、$\gcd(R_n,R_m)=R_{\gcd(n,m)}$ が示せる。

• $\gcd(R_{14},R_{10}) = \gcd(R_{14}-R_{10}, R_{10})$
  • $= \gcd(11110000000000, R_{10})$
  • $= \gcd(R_4 \times 10^{10}, R_{10})$
  • $= \gcd(R_4,R_{10})$

$R_1,R_2,...,R_{m} \mod{P}$ とその逆数を計算するのは $O(m \log{P})$ でできるので、 それらを前計算しておけば、任意の2数のLCMなら求められることがわかった。

元の問題に戻る。
$L_i=\operatorname{lcm}(R_{A_1},R_{A_2},...,R_{A_{i}})$ として、 $z_i=\dfrac{L_i}{L_{i-1}}$ が求められれば、それをかけていけば順次答えが求められる。

一般的には $z_i=\dfrac{R_{A_i}}{\gcd(L_{i-1},R_{A_i})}$ なのだが、巨大数のGCDは求めづらい。
直感的には、「$R_{A_i}$ の因数のうち、$L_{i-1}$ に既に含まれている因数を除き、まだのやつのみをかける」と$L_i$ になる。

$R_{A_i}$ の何らかの因数が、$L_{i-1}$ に既に含まれているのを気にするのは、 $A_i$ と互いに素でない数が $A_1～A_{i-1}$ に含まれていた場合に限られる。
その数を $A_j$ とし、$A_j$ 処理時に、$A_j$ の各約数 $d$ につき 「因数に $d$ を持つ要素はもう使ったよ～」という情報を残しておけば、 $A_i$ 処理時に「$d$ は既にあるのでかけてはいけない」とわかる。

具体的には、任意の $x$ について以下を満たすような数列 $F$ を定義する。

• $\displaystyle R_n = \prod_{d|n}F_d$
  • （例）$R_{12}=F_1F_2F_3F_4F_6F_{12}$

$A_i$ を処理する時、$A_i$ の約数のうち、まだ $L_{i-1}$ にかけられていない $F_d$ をかけていけば $L_i$ が求められる。

$1～n$ の約数の個数の総和は $O(n \log{n})$ と見積もれるので、$k=2,3,...,n$ から順番に、

• $k$ の約数を求める
• 各約数 $d$ について、$R_k$ を $F_d$ で割っていく（mod逆数をかけていく）

ことで、$F_d$ を前計算できる。
計算量は $M=\max(A)$ として、$O(M (\log{M}+\log{\mathrm{mod}}))$ 程度で行える。
（公式Editorialでは、$O(M \log{\log{M}} + \log{\mathrm{mod}})$ でできるらしいことが書かれている）

Python3

from itertools import product
from math import prod


def get_spf(n):
    """ nまでの各数を割り切る一番小さな素数 """
    spf = list(range(n + 1))
    for i in range(2, n + 1, 2):
        spf[i] = 2
    for p in range(3, int(n ** 0.5) + 1, 2):
        if spf[p] == p:
            for m in range(p * p, n + 1, 2 * p):
                if spf[m] == m:
                    spf[m] = p
    return spf


def prime_factorize(x, spf):
    """ xを素因数分解、(素数, 個数)の配列で返す """
    factors = []
    prev = -1
    cnt = 0
    while x > 1:
        if spf[x] == prev:
            cnt += 1
        else:
            if prev != -1:
                factors.append((prev, cnt))
            prev = spf[x]
            cnt = 1
        x //= spf[x]
    if prev != -1:
        factors.append((prev, cnt))
    return factors


def enumerate_divisors(x, spf):
    factors = prime_factorize(x, spf)
    exps = [[p ** e for e in range(cnt + 1)] for p, cnt in factors]
    return [prod(combo) for combo in product(*exps)]


def solve(n, aaa):
    MOD = 998244353

    rep = [0] * 200001
    for i in range(1, 200001):
        rep[i] = (rep[i - 1] * 10 + 1) % MOD

    pre = [0] * 200001
    inv = [0] * 200001
    pre[1] = inv[1] = 1
    spf = get_spf(200000)
    for i in range(2, 200001):
        divisors = enumerate_divisors(i, spf)
        tmp = rep[i]
        for d in divisors[:-1]:
            tmp *= inv[d]
            tmp %= MOD
        pre[i] = tmp
        inv[i] = pow(tmp, -1, MOD)

    ans = []
    appeared_a = set()
    appeared_divisor = [0] * 200001
    tmp = 1
    for a in aaa:
        if a in appeared_a:
            ans.append(tmp)
            continue
        appeared_a.add(a)

        divisors = enumerate_divisors(a, spf)
        for d in divisors:
            if appeared_divisor[d] == 0:
                appeared_divisor[d] = 1
                tmp *= pre[d]
                tmp %= MOD
        ans.append(tmp)

    return ans


def naive(n, aaa):
    from math import gcd
    MOD = 998244353
    ans = []
    ans_row = []
    tmp = 1
    for a in aaa:
        r = int('1' * a)
        g = gcd(tmp, r)
        tmp *= r // g
        ans.append(tmp % MOD)
        ans_row.append(tmp)
    return ans, ans_row


def check():
    n = int(input())
    aaa = list(map(int, input().split()))
    ans1 = solve(n, aaa)
    ans2, ans3 = naive(n, aaa)
    print(f'{ans1=}')
    print(f'{ans2=}')
    print(f'{ans3=}')


# check()

n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print('\n'.join(map(str, ans)))