Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

文字列

Codechef March Cook-Off 2014 - ABC-Strings

問題文 : ABC-Strings概要 : 文字列 $S$ の部分文字列 $t$ であって, $t$ の中の A の個数, B の個数, C の個数が等しい物の個数を数えよ.制約 : $1 \leqq |S| \leqq 10^6$ $S$ は A, B, C だけからなる文字列である.

AOJ 2369 - CatChecker

問題文 : CatChecker概要 : 文字列$s$ が次のBNF に従っているか判定せよ.<cat> := "" | 'm' + <cat> + 'e' + <cat> + 'w'$1 \leqq |s| \leqq 500$</cat></cat></cat>

Codeforces 356B - Xenia and Hamming

問題 : Xenia and Hamming概要 :文字列$x$ を$n$ 回繰り返した文字列$a$ と, 文字列$y$ を$m $ 回繰り返した文字列$b$ がある. $a$ と$b$ のハミング距離を求めよ. ただし, ハミング距離とは$\displaystyle \sum_{i=1}^{n} [a_i \neq b_i]$ で定義され, $a_i…

Typical DP Contest G - 辞書順

問題文 : 辞書順

IOI 2008-day1 Type Printer

問題文 : 活字印刷機解法 : Trie 木上の探索を行う. 最も長い文字を最後にたどれば, その文字の文の型を回収しなくていいため最短ですべての文字を打ち終えることが出来る. (他の文字はどのみち回収しないといけないため). コード : #include <cstdio> #include <cstdlib> #in</cstdlib></cstdio>…

JOI春合宿 2011-day3 deciphering

問題文 : 解読解法 : dp[i][j], i番目の文字まで, jで終わる暗号の総数, とするとdp[i][i番目の文字] = Σ[j = 'A'...'Z' + ' ', j + i番目の文字は禁止されていない] dp[i - 1][j]となります. 答えは Σ[i = 'A'...'Z'] dp[L][i] です. dp[0][' '] = 1として…

JOI春合宿 2010-day2 DNA synthesizer

問題文 : DNAの合成解法 : dp[M] = M番目の文字までを構成するのに必要なDNA素数の最小値, とすると, M + 1 ~ M + kまでの部分文字列s_kがあるとするとdp[M + i] (1 ≦ i ≦ k) = min(dp[M + i], dp[M] + 1) となる. DNA素を全て確かめるとO(strlen(合成したい…