難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) Lv.5.5 (2票)

投票の分布
  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.51票
  6. Lv.61票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Periodic Noise

作成者 yuki4869

難易度(作成者設定) Lv.5

難易度(投票) Lv.5.5 (2票)

実行時間制限
2 秒
メモリ制限
512 MiB

解説

KK 個離れた項の差を取ると、Z-algorithmで解くことができます。

まず、ii を固定して考えます。BB の最初の KK 項には、それぞれ異なる CjC_j を加えられるため、自由に値を調整できます。したがって、少なくとも min⁡(K,N−i+1)\min(K,N-i+1) 項は一致させられます。

一方、BjB_j と Bj+KB_{j+K} には同じ整数を加えるため、この 22 項の差は操作によって変わりません。よって、先頭 LL 項を一致させるためには、すべての 1≤j≤L−K1\le j\le L-K について

Ai+j+K−1−Ai+j−1=Aj+K−AjA_{i+j+K-1}-A_{i+j-1} = A_{j+K}-A_j

が成立する必要があります。

逆に、この等式がすべて成立するなら、最初の KK 項を一致させるように C1,…,CKC_1,\ldots,C_K を選ぶことで、以降の項も順に一致します。したがって、これは必要十分条件です。

ここで、長さ M=N−KM=N-K の整数列 DD を

Dj=Aj+K−Aj(1≤j≤M)D_j=A_{j+K}-A_j \qquad (1\le j\le M)

と定義します。先ほどの条件は

Di+j−1=Dj(1≤j≤L−K)D_{i+j-1}=D_j \qquad (1\le j\le L-K)

と書き換えられます。つまり、DD とその接尾辞 (Di,…,DM)(D_i,\ldots,D_M) の先頭が何項一致するかを求めればよいことになります。

この最長共通接頭辞の長さを ZiZ_i とすると、答えは

Li={K+Zi(1≤i≤M),N−i+1(M<i≤N)L_i= \begin{cases} K+Z_i & (1\le i\le M),\\[2mm] N-i+1 & (M<i\le N) \end{cases}

です。後者では接尾辞の長さが KK 以下なので、すべての項を一致させられます。また、前者では Zi≤M−i+1Z_i\le M-i+1 より、K+Zi≤N−i+1K+Z_i\le N-i+1 が保証されます。

Z1,…,ZMZ_1,\ldots,Z_M は、整数列 DD にZ-algorithmを適用することでまとめて求められます。M>0M>0 の場合は Z1=MZ_1=M とします。K=NK=N の場合は DD が空となり、すべての ii で Li=N−i+1L_i=N-i+1 です。

DD の構築とZ-algorithmはいずれも O(N)O(N) 時間なので、全体の計算量は O(∑N)O(\sum N)、必要な追加メモリは O(N)O(N) です。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。