Codeforces Beta Round #86 Div. 1 Only

Codeforces Beta Round #86 Div. 1 Only (9/9 0:00~2:00）

■A. A Grammar Lessons

問題

Petyaの作った言語は以下のBNFにより定義される．与えられた文字列がSentenceか判定せよ．

Sentence := Statement | AdjectiveM | AdjectiveF | NounM | NounF | VerbM | VerbF
Statement := (AdjectiveM* NounM VerbM*) | (AdjectiveF* NounF VerbF*)

AdjectiveM := "lios" | Alphabet AdjectiveM
AdjectiveF := "liala" | Alphabet AdjectiveF
NounM := "etr" | Alphabet NounM
NounF := "etra" | Alphabet NounF
VerbM := "initis" | Alphabet VerbM
VerbF := "inites" | Alphabet VerbF

Alphabet := "a"|"b"|"c"|…|"z"

解法

書くだけ．StatementのBNFをDFAにしてからコードにすると，機械的に解ける．
#86 Div. 1 A. A Grammar Lessons

■B. Petr#

問題

文字列s，s_begin，s_endが与えられる．
以下を満たす文字列tの個数を求めよ．

• tはsの部分文字列
• s_beginはtのprefix
• s_endはtのsuffix

解法

sにおいて，s_beginおよびs_endを検索して，インデックスの候補を列挙する．
s_begin，s_endに関するインデックスks，keについて，
s[ks]からs_beginがあり，
s[ke]からs_endがあり，
ks≦ke かつ ks+|s_begin|≦ke+|s_end|
ならば，
s[ks],…,s[ke],…,s[ke+|s_end|-1]
が条件を満たす文字列．
条件を満たす文字列を逐一生成すると，TLEするので，
ハッシュを計算し，重複要素を取り除くことで高速化．
#86 Div. 1 B. Petr#

■Result

o---- 254pts. 215th
1684->1700