Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2469-8c9aae50
この記事にトラックバックする(FC2ブログユーザー)

Timus 1996 - Cipher Message 3 (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1996

問題概要

$n$ 個のバイト($8$ ビット)からなる列 $A$ と,$m$ 個のバイトからなる列 $B$ が与えられる.
何箇所か $A$ の要素のうち最下位ビットを書き換えて良い.
そうして,$A$ の連続する部分バイト列で, $B$ と一致する部分を作りたい.
書き換える最小ビット数と,それで一致させることができる場所を求める問題.
場所は複数あるなら,一番最初のものを求める.
$1 \leq n, m \leq 250000$

解法

$m > n$ なら不可能.
上位 $7$ ビットは全部一致しなければならない.
一致する場所は,ローリングハッシュやKMPを使って求める.
各場所で何文字置き換えなければいけないかはFFTすれば良い.
例えば,$B$ を逆順にして,最下位ビットが $0$ なら $-1$ とみなして,$1$ なら $1$ とみなすなどとすれば,$3$ 回のFFT($A$ で $1$ 回,$B$ で $1$ 回,逆変換 $1$ 回)で計算できる.
一致する場所は $1$,一致しない場所は $-1$ が出てくる.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2469-8c9aae50
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。