文字列問題
慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…
Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった！ 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…
フラグの考え方で解くのが一番分かりやすいと思った 問題へのリンク 問題概要 英小文字と、文字 , と " からなる長さ の文字列 が与えられます。 に含まれる文字 " の個数は偶数であることが保証されています。 に含まれる " の個数を 個とすると、各 につい…
文字列の連続した部分文字列を数え上げるのは Suffix Array の典型問題。それを少し応用した面白い問題！ 問題へのリンク 問題概要 英小文字からなる 2 つの文字列 が与えられる。次の条件を満たす文字列の個数を求めよ。 中に連続した部分文字列として含ま…
Suffix Array の典型問題 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列として登場しうる文字列をすべて考える。重複は除外する。これらの文字列の長さの総和を求めよ。 制約 考えたこと 次の問題とほと…
めっちゃ面白い問題だった！ Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…
すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…
Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…
とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…
Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題！ 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…
この問題、深く考えずに for 文回した人も多いと思う。実際それでも問題なく解ける！ 問題へのリンク 問題概要 英小文字のみからなる 2 つの文字列 が与えられる。 は に英小文字を 1 つ挿入して作られたことがわかっている。 挿入された文字は の先頭から何…
ひたすらに迷走してしまった。今回の記事は解説というより、個人的備忘録として書く。 問題へのリンク 問題概要 一般に、'A' と 'B' と 'C' の 3 種類の文字からなる文字列 のスコアを次のように定める 文字列 に対して、以下の操作を繰り返し実施していく。…
ビット全探索もついに茶色 diff ですね！ 問題へのリンク 予備知識 ビット全探索の知識があると解きやすいです！ drken1215.hatenablog.com 問題概要 英小文字のみからなる 個の文字列 が与えられます。 これらの文字列の中から、いくつかの文字列を選びます…
包除原理を学べる問題！ 問題へのリンク 問題概要 個の文字列 が与えられます。次の手順によって作れる長さ の文字列の個数を 998244353 で割ったあまりを求めてください。 のいずれかを選ぶ 文字列 に含まれる文字のみを使って、長さ の文字列を作る 制約 …
これまたすごく典型的な DP！！！ 「状態遷移」を意識して取り扱う DP。ごく一部の界隈では耳 DP と呼ばれていたりもするかもしれない。 問題へのリンク editorial この問題の前提知識 ナップサック問題を解く DP が自力で書けること 1000000007 で割ったあ…
辞書順最小なものを求めるとき、しばしば貪欲法が有効ですね！ 問題へのリンク editorial 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の長さ の部分文字列であって、辞書順最小のものを求めてください。 制約 辞書順最小 → 貪欲法！ 「辞…
これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…
いわゆる部分列を扱う DP ですね。経路復元も含んでいて少し難しい問題です。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の部分列 (連続でなくてもよい) として考えられる文字列をすべて考えたとき、その中で辞書順で 番…
文字列の処理を練習する問題ですね 問題へのリンク 問題概要 文字の文字列 が与えられます。 は英文字のみからなります。 の 文字目以降について、 大文字ならば小文字に 小文字ならば大文字に なるように変換してくだだい。 制約 考えたこと この問題では、…
ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題！ 問題へのリンク 問題概要 英子文字からなる長さ の文字列 が与えられます。 をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれ…
いわゆる、 まで調べれば十分というタイプの問題だね。最近そのタイプの問題が流行っている気がする！ 問題へのリンク 問題概要 十進法表記で偶数桁で、かつ、その前半と後半とが文字列として等しいようなものを「良い整数」と呼ぶことにします。 以上 以下…
すごく面白かった！ 問題へのリンク editorial スコア: 191.85 / 500.00 問題概要 "I" と "O" のみからなる文字列 が IOI 文字列であるとは、ある正の整数 が存在して = "I" = "O" = "I" が成立することと定義する (1-indexed)。 いま、"I", "O", "?" のみか…
KMP 法で殴ったけど、愚直にやっても調和級数的計算量で間に合うね。 問題へのリンク 問題概要 円周上に等間隔に 個の点が打たれている。これらの点を端点とした 個の線分がある (下図のような感じ)。 これが回転対象性をもつかどうかを判定せよ (1 周未満の…
とにかく実装力を鍛えよう〜〜 問題へのリンク 問題概要 個の文字列が与えられる。そのうちのいくつかは先頭の文字が ! である (それ以外はすべて英小文字)。 red gray !orange yellow !blue cyan !green brown !gray ! の付いていない文字列と、付いている…
本番 14 分かけたのは反省。 問題へのリンク 問題概要 "110" という文字列を 10000000000 個連結してできる文字列を とする。 長さ の文字列 が与えられる。 の中に が連続する部分文字列としていくつ含まれるかを求めよ。 制約 考えたこと こういう、端の処…
桁DPとは違うけど、桁DP的な発想で解けた ジャッジページへのリンク 問題概要 長さ の文字列 が与えられる。 の各文字を並び替えてできる文字列をすべて考えたとき、 はその中で辞書順で何番目の文字列に相当するのかを求めよ。 制約 の文字はすべて英大文字…
結構悩んだ！！！ 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、 とする。 の考えられる最大値を求めよ。 制約 考えたこと 単純にそれぞれの部分文字列を探索し…
ちょっと実装大変だった。差分のみ更新していく系の問題。 問題へのリンク editorial 問題概要 のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。 またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。 今、与…
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …
Zero-Sum Ranges の応用問題だけど、最初難しく考えてしまって「解けない...」となってました ジャッジページへのリンク 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。…
