Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12682 - Joe is learning to speak (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12682

問題概要

Joe君は,昨日までに聞いた英語の文章の連続する $k$ 個の単語の列を全部覚えている($k=1,2,\ldots,n$ で $n$ は入力で与えられる).
また,Joe君は,"Joe"という単語は既に知っており,昨日までに聞いた英語の文章は全部与えられる.
今日聞いた文章が $1$ つずつ与えられるので,各文章に対して
 知らない単語があれば,その単語の意味を聞く
 文章が $2$ つ以上の単語からなり,その文章の連続する $k$ 個の単語の列で,知らないものが $1$ つでもあれば,文章の意味を聞く($k=1,2,\ldots,n$)
もちろん,$1$ 度聞いた文章は昨日聞いた文章と同様に覚える.
Joe君が発する言葉を出力する問題.
単語は,大文字と小文字が違うだけのものは同じとみなす.
Joe君が単語の意味,文章の意味を聞くときは,その時与えられた文章,単語と同じように大文字小文字を使い分ける.
$2 \leq n \leq 5$
$1$ 単語の文字数は $20$ 文字以下で,アルファベットのみ.
$1$ つの文章に含まれる単語の数は $100$ 以下.
出てくる単語の種類は合計で $2 \times 10^4$ 以下
前日に聞いた文章,今日聞いた文章の数はそれぞれ $1000$ 以下

解法

頑張って実装する.
文字列をそのまま扱うと重たいので,単語の連続する列をハッシュ値に変換にしてsetに突っ込んだ.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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