2015年2月14日土曜日

yukicoder 150 "良問"(良問とは言っていない

問題

http://yukicoder.me/problems/344
要するに入力された文字列sを、
先頭から見たときに"good","problem"がこの順に見つかるようにするためには何文字変更するべきかを求める問題。
100個の100字以内の文字列に対して探さなければならない。

解法

tbl1[i] = str[0~i]の中で"good"とのハミング最小距離
tbl2[i] = str[i~n-1]の中で"problem"とのハミング最小距離
とすると,tbl1[i]+tbl2[i+1]で求めることが出来る。

tbl1[i] = min(tbl[i-1], haming("good", str[i-3~i])
で求められるのでO(4・n) = O(n)
tbl2も同様にして求めることが出来る。
なので全体としてO(n)で求めることが出来る。


0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...