WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Statement訳マルコは回文というものがあることを知った。回文とは左から読んでも右から読んでも同じになるものである。"radar"や"racecar"は回文である。マルコは回文となっている文字列がとても好きであり、特に回文となる部分文字列がたくさん含まれているものが好きである。彼は"aaa"という文字列がとても好きである。それは、"a"という回文が3つ、"aa"という回文が2つ、"aaa"という回文が1つの、6つの回文となる部分文字列が含まれているからだ。マルコは、全て小文字のSという文字列について考えている。S2が与えられるので、まず下記のようにしてSを得てほしい。S1の全ての文字列を順番に結合してAという文字列を得る。S2の全ての文字列を順番に結合してBという文字列を得る。最後にAとBを結合してSを得るSに回文となる部分文字列が何個含まれているかを返せ。2500考えたことSの文字列長をNとする。S[s]からS[t]は回文かどうか確かめてく。愚直にやると、回文か確かめるのにNかかり、O(N^3)でぷぎゃーするのでDPする。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。