NS Solutions Corporation Programming Contest 2022(AtCoder Beginner Contest 257)
C,Dなど、解法自体は単純だがそこに至るまでの発想に少しまごつく問題があった。
「一方の端点の決まっていない辺」を「ワープ辺」、 「ワープ辺のもう一方の端点」となっている頂点を「ワープ頂点」と呼ぶことにする。
ワープ辺は全て同じ頂点に結びつけられる、というのがポイント。
どこに結びつけられようと、最短経路においては同じ頂点を2回通るのは明らかに無駄。
なので、例えばワープ辺を頂点 $i$ に結びつける場合、
この4タイプしかない。(⇒ がワープ辺)
$1$ と $N$ から、それぞれワープ辺を使わない全頂点への距離を求めておく。
その時点で到達できない頂点への距離は、番兵として非常に大きな値を入れておくとよい。
「$1$ → 最寄りのワープ頂点」「最寄りのワープ頂点 → $N$」は、$k$ によらず固定なので事前に求められる。
その後、$i=1,2,...,N$ について4タイプを全て試して、最小値をとればよい。
これが番兵と等しいなら、到達不可能となる。
ワープ辺が1つもない場合に、最寄りのワープ頂点を計算しようとしてエラーを出さないように注意。(1WA)
S = abaab T = ababaaab ↓ ab + abaa + ab 3つの、Sのprefixに分割できる
文字列の問題は、(ABCに出てくる範囲では、おそらく)使うアルゴリズムが限られるので、 問題の性質よりも「文字列アルゴリズム」の側から使えそうなものがないか探すというハックが有効に働く場合がある。
prefixに関する問題で、Z-Algorithmが解法となるものは過去にも何回か出ている。
以下、○文字目というのは 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$ の更新回数+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$ まで至れるかを調べてもよい。