AtCoder Regular Contest 071

参加しました。

C問題　怪文書 / Dubious Document

n個の文字列が与えられるので、各々の文字列に対していくつか文字を取り出して別の文字列を作った時にどの文字列からでも作れる文字列のうち最長のものを求める問題。

出てくる文字をカウントしていって、各々の文字に対して出てくる回数の最小を計算する。あとはaから順に並べて終わり。（1回バグらせた）

D問題　井井井 / ###

xy座標にx軸に平行な直線がm本、y軸に平行な直線がn本あるときに、作られるすべての長方形の面積の和の10^9+7で割ったあまりを求める問題。

x_i-x_j (i>j)の和とy_j-y_k (j>k)の和を取って掛け算すれば多分いいんだろというノリで考える。

そのままだとTLEなので、足される回数と引かれる回数を考えて、O(n+m)で計算しました。おわり。

E問題 TrBBnsformBBtion

今気づいたけどTransformationってことか。

A,Bからなる文字列に対して、A→BB、B→AAもしくはAAAかBBBであるような一部を消去（場所は選べる）という操作を考える。

文字列S,Tに対してSのa_i~b_i文字目をTのc_i~d_i文字目に変化させられるかを判定する問題。

なんかいっぱいクエリがあるしどうすんだ〜〜〜と思いましたが、逆にいっぱいクエリがあるってことは前処理で位置に対して値が対応付けられるのでは？という気持ちになる。

とりあえず全部のBをAAに変えることを考える。→なんかAの数で分類分けできるっぽいぞ？？？

サンプル見てもそうっぽいにおいしかしないので、S,Tに対してi文字目までの部分列についてBをすべてAAに変えた時のAの個数をx[i],y[i]として予め計算。

kつめのクエリに対して、x[b_k]-x[a_k-1]とy[d_k]-y[c_k-1]のmod.3が一致しているかどうかで判定した。

なんかうまくいった。やったね！

F問題　Infinite Sequence

問題分がまずややこしい。

{1,...,n}からなる無限長の列っていう文字で若干ウッとくるものがあるよね。

第n項以降は同じ数。第i項の直後のa_i個の項はすべて同じ数。

となるような{1,...,n}からなる{a_n}の総数を10^9+7で割ったあまりを求める問題。

とりあえずn=2の時とかを考える。→なんかいまいちよくわかんない。

そのままnで考えてみる。なんか色々分かる。

①1でない数pのあとに1でない数qが来ると、その後は再帰的に全部qになる。

②p 1 1 1 .... 1 1(1がn個) って感じだとその後はまた新たに考えればよい。

なので、n文字目まで残りk文字残っているような時の数列の総数をx_kとすると以下のような漸化式が成り立つ。

x_k = (n-1)^2 + x_(k-1)+x_(k-3)+...+x_0+n+1-k

これをkとk-1の時で連立させると、

x_k - x_(k-1)  = x_(k-1) - x_(k-2) + x_(k-3) -1

3項間漸化式の出来上がり。

あとは適当に計算して終わり。一応確かめたらきっちりあってそうだったので、提出したらACでした。

算数ゲーすぎて全完できてしまった・・・　なんか後にも先にもこの順位も全完ももうなさそうですね。

35位 パフォーマンス2742 レート 1981(+141)

黄色まであと19。ギリギリいかない奴だ。