文字列
問題 英小文字からなる文字列が与えられる。 文字列の必ずしも連続しない部分文字列のうち、回文であるものは何種類あるか。 同じ回文は一つと数える。 制約 文字列の長さ2000以下。
問題 長さnの文字列がありその一部の情報が以下のどれかの形式で与えられる。 x文字目がcである l文字目からr文字目がh文字目からと等しい このときq個のクエリ、x文字目が何の文字であるか、あるいは与えられた情報からではわからないかを答えよ。 制約条件…
問題 aまたはbからなる文字列が与えられる。 このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。 文字列が同じときは一つと数える。 制約条件 文字列は乱数により生成される。 n≦10^5
問題 n項からなる数列a[i]が与えられる。これに対してq個のクエリに答えよ。 クエリ: 区間l, rが指定される。 [l, r]と長さが等しく、[l, r]に交わらない区間[s, t]で、a[l + i] = a[s + i] = constとなる区間はいくつあるか求めよ。 制約条件 n, q≦10^5 a[…
問題 日本語なので本文参照(http://kupc2014.contest.atcoder.jp/tasks/kupc2014_k) 文字列s1, s2, ... snの中のうち、文字列tを連続する部分文字列として含むものの個数をkとする。k * |t|の最大値を求めよ。 制約条件 n≦10^5 Σ|si|≦10^5
問題 文字列sが与えられる。次のようなクエリq個に答えよ。sの連続する部分文字列で、文字列x, yをともに連続する部分文字列として含むような文字列のうち、長さが最小のものの長さを出力せよ。 そのような文字列が存在しない場合-1を出力せよ。 x, yはオー…
問題 長さnの文字列tが与えられる。 長さnの文字列で、tとの編集距離がちょうどiであるような文字列を 1≦i≦nなるiについて出力せよ。 制約条件 n≦25 tおよび出力する文字は英小文字からなる
問題 長さnの数字のみからなる文字列が与えられる。 この数字の連続する部分文字列(ただしleading zeroがあってはならない)で、 回文かつ3の倍数であるものの個数を求めよ。 制約条件 n≦1000000
問題 文字列sの回文度とは、sの空でない連続する部分文字列のうち、回文であるものの個数を言う。 英小文字と'?'からなる文字列sが与えられる。 文字列中の'?'は等確率でa-zに変化する。このとき、sの回文度の期待値を求めよ。 制約条件 sの長さ≦5000
問題 文字列sが与えられる。 文字列sのi文字目からj文字目を抜き出したものをs(i, j)とする。 s(i, j)のうち"bear"を連続する部分文字列として含むものはいくつあるか答えよ。 制約条件 sの長さ≦5000
問題 文字列aをb回繰り返すことを(a, b)と書く。 文字列a, cおよびそれらの繰り返し回数b, dが与えられる。 w = [a, b], q = [c, d]としたとき、 [q, p]がwの(必ずしも連続しない)部分文字列となるような最大の整数pを求めよ。 そのような正の整数pが存在…
問題 辺に文字列のついた根付き木が与えられる。 この木から文字列を以下のようにして作ることができる。 始点の(枝,枝の文字の何番目か)、終点の(枝,枝の文字の何番目か)を選ぶ。 必ず始点のほうが根に近いほうを選ぶものとする。 始点枝から終点の枝…
問題 二つの文字列s, tが与えられる。 任意のiに対して、sのi番目の文字を含んだ、必ずしも連続しないsの部分文字列であって、 tに一致するものが存在するか。存在するならYesを、そうでないならNoを出力せよ。 制約条件 s, tの長さ≦2 * 10^5 s, tは英小文字…
問題 '(', ')', '[', ']'からなる文字列が与えられる。 この文字列の連続する部分文字列のうち、 括弧の対応が正しいもので、'['の含まれる個数が最大であるものをどれか一つ出力せよ。 制約条件 文字列の長さ≦10^5
問題 文字列の集合Sが与えられる。 先手はこのうちひとつの文字列を選ぶ。これをxとする。 また、先手はアルファベットに好きな順に優先順位をつける。 後手は、Sのうちx以外の文字列を好きに並べ替える。 並べ替えたあと、xがSのなかで、他のどの文字列より…
問題 長さnの文字列sと整数i, jに対して、次の関数を定義する。 f(s, i, j) = s[i+1...j-1] + r(s[j...n]) + r(s[0...i]) ただし、+は文字列の結合を、r(s)は文字列の反転を表すものとする。 二つの文字列a, bが与えられる。 f(a, i, j) = bを満たすi, jのう…
問題 英小文字からなる文字列sが与えられる。 この文字列に対して、以下のようなクエリをm個実行する。 入力l, rを受け取る。 sのl文字目からr文字目を、その部分が回文になるように並び替える。 回文が複数個できる場合は、辞書順で最小になるように並び替…
問題 A以上B以下の数で、 二進数で書いたとき、Pを二進数で書いた文字列を連続する部分文字列として含むような数のうち、最小のものを求めよ。 存在しない場合はNONEを出力せよ。 制約条件 1≦A, B, P≦10^15
問題 n個の文字列が与えられる。 それぞれの文字列は、文字列の中で文字の順序を自由に入れ替えてよい。 入れ替えた後で、trie木を作る。 文字の順序を最適に入れ替えたとき、trie木の頂点の数は最小でいくつか、求めよ。 制約条件 n≦16 各文字列の長さ≦50
問題 次のような携帯の文字列入力がある。2-9のボタンに次の文字が対応している。 2 a,b,c 3 d,e,f 4 g,h,i 5 j,k,l 6 m,n,o 7 p,q,r,s 8 t,u,v 9 w,x,y,z 携帯は次の三つの内部状態を持つ。 D: 今まで入力した数字 U: 未確定の文字列 F: 確定の文字列 辞書…
問題 文字列A, B, Cが与えられたとき、 文字列xに対する操作fを、f(x) = A + x + B + x + Cとする。 (+は文字列の結合を表す) fをn回適用する操作(f(f...(f(f(x)))...))をf^nと書く。 f^k(x)に、文字列Fが何回出現するかを求めよ。 制約条件 A, B, C, Fの…
問題 n個の文字列b1, ..., bnが与えられる。 m個のインデックスi1, ..., imが与えられる。 文字列tを、bi1 + bi2 + ... + bimとする。(ただし+は文字列の結合をあらわす) 別の文字列sが与えられる。 このとき、sとtの最長共通部分列(連続しなくともよい)…
問題 A,C,G,Tからなる文字列n個が与えられる。 n個全てに出現する文字列のうち、最も長さの長い文字列の長さを求めよ。 制約条件 n≦6 それぞれの文字列の長さは100万以下
問題 英小文字からなる文字列sが与えられる。sの連続する部分文字列uを任意に一つ選ぶ。 uに対して、 先頭または末尾に一字を加える。 先頭または末尾の一字を消す。 任意の一文字を、別の文字に変える。 の操作を行うことができる。 最小で何回の操作を行え…
問題 英小文字からなる文字列sが与えられる。 sの任意の連続する二文字に対して、1文字目をアルファベット順で一つ進めて、2文字目を一つ戻す、 または1文字目を一つ戻して、2文字目を一つ進める、 という操作が何度でも行える。 ただし、aの前の文字は存在…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1090) 制約条件 n≦100 1≦col[i]≦4 m≦2000 1≦ai,bi≦n -1000≦ci≦1000 1≦k≦10 patternは1〜4からなる長さ10以下の文字列
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2020) 制約条件 入力の一行は100文字以下
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2367) 2(3(b)4(ab)x) のように圧縮された文字列sが与えられる。 tの空でない全ての連続する部分文字列のうち、展開後のsに含まれるものはいくつあるか を求める問題…
問題 アルファベットがm種類ある言語の上で、 n文字からなり、その連続する部分文字列の長さがkのものはどれも回文になっているような文字列はいくつあるか、mod 10^9+7で求めよ。 制約条件 n,m,k≦2000
問題 与えられた数字を $をつけて、3桁ごとにカンマで区切り、小数点2桁未満を切り捨てて表示せよ。 数字が負の場合は、さらにその文字列を()でかこって表示せよ。 制約条件 与えられる数字の桁数≦50