WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Statement訳キツネのシエルはn個のアルファベットを持っている。彼女は下記のような性質を全て持つ文字列が好きである。同じ文字が隣り合っていない。xとyを(同じ文字もありうる)ある文字として、xyxyとなるような部分列を持たない。部分列は元の文字列の連続したものでなくともよいことに注意して欲しい。上記1.と2.を満たす文字列の中で、最も長い文字列である。例:シエルは'B'が2つ隣り合っているため、"ABBA"は好きではない。シエルは部分列"TETE"を含んでいるため、"THETOPCODER"は好きではない。シエルは部分列"AAAA"を含んでいるため、"ABACADA"は好きではない。(x=y='A')シエルはより長い"ABCBA"があるため、"ABCA"は好きではない。彼女は"A"という文字列が好きである。彼女は"ABA"と"BAB"という文字列が好きである。整数nが与えられるので、シエルが好きな文字列の数を返せ。5000考えたことまず、問題文より次のことが分かるある文字は3回までしか使えない。"ABCA"という文字列を考える。ここで、'A'に挟まれた'B'と'C'は1回しか使っていないが、末尾に追加しようとしても、部分列に"ABAB"または"ACAC"を含んでしまうためこれ以上追加で使うことはできない。'A'の挟まれた中に追加し、"ABCBA"もしくは"ACBCA"とすることはできる。なにが言いたいかというと、"ABCA"みたいに'A'で挟まれた部分で左右非対称となるのは、最も長い文字列をでなければならないという条件に反するため、シエルの好きな文字列にはなり得ない、といいたいのです・・(説明が上手くできぬ)ある文字で挟まれた部分は、左右対称でなければならないある文字で挟まれた部分は、左右対称となる必要があるため、1文字だけは1回しか使えない。'D'を1回とする必要がある。ここでは'A'を2回使ったので1文字が1回しか使えなくなったが、'A'を3回使うと2文字が1回しか使えなくなる。"ABACA"は'B'と'C'が、"ABCBADA"は'C'と'D'が1回しか使えなくなっている。'A'を2回から3回使うと1回しか使えない文字が1文字増えるため、2回使おうが3回使おうが、文字列の最大の長さは変わらない。1であるこれらの条件を利用すれば、DPで解けるようになる。i文字でシエルの好きな文字列が何個作れるか。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。