日鉄ソリューションズプログラミングコンテスト 2022（AtCoder Beginner Contest 257）F,G問題メモ

NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

C,Dなど、解法自体は単純だがそこに至るまでの発想に少しまごつく問題があった。

F - Teleporter Setting

• $N$ 頂点 $M$ 辺の無向グラフが与えられる
  • 1辺の距離を1とする
• 一部の辺は、結ぶ一方の端点が決まっていない（入力では頂点番号 “0” として表される）
• $i=1,2,...,N$ のそれぞれについて、以下の問題に答えよ
  • 決まっていない端点 “0” を全て $i$ に置き換えたグラフにおいて、$1→N$ への最短距離を求めよ
  • 到達が不可能な場合は “-1” とせよ
• $1 \le N, M \le 3 \times 10^5$

「一方の端点の決まっていない辺」を「ワープ辺」、 「ワープ辺のもう一方の端点」となっている頂点を「ワープ頂点」と呼ぶことにする。

ワープ辺は全て同じ頂点に結びつけられる、というのがポイント。
どこに結びつけられようと、最短経路においては同じ頂点を2回通るのは明らかに無駄。

なので、例えばワープ辺を頂点 $i$ に結びつける場合、

1. ワープ辺を使わない経路
2. $1$ → 最寄りのワープ頂点 ⇒ $i$ → $N$
3. $1$ → $i$ ⇒ 最寄りのワープ頂点 → $N$
4. $1$ → 最寄りのワープ頂点 ⇒ $i$ ⇒ 最寄りのワープ頂点 → $N$

この4タイプしかない。（⇒ がワープ辺）

$1$ と $N$ から、それぞれワープ辺を使わない全頂点への距離を求めておく。
その時点で到達できない頂点への距離は、番兵として非常に大きな値を入れておくとよい。

「$1$ → 最寄りのワープ頂点」「最寄りのワープ頂点 → $N$」は、$k$ によらず固定なので事前に求められる。

その後、$i=1,2,...,N$ について4タイプを全て試して、最小値をとればよい。
これが番兵と等しいなら、到達不可能となる。

ワープ辺が1つもない場合に、最寄りのワープ頂点を計算しようとしてエラーを出さないように注意。（1WA）

Python3

from collections import deque

INF = 1 << 60


def bfs(n, links, s):
    q = deque()
    q.append(s)
    dists = [INF] * n
    dists[s] = 0
    while q:
        u = q.popleft()
        du = dists[u]
        for v in links[u]:
            if dists[v] <= du + 1:
                continue
            dists[v] = du + 1
            q.append(v)
    return dists


n, m = map(int, input().split())
links = [set() for _ in range(n)]
shortcuts = []
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if u == -1:
        shortcuts.append(v)
    else:
        links[u].add(v)
        links[v].add(u)

dists_1 = bfs(n, links, 0)
dists_n = bfs(n, links, n - 1)
base = dists_1[-1]

if shortcuts:
    nearest_1 = min(dists_1[i] for i in shortcuts)
    nearest_n = min(dists_n[i] for i in shortcuts)
else:
    nearest_1 = INF
    nearest_n = INF

for i in range(n):
    ans = min(
        base,
        nearest_1 + 1 + dists_n[i],
        dists_1[i] + 1 + nearest_n,
        nearest_1 + 2 + nearest_n,
    )
    if ans >= INF:
        print(-1)
    else:
        print(ans)

G - Prefix Concatenation

• 文字列 $S,T$ が与えられる
• $T$ を「$S$ のprefixをつなげたもの」として構築可能か調べ、可能なら分割の最小数を求めよ
• $1 \le |S|,|T| \le 5 \times 10^5$

S = abaab
T = ababaaab
       ↓
    ab + abaa + ab    3つの、Sのprefixに分割できる

文字列の問題は、（ABCに出てくる範囲では、おそらく）使うアルゴリズムが限られるので、 問題の性質よりも「文字列アルゴリズム」の側から使えそうなものがないか探すというハックが有効に働く場合がある。

prefixに関する問題で、Z-Algorithmが解法となるものは過去にも何回か出ている。

• 文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

以下、○文字目というのは 0-indexed とする。

Z-Algorithmというのは「自身の0文字目からと、自身の $i$ 文字目からが、最長何文字一致するか」を $O(文字列長)$ で求めるアルゴリズムだが、このままでは1つの文字列に対する情報しか得られない。

絶対に $S,T$ に出てこない文字（たとえば “!”）をはさんで「S!T」に対して適用することで、「$S$ の0文字目からと $T$ の $i$ 文字目から」の一致を得ることができる。

さて、上記の例に対してZ-Algorithmを用い、$T$ の部分だけを取り出すと、以下のようになる。

i   01234567
S = abaab
T = ababaaab

i    0  1  2  3  4  5  6  7
Z = [3, 0, 4, 0, 1, 1, 2, 0]

$Z[i]=k$ は、この問題に即して意味を与えれば、「もし、$T$ の先頭から $i-1$ 文字目までを構築可能なら、$i$ 文字目からは最長 $i+k-1$ 文字目まで構築可能文字数を伸ばせるよ」といえる。

たとえば $Z[2]=4$ は、「$T$ の先頭から1文字目を構築可能なら、2文字目から最長5文字目までは'abaa'によって構築可能」である。
最長、というのは、途中で切っても（'abaa'のうち'aba'だけを利用しても）prefixであることに変わりは無いので問題ないため。

よって、$i=0$ から始めて、

• $i+Z[i]-1$ までは構築可能
• $j=i+1,...,i+Z[i]$ について、$j+Z[j]$ を求めて、さらに構築可能距離を伸ばせるか調べる
  • $T$ の長さに満たないのにそれ以上伸ばせなくなったら不可能
• 移動可能距離を最も遠いところまで伸ばせる点を $k$ として、$i←k$ に更新
• $i+Z[i]=N$ になったら終了

というのを繰り返せば、$i$ の更新回数+1が答えとなる。

上記を愚直にやると $j$ が同じところを何度も調べることになり得るためTLEだが、 $i←k$ に更新したとき、（更新前）$i+Z[i]$ までは既に調べ終えていて、 その上で $k+Z[k]$ より大きい値が存在しなかったことがわかっているので、 次に $j$ として調べる範囲は $j=i+Z[i]+1,...,k+Z[k]$ でよい。全体で $O(|T|)$ で調べられる。

もしくは、以下のようにすると多少わかりやすい？

i    0  1  2  3  4  5  6  7
Z = [3, 0, 4, 0, 1, 1, 2, 0]

Y = [3, 1, 6, 3, 5, 6, 8, 7]    Zにiを加算
X = [3, 3, 6, 6, 6, 6, 8, 8]    Yの累積MAX

これで、$i=0$ から、$i←X[i]$ の更新を繰り替えし、無限ループにならず $i=N$ まで至れるかを調べてもよい。

Python3

from itertools import accumulate


def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        z[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + z[k] < j:
            z[i + k] = z[k]
            k += 1

        i += k
        j -= k

    return z


s = input()
t = input()
sl = len(s)
tl = len(t)

z = z_algorithm(s + '$' + t)
x = z[sl + 1:]

y = [i + x for i, x in enumerate(x)]
acc = list(accumulate(y, func=max))

ans = 0
i = 0
while i < tl and i < acc[i]:
    ans += 1
    i = acc[i]

if i == tl:
    print(ans)
else:
    print(-1)