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$ をくっつけたものである.
検索クエリ内の各単語について,以下の処理を行い,検索クエリを修正して,修正されたクエリを出力する問題.

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

解法

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

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

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


Current time: 2017年07月23日17時35分20秒
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)

ログイン: