UVa 13042 - Ikroch

Source

A Bangladeshi Contest at SUST（20151212）
UVa 13042

問題概要

$2$ つの文字列 $s,t$ に関するIkroch距離とは，任意の $1$ 文字を消す，任意の場所に任意の文字を入れるという $2$ つの操作ができるときに $s$ を $t$ に一致させるために必要な操作の最小回数とする．
辞書に載っている $C$ 個の単語のリストとして $D_1,D_2,\ldots,D_C$ が与えられる．
また，各単語 $D_i$ には重み $W_i$ が付随している．
各単語はアルファベット小文字のみからなる．
検索エンジンにおける $P$ 個の検索クエリ $Q_1,Q_2,\ldots,Q_P$ が与えられる．
検索クエリ $Q_i$ は，アルファベット小文字のみからなる文字列をいくつか半角スペース区切りで連結した後，最後に半角スペースと整数 $X_i$ をくっつけたものである．
検索クエリ内の各単語について，以下の処理を行い，検索クエリを修正して，修正されたクエリを出力する問題．

その単語が辞書内に存在するなら，その単語はそのままにする
そうでないならば，その単語とIkroch距離が $X_i$ 以下の単語を辞書から見つけてきて，それに置き換える
複数見つかった場合は重みが最も大きい物，それでも複数あるならば，辞書順で最初のものと置き換える
もし，Ikroch距離が $X_i$ 以下の単語が見つからないなら，その単語を削除する
最後に，最後の半角スペースと整数 $X_i$ を削除する

テストケースの数 $T$ は $T \leq 10$ を満たす
$1 \leq C \leq 40000\ (4 \times 10^4)$
$1 \leq |D_i| \leq 10$，$|D_1|+|D_2|+\cdots+|D_C| \leq 200000\ (2 \times 10^5)$
$1 \leq W_i \leq 1000\ (10^3)$
$1 \leq P \leq 100000\ (10^5)$
$1 \leq |Q_i| \leq 50$，$|Q_1|+|Q_2|+\cdots+|Q_P| \leq 200000\ (2 \times 10^5)$
$0 \leq X_i \leq 1$
クエリ $Q_i$ に含まれる任意の単語の長さは $10$ 以下

解法

まず，ある単語が辞書にあるかどうか，その単語の重みは何かはsetか何かに突っ込んでおいてすぐ探せるようにしておく．
クエリ内の各単語について，$X_i=0$ ならば，辞書にその単語があるかどうか判定するだけで良い．
$X_i=1$ ならば，$1$ 文字削除したもの，$1$ 文字任意の場所に付け加えたものを列挙し，それらの単語が辞書にあるかどうかを確かめる．
C++で $\verb|map<string,int>|$ などとしたらTLEしたので，文字列はハッシュにして整数値に直して格納した．

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります．

Current time: 2024年04月19日16時09分01秒
Last modified: 2015年12月16日02時04分26秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る

Logged in as: unknown user (not login)