問題 Editorial 問題 '0'〜'9'からなる文字列digitsが与えられる。 この文字列をいくつかに分割し、それぞれを整数として読む(leading zeroは許可され、単に無視される)。ただし、列はstrictly increasingでなければならない。 このような列の中で、最後の整…

問題 Editorial 問題 単語列wordsが与えられる。それらを全て含む、長さ最小の文字列の辞書順最小を求めよ 1 1 解答 まず、他の文字列に含まれている関係にある文字列たちを除去する。 この除去された文字列は他の文字列に含まれるので、考えなくても問題の…

問題 Editorial 問題 ある文字列のサブシークエンスとは、その文字列から任意の個数の文字を消したものである(連続している必要はない)。 3つの文字列a,b,cが与えられる。この3つの文字列に共通する空でないサブシークエンスの数(同じ文字列は重複して数えな…

問題 Editorial 問題 辞書dictが与えられる。 この辞書dictに含まれる単語を使ってしりとりをする。 ただし、同じ単語を複数使っても良い。 しりとりをして文字列を作ることが出来る。例えば"abc"と"cd"と"efgh"でしりとりすると"abcdefgh"という文字列にな…

問題 Editorial 問題 2人でゲームをする。 シークエンスの集合sequencesが与えられる。 最初のプレイヤーはsequencesから1つ選ぶ。 相手のプレイヤーは最初のプレイヤーが選んだものとは違うシークエンスをsequencesから1つ選ぶ。 その後ランダムなコインを…

問題 Editorial 問題 無限のグリッドにそれぞれ小文字アルファベットが書かれている。 (i,j)に書かれている文字は(g[i mod R][j mod C] where gはR*Cのサイズ)である。 (0,0)から(x,y) (x,yは非負整数)を通る半直線上の(厳密にその座標を通った)文字を繋げる…

問題 Editorial 問題 文字列の集合dictionaryが与えられる。 長さnの文字列のうち、dictionaryに含まれる単語を部分文字列として含むものの数をmod 10000で求めよ 1 1 1 解答 行列累乗。 単語へのマッチング状態を状態として持って、次の文字で行く所に+1す…

問題 Editorial 問題 xとyからなる文字列に対して、いつでも 含まれる"yyyyyy"を削除する 含まれる"xxxxxxxx"を削除する 含まれる"xy"を"yyyyyx"に置換する という操作ができる。 文字列Aに操作を0回以上繰り返してBにできることを(A ⇒* B)と書くとき、関係~…