読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

yukicoder contest-158 解説 (yukicoder No.490 491 492 493)

競技プログラミング

http://yukicoder.me/contests/159

解説です。
















yukicoder No.490 yukiソート

http://yukicoder.me/submissions/156505
書かれているアルゴリズムを素直に実装するだけ。

yukicoder No.491 10^9+1と回文

http://yukicoder.me/submissions/157172
10^9+1の倍数かつ回文である数は、以下の性質を満たす。

  • A + B + A : Aは回文の数,Bは0が連なったもの
  • len(A) + len(B) = 9

2番目の性質より、len(B)=0の時に18桁となって最大。
Bは0が9-len(A)個だけ連なったものなので、Aによって一意に決定。
Aを全探索すればよい。
Aはそのまま全探索すると10^9となってしまうが、回文となるため半分全列挙が使える。よって10^5くらいとなるので間に合う。

yukicoder No.492 IOI数列

https://yukicoder.me/submissions/157179
別々に問題を解く。

関数solA : mod10^9+7
行列累乗で解く。漸化式から行列を作ると以下のようになる

| a[i+1] |   | 100  1 |   | a[i] |
|   1    | = |  0   1 | * |  1   |

この行列を事前に行列累乗で計算しておくことにより、素早く漸化式を解くテクニック

関数solB : mod1010…
modのbaseがlong longに乗らないので、別方針で考える。
規則性がある
1 -> 101 -> … -> 101010101010101010101 -> 0 -> 1 -> …
周期が11回なので、N %= 11としてしまって問題無い。あとはi番目の文字数はi * 2 - 1個なので上手いこと文字列を作って返す。(N == 0の時は"0")

yukicoder No.493 とても長い数列と文字列(Long Long Sequence and a String)

https://yukicoder.me/submissions/157186
漸化式で区間クエリだとよくある問題。
Kは62くらいが上限なので、それ以上の数であっても62くらいにしておく。
区間でよくあるテクで[L,R]を考える時に[0,L]と[0,R]を計算してなんとかするやつがある。
なので、[0,x]の区間について和と積を考える。

事前計算(pre関数)をしておく。
sz[i] = f(i)の要素数
sm[i] = f(i)を文字列化したものの総和
mu[i] = f(i)を文字列化したものの総積
これは漸化式から簡単に求まる。

あとはcalcSumとcalcMulを作るだけだが、和と積は計算部分だけ違うので、calcSumだけ説明する。
calcSum(int k, ll x) := f(k)のx番目までの総和

  • x==0ならreturn 0(0番目までってことは何もない)
  • x <= sz[K - 1]なら、f(k-1) + k^2 + f(k - 1)の前半部分だけの総和なので、return calcSum(k - 1, x)とする
  • x <= sz[k] - sz[k-1]なら、f(k-1) + k^2 + f(k - 1)の前半部分全部とk^2の一部(または全部)なので、return sm[k - 1] + (k^2の該当範囲の和)
  • それ以外なら、f(k-1) + k^2 + f(k - 1)の前半とk^2とを全部 + 後半部分の一部なので、return sm[k-1] + (k^2全部の和) + calcSum(k - 1, x - (sz[k] - sz[k-1]))