srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

文字列

yukicoder No.267 トランプソート

問題 問題概要 文字列をソートする。 解法 単純に文字列を比較することはできない。ただし、1文字目は4種類、2文字目は13種類しかないので、その文字を通常のsortで比較できるように文字列をAから順に利用して置換することで、通常通りsortが行えるようにな…

yukicoder No.18 うーさー暗号

問題 問題概要 i文字目はi文字前へずらしら文字に置換した文字列を求める問題。 解法 Aからのindexを求めて、i番目ならi文字前へずらせば良い。ただし、そのまま d -= i + 1 としてしまうと、マイナスになる場合もあるので、先に2600(=0(mod26))ぐらいの数字…

yukicoder No.457 (^^*)

問題 問題概要 省略 解法 「同じ文字は何度でも使用可能ですが、一つの'('')'の組み合わせから錬成出来るのは左向き、右向きそれぞれ1つです。」といのがポイント? "(^^)"が、何個あるから求める。'(' を決めて、そこから "^^" の順で "^^" が何回分でたかを…

yukicoder No.432 占い(Easy)

問題 問題概要 隣りあったの数字をたす。足した値が2桁になるときは10の位と1の位の数字をたす。1桁ならそのまま。この操作を続けていき、さいご1桁になった時、どのような数字になるかを求める。 解法 与えられう数字Sの桁は大きいので文字列として受け取る…

SRM 689 div2 easy SimilarUserDetection

問題 問題概要 文字列がいくつか与えられる。その文字列のなかに同じものが2つ以上あるかを判別する。ただし、0(ゼロ)とO(オー)は同じもの、1(いち)とl(Lの小文字)とI(iの大文字)は同じものとして考える。 解法 方針としては、文字列を変換して、重複を確認…

SRM 690 div2 easy DoubleString

問題 問題概要 文字列Sが与えられる。その文字列がS = T + T となる文字列Tが存在するか。 解法 Tが2回続くので、TはSの文字列の長さの1/2なので、Sを前後で二等分した文字列どおしが同じものであるかを見ればよい。 ミス なし。 コード #include <iostream> #include <string></string></iostream>…

yukicoder No.430 文字列検索

問題 問題概要 文字列sの中に文字列cがいくつ含まれているかを求める問題。 解法 ローリングハッシュを使いました。ほぼ理解していないので、応用はきかないので要練習。文字列を比較するとき、1文字ずつ見比べいると、文字列の長さがmだとそこで、O(m)なっ…

codeforces 374 div2 A. One-dimensional Japanese Crossword

問題 問題概要 連続する黒のマスの数。 解法 Bが始まった位置をl、Bが終わった位置をrを記録しながら、やる。 ミス サンプルから推測 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #def</cmath></cstdio></queue></vector></algorithm></iostream>…

SRM 696 div2 easy Ropestring

問題 問題概要 -と.を含んだ文字列sが与えられる。この文字列を並び替える。-の連続した部分をひもとして考える。ひもの長さが偶数で大きいものから左へ、つぎ、奇数のもので、大きいものをつなげていく。ひもとひもの間には.をつけなければならない。.が余…

SRM 698 div2 easy Initials

問題 問題概要 スペース入りのアルファベットンの文が与えられるので、単語ごとの頭文字をとり、それをつなげたものを表示する問題。 解法 まず、name[0]は必ず、頭文字になる。そのあとは、スペースのあとの文字が必ず頭文字になるので、スペースのあとの文…

aoj 0572 - Card Game is Fun

問題 問題概要 文字列bの連続した文字列が文字列aの部分文字列(連続していなくてもよい文字列)で作れる時の、最長の長さを調べる。 解法 連続文字列の先頭の文字を決め(b[i])、その文字が文字列aを先頭から見ていき、存在するかを調べ、文字存在するなら(a[k…

aoj 0538 - IOIOI

問題 問題概要 該当する文字列がいくつ存在するか求める問題。 解法 与えれた文字列(s)にIOIOI等の文字列があるかを調べる。sの先頭から調べていき、Iの文字であれば、その位置から、2*n + 1文字を切り取り、該当する文字(ans)と一致するからを調べている。…

ABC 043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit)

問題 問題概要 省略 解法 条件通りにの文字列を作る。 0の時は、文字列の末尾に0を付け加え、1の時は文字列の末尾に1を付け加え、Bの時は、文字列の末尾を取ればよい。 ミス ClangだとACだけど、GCCだとREでよく分からない。 [追記] @mmxsrup 空の文字列に対…

yukicoder No.39 桁の数字を入れ替え

問題 問題概要 数字の一か所を入れ替えて、最も大きい数字を求める。 解法 数字を文字として扱う。文字列の一か所を入れ替えたものを全探索している。出来上がった文字列をstring型のvector配列にいれて、ソートする。数字だけじゃなくて、文字列もソートで…

yukicoder No.52 よくある文字列の問題

問題 問題概要 文字列の中で最も左のもの、またはもっとも右の文字を任意の順番で取り出していき、取り出した順番で並べる。何種類の文字列が作れるか。 解法 全探索する。左または右から取る順番をbitを用いて実装した。今回はbit列iのpos番目のbitが立って…