AtCoder × Engineer Guild オンサイトコンテスト ～ACからはじまる27卒キャリア～予選　（AtCoder Beginner Contest 446）E,F,G問題メモ

AtCoder × Engineer Guild オンサイトコンテスト ～ACからはじまる27卒キャリア～予選　（AtCoder Beginner Contest 446）

E - Multiple-Free Sequences

• $0 \leq x,y \leq M-1$ を満たす整数組 $(x, y)$ のうち、以下の漸化式で表される無限長の数列 $(s_1, s_2, \dots)$ が $M$ の倍数を全く含まないようなものは何通りありますか？
  • $s_1 = x$
  • $s_2 = y$
  • $s_n = A s_{n-1} + B s_{n-2}$ ($n \geq 3$)

• $2 \leq M \leq 1000$
• $0 \leq A, B \leq M-1$
• 入力される値はすべて整数

本番で解法が思いつかなかった。う～む。
各項は必ず第1,2項を使って $a \cdot s_1 + b \cdot s_2$ で表せることにとらわれ、 $s_1,s_2$ ごとに、この $a,b$ がループするまでの全てに $M$ の倍数が含まれなければよい、 みたいな方向は思いつくが、これだと $O(M^4)$ かかる。

$a,b$ よりもっと単純に、隣り合う2項 $(s_i,s_{i+1}) \mod{M}$ がループするかどうかを調べればよかった。

ある隣接2項が $(p,q)$ の時、それを1つ進めた次の隣接2項は $(q,Aq+Bp)$ となる。

..., p, q, Aq+Bp, A(Aq+Bp)+Bq, A(A(Aq+Bp))+B(Aq+Bp), ...

数列は無限に続くので、$(x,y)=(p,q)$ とした数列が $M$ の倍数を含むかは、 （$p=0$ で無い限り）$(x,y)=(q,Aq+Bp)$ とした数列の結果と一致する。

よって、$(p,q)→(q,Aq+Bp)→(Aq+Bp,A(Aq+Bp)+Bq)→... \mod{M}$ と辿っていって、$(*,0)$ が出てくればアウト。
$0$ が出てこずループすれば $M$ の倍数は含まれないと言える。

逆向き $(q,Aq+Bp)→(p,q)$ に辺を張ったグラフで $(*,0)$ から探索したり、 再帰関数で $(*,0)$ またはループに辿り着くまで調べるなどで、 $O(M^2)$ で各 $(p,q)$ が条件を満たすか求められる。

Python3

import sys

sys.setrecursionlimit(1_000_000)


def solve(m, a, b):
    ans = [[-1] * m for _ in range(m)]
    for i in range(m):
        ans[0][i] = ans[i][0] = 0

    def search(i, j):
        ni, nj = j, (a * j + b * i) % m
        if ans[ni][nj] == -2:
            ans[i][j] = 1
        elif ans[ni][nj] == -1:
            ans[i][j] = -2
            search(ni, nj)
            ans[i][j] = ans[ni][nj]
        else:
            ans[i][j] = ans[ni][nj]

    for i in range(1, m):
        for j in range(1, m):
            if ans[i][j] == -1:
                search(i, j)

    ans = sum(map(sum, ans))
    return ans


m, a, b = list(map(int, input().split()))
ans = solve(m, a, b)
print(ans)

F - Reachable Set 2

• $N$ 頂点 $M$ 辺の有向グラフ $G$ が与えられます。
• $k=1,2,\ldots,N$ について以下の問題を解いてください。
  • 高橋君の目標は、$G$ から（$0$ 個でも良い）いくつかの頂点、およびそれらの頂点を始点または終点として持つすべての辺を削除することで、次の条件をみたすようにすることです。
    • 頂点 $1$ から $0$ 本以上のいくつかの辺を辿って到達可能な頂点が頂点 $1,2,\ldots,k$ のみである。
    • 高橋君が目標を達成することが可能か判定し、可能な場合は目標を達成するために高橋君が最低何個の頂点を削除する必要があるか求めてください。

• $2\leq N\leq 3\times 10^5$
• $1\leq M\leq 3\times 10^5$
• $1\leq U_i,V_i\leq N$
• 入力はすべて整数

$k$ が小さい方から求めていく。

たとえば $k=5$ の時に訪れてよい頂点は $k \ge 6$ でも訪れてよいので、 $k$ が進むごとに徐々に探索を広げていく、という方法が使える。

①から探索済み頂点の個数を $C$ とする。
探索済み頂点から、次に探索を広げられる未探索頂点のリストを $Q$ とし、$Q=[1]$ で初期化する。

①→②→④→③
      ↘↑
        ⑤

k=1
  ①以下の頂点に探索を進める。（①のみ）
  C=1, Q=[2]
  k=C の場合、目標を達成できる。この時、Q にある頂点を消せば良いので、|Q| = 1 が答えとなる。

k=2
  ②以下の頂点に探索を進める。
  C=2, Q=[4,5]
  k=C なので、目標を達成できる。|Q| = 2 が答えとなる。

k=3
  ③以下の頂点に探索を進める。
  C=2, Q=[4,5]
  k>C なので、目標を達成できない。

k=4
  ④以下の頂点に探索を進める。新たにQに加えられた頂点でもk以下である限り探索は広げる。
  C=4, Q=[5]
  k=C なので、目標を達成できる。|Q| = 1 が答えとなる。

k=5
  ⑤以下の頂点に探索を進める。
  C=5, Q=[]
  k=C なので、目標を達成できる。|Q| = 0 が答えとなる。

$Q$ は優先度付きキューなどで実装すればよい。

Python3

from heapq import heappop, heappush


def solve(n, m, edges):
    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)

    hq = [0]
    queued = [False] * n
    queued[0] = True
    visited_count = 0
    buf = []
    for i in range(n):
        while hq and hq[0] <= i:
            u = heappop(hq)
            visited_count += 1
            for v in links[u]:
                if queued[v]:
                    continue
                heappush(hq, v)
                queued[v] = True
        if visited_count == i + 1:
            buf.append(len(hq))
        else:
            buf.append(-1)
    return buf


n, m = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print('\n'.join(map(str, ans)))

G - 221 Subsequence

• 正整数からなる数列 $X = (X_1, \dots, X_n)$ に対し、その連長圧縮の任意の (長さ・値) ペアにおいて長さと値が等しいとき、かつそのときに限り、$X$ を 221 数列 と呼びます。
  • たとえば、$(2,2,3,3,3,1,2,2)$ は連長圧縮で $[(2,2),(3,3),(1,1),(2,2)]$ となるため 221 数列です。
  • $(1,1)$ や $(4,4,1,4,4)$ は 221 数列ではありません。
• 長さ $N$ の正整数列 $A = (A_1, \dots, A_N)$ が与えられます。$A$ の空でない(連続とは限らない)部分列であって、221 数列であるものの個数を $998244353$ で割ったあまりを求めてください。
• ただし、異なる位置から取り出した部分列であっても、数列として一致するものは区別せずまとめて $1$ 通りとして数えます。

• $1 \leq N \leq 500\,000$
• $1 \leq A_i \leq N$
• 入力される値はすべて整数

少しテクニカルなDP。

例えばある $i$ において、$A_i=3$ だったとする。
「取り出す部分列において、$i$ から開始して $3$ を $3$ 個連続させるように取る」場合、 「できるだけ左詰で取るもののみを数える」とすると、重複を避けられる。

以下のDPを定義する。

• $\mathrm{DP}[i,k]:=i$ までから取れる、末尾要素が $k$ であるような221数列の個数

$i$ から数えて $3$ 個先の $3$ がある位置を $j$ とする。

       i                 j
... *  3  *  *  *  3  *  3  *  3  *  ...

この時、$\mathrm{DP}[j,3]$ には、$\mathrm{DP}[i-1,k]$ のうち、$k \neq 3$ であるもの全てから遷移できる。

• $\displaystyle \mathrm{DP}[j,3] = \sum_{k \neq 3}\mathrm{DP}[i-1,k]$

「$i-1$ より前から取れる末尾要素が $3$ である221数列で、$i～j$ の要素は一切取らない」 ものとの重複を避けるため、加算ではなく上書きで更新する。

だが、DPの状態数が $O(N^2)$ なので、この通りに実装することはできない。

$i$ の時に更新すべき値を計算しておいた上で、 「$j$ まで進んだら、$\mathrm{DP}[j,k]$ をこの値で更新してね」という値をメモっておくことで、 DPから $i$ の次元を省略し、破壊的に更新していくことができる。

Python3

from collections import defaultdict


def solve(n, aaa):
    MOD = 998244353

    pos = defaultdict(list)
    indices = []
    for i in range(n):
        a = aaa[i]
        indices.append(len(pos[a]))
        pos[a].append(i)

    additions = [0] * n
    dp = [0] * (n + 1)
    dp[0] = 1
    total = 1
    for i in range(n):
        a = aaa[i]
        pi = indices[i]
        if len(pos[a]) >= pi + a:
            j = pos[a][pi + a - 1]
            additions[j] = (total - dp[a]) % MOD
        inc = additions[i] - dp[a]
        dp[a] = additions[i]
        total += inc
        total %= MOD
    total -= 1
    total %= MOD
    return total


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(ans)