文字列問題
カッコ列系の問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…
単純な探索でも解けるし、考察で計算量を減らすこともできそう。 問題へのリンク 問題概要 文字列 が与えられる。文字列 に以下の操作を最小回数行うことで、辞書順で > "atcoder" となるようにせよ。 中の連続する 2 文字を swap する (このテストケースが …
現在の AtCoder ではあまり出なさそうな問題。こういうのは Python 楽だね。 問題へのリンク 問題概要 (西暦) ÷ (月) ÷ (日) が整数となるような日付を「割り切れる日付」と呼ぶ。 日付が "2020/11/14" のようなフォーマットで与えられる。その日付以降の最…
区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…
意外とすぐにわからなかったんやけど... 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。以下の条件をみたす最大の正整数 を求めよ。 を空でない 個の文字列へと分割したとき、連続する文字列は相異なる 制約 Greedy は嘘 パッと思い浮かぶ …
この回の前の回の LCMs といい、約数系包除がこの時期流行ってたのかな。 問題へのリンク 問題概要 整数 が与えられる。 以上 以下のすべての整数 に対し、 に以下の操作を繰り返すことによって次に に戻るまでの操作回数 (戻らない場合 0) を足し合わせた値…
BNF が書かれているので、LL(1)文法を再帰降下とかするのが標準みたいだけど、ad-hoc にスタックでなんとかしてしまった 問題へのリンク 問題概要 以下の BNF によって定義された文字列が与えられる。 <Cipher> ::= <String> | <Cipher><String> <String> ::= <Letter> | '['<Cipher>']' <Letter> ::= '+'<Letter> | '-'<Letter> | 'A' | 'B' |</letter></letter></letter></cipher></letter></string></string></cipher></string></cipher>…
面白かった 問題へのリンク 問題概要 文字列 がアンバランスであるとは、 の中の文字のうち、過半数が同じ文字 であることを指すものとする。長さ の文字列 が与えられたとき、 の連続する部分文字列であって、アンバランスなものがあるかどうかを判定せよ。…
これすごく好き！！！普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…
最初は文字列 を文字列 にできるかを問うつもりだった。てんぷら君のおかげで、 を真っ白にすることで、シンプルな問題になった！ 問題へのリンク 問題概要 マスがあって最初はすべて白く塗られている。ここに "RGB" のスタンプを押していく。スタンプを押す…
めちゃくちゃ面白かったし勉強になった！ 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…
めちゃくちゃ面白かった！ 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…
多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…
この問題のテスターをやってた！ 今流行の NTT 系問題！！しかも分割統治 + FFT というカッコいいやつ！！ 問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さ の文字列 の UMG 数を、以下の条件を満たす添字 の組の個数として定義する。 T[…
Zero-Sum Ranges だった！！！ 問題へのリンク # 問題概要 'A', 'G', 'C', 'T' からなる文字列 が相補的であるとは、 を並び替えてできる文字列 が存在して、 T[ i ] = 'A' ならば T'[ i ] = 'T' T[ i ] = 'T' ならば T'[ i ] = 'A' T[ i ] = 'G' ならば T'[…
これはそんなにコーナーケースとかはなさそう 問題へのリンク 問題概要 個の文字列 が与えられます。各文字列に対して、 英大文字の部分だけを取り出して、この順に連結した文字列 を作り出し、それを 個連結します。そうして得られた文字列の末尾に "UPC" …
これ楽しい！ 問題へのリンク 問題概要 長さ の英小文字のみからなる文字列 が与えられます。 の文字を入れ替えることによって、次の条件を満たす文字列 を作ることができるかどうかを判定してください (可能ならば具体例を 1 つ挙げてください)。 のどの長…
こういう重たい実装を確実にこなせるように...なりたい！ 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…
これ系、この問題以降はたくさん見るようになったけど、この問題が先駆けとなった気がする 問題へのリンク 問題概要 'a', 'b', 'c' のみからなる長さ の文字列 が与えられる。 に以下の操作を好きな順序で好きな回数だけ行って得られる文字列が何通りあるか…
実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という！！！ 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…
ちょっと問題を理解するのが大変かもしれない 問題へのリンク 問題概要 ロボットと 回ジャンケンをする。ロボットの出す手はあらかじめすべてわかっている。 グーを出して勝つと 点 チョキを出して勝つと 点 パーを出して勝つと 点 が得られる。ただし 回目…
落ち着いて頭を整理。。。 問題へのリンク 問題概要 'R', 'G', 'B' のみからなる長さ の文字列 が与えられる。 の index の組 であって、 と と はすべて互いに異なる である という条件を満たすものの個数を求めよ。 制約 考えたこと 頭がごっちゃになりそ…
E8君問題集第3問！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の連続する部分列であって、'A', 'C', 'G', 'T' のみからなる部分の長さの最大値を求めよ。 制約 考えたこと が小さいので、全部調べても間に合う。連続する部分列は 個ある。 それ…
AtCoder 版蟻本に bit 全探索の最初の例題として、この問題を挙げていたので。 問題へのリンク 問題概要 "231" といった 1〜9 の数値で構成された、長さ の文字列 が与えられる。文字列の隙間に '+' を挿入する方法は 通りある。そのそれぞれについての計算…
一瞬コーナーケースがないかと怖くなる 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対し、以下の操作を好きな回数だけ行うことができる。文字列を「単一の文字からなる状態」にするのに必要な操作回数の最小値を求めよ。 文字列の各…
誤読したーーーーーー操作は 1 回しか行えないものと思って悩んでた 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を好きな回数だけ行うことで、 と とが一致する状態にすることが可能かどうかを判定せよ。 1 以上 以下の整数 を定める …
先頭と末尾の両方から push できるデータ構造といえば、deque！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個の操作を行ってできる文字列を出力せよ type 1： 文字列 を左右反転する type 2： 値 F と文字 c が与えられ、F = 1 のと…
一瞬、「更新がある」「種類数」ということで、Wavelet Matrix が必要かとびびった 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個のクエリに答えよ タイプ 1： の 文字目を に変更する タイプ 2： の区間 に含まれる文字の種類数を答える …
まさか残り 25 分で通し切れるとは思わなかった！ 問題へのリンク 問題概要 長さ の '0' と '1' のみからなる文字列 が与えられる。以下の 個のクエリに答えよ 各クエリは left, right, len からなる 部分文字列 A = S[left : left + len], B = S[right: rig…
全探索した！ 整数を string 型にするのに手こずってしまった。 問題へのリンク 問題概要 以下の条件を満たす整数があれば、それを出力し、存在しなければ -1 を出力せよ。 ちょうど 桁である 左から数えて 桁目は である。() 制約 考えたこと 存在しない場…
