連続部分列を扱う問題
2 つの文字列の最長の共通部分文字列 (部分列ではなく) を求める問題! これ、蟻本の例題にもあるけど、POJ ではなく Yosupo Judge で解けるようになったのは大きい! なお、Suffix Automation があれば本当に貼るだけみたい。 問題へのリンク 問題概要 2 つ…
ランレングス圧縮の典型題! なお、ランレングス圧縮は鹿本でみっちり解説している。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。 制約 考え…
文字列の練習! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列 中に、文字 'a' と 'b' が隣接する箇所があるかどうかを判定せよ。 考えたこと for 文を用いて判定していく。添字 i を回していき、 S[i] == 'a' and S[i+…
最長回文を求める問題! 問題へのリンク 問題概要 文字列 が与えられる。 の連続する部分文字列のうち、回文であるものについて、最長の長さを求めよ。 考えたこと この問題は次の 2 ステップに分かれている。 の連続する部分文字列を全種類抜き取る それら…
Suffix Array 上をひたすら頑張って探索する感じ 問題へのリンク 問題概要 個の文字列 が与えられる (これらの文字列はすべて英小文字のみからなる)。 以下の条件を満たす文字列 の個数を求めよ。 英小文字のみからなる のうち、ちょうど 1 個の部分文字列で…
「連続文字列」を処理する典型問題。 問題へのリンク 問題概要 文字 A, B, C のみからなる長さ の文字列 が与えられる。 文字列 に含まれる連続部分文字列 "ABC" のうち、それが始まる最小の添字を答えよ。"ABC" を含まない場合は -1 を出力せよ。 解法 (1)…
ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…
Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった! 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…
文字列の連続した部分文字列を数え上げるのは Suffix Array の典型問題。それを少し応用した面白い問題! 問題へのリンク 問題概要 英小文字からなる 2 つの文字列 が与えられる。次の条件を満たす文字列の個数を求めよ。 中に連続した部分文字列として含ま…
Suffix Array の典型問題 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列として登場しうる文字列をすべて考える。重複は除外する。これらの文字列の長さの総和を求めよ。 制約 考えたこと 次の問題とほと…
Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…
Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題! 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…
ひたすらに迷走してしまった。今回の記事は解説というより、個人的備忘録として書く。 問題へのリンク 問題概要 一般に、'A' と 'B' と 'C' の 3 種類の文字からなる文字列 のスコアを次のように定める 文字列 に対して、以下の操作を繰り返し実施していく。…
累積和を使う代表的な問題ですね。 ジャッジへのリンク 問題文へのリンク 問題概要 個の整数からなる数列 と、整数 が与えられる。 数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。 制約 前提知識 まず、愚直な解法で…
平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…
結構悩んだ!!! 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、 とする。 の考えられる最大値を求めよ。 制約 考えたこと 単純にそれぞれの部分文字列を探索し…
Zero-Sum Ranges の応用問題だけど、最初難しく考えてしまって「解けない...」となってました ジャッジページへのリンク 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。…
面白かった!! 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは,以下の 2 種類の操作を好きな順序で好きな回数行うことができます. の連続する 文字を選んで,それらをすべて 0 にす…
面白かった 問題へのリンク 問題概要 文字列 がアンバランスであるとは、 の中の文字のうち、過半数が同じ文字 であることを指すものとする。長さ の文字列 が与えられたとき、 の連続する部分文字列であって、アンバランスなものがあるかどうかを判定せよ。…
5 + 7 + 5 = 17 なの、よくできてる! 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…
めちゃくちゃ面白かったし勉強になった! 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…
Zero-Sum Ranges だった!!! 問題へのリンク 問題概要 'A', 'G', 'C', 'T' からなる文字列 が相補的であるとは、 を並び替えてできる文字列 が存在して、 T[ i ] = 'A' ならば T'[ i ] = 'T' T[ i ] = 'T' ならば T'[ i ] = 'A' T[ i ] = 'G' ならば T'[ i…
まさかの既出!!!しかも割と最近の ABC-E!!! drken1215.hatenablog.com 問題へのリンク 問題概要 から までの数字のみからなる文字列 が与えられる。 の連続する区間であって、 の倍数であるものが何個あるのかを求めよ。 制約 考えたこと 実は完全にマ…
じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…
こういう問題を求めてた!! 問題へのリンク 類題として、こんなのがある。 drken1215.hatenablog.com 問題概要 長さ の、各文字が '0'〜'9' のいずれかとなっている文字列 と、素数 が与えられる。 の空でない連続する区間であって、その整数が で割り切れ…
期待値の線形性!!! 問題へのリンク 問題概要 個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。 隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。…
文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける!!! Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editorial のラスト 3 行で言及された…
超典型的なしゃくとり法そのものだった!!! 問題へのリンク 問題概要 個の整数 があたえられる。 数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com こ…
部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…
こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…