巨大数研究 Wiki
Advertisement
巨大数研究 Wiki

\(\newcommand{\nat}{\mathbb{N}} \newcommand{\len}{ {\rm len}} \newcommand{\parent}{ {\rm parent}} \newcommand{\cln}{ {\rm Cln}} \newcommand{\yume}{ {\rm yume}} \newcommand{\if}{ ~{\rm if}~} \newcommand{\else}{ ~{\rm else}~} \)Naruyokoさんの寝起き120分チャレンジ!いぇいいぇい数aAAAAAAAAAAAAAAASFCdgh\r\nなんかごめんなさい。をここで読みやすいように引用・解析していく。

同じものを書いても仕方ないので、できるだけ読みやすいように「意訳」したものにしてみる。

準備

途中までは、通常よく使われる概念を、独自の記法で定義したものとなっており、トライバルが感じられる。

  1. 集合 \(G\) は非負整数の集合なので、\(\nat\) と表してみる。
  2. 集合 \(S\) は有限非負整数列の集合っぽいので \(\nat^{\lt \omega}\) と表すことにし、\(S\) はその要素を表すことにする。
  3. \('[a,b,c]\) は普通の配列。\((a,b,c)\) と表してみる。
  4. 関数 \(i(s)\) は配列の長さを返す関数なので、\(N_S\) と表してみる。
  5. 関数 \(p(s,n)\) は配列 \(s\) の \(n\) 番目要素を表すので、\(S_n\) と表してみる。
  6. \(p(s,i(s)-1)\) は繰り返すよく出てくる数列末尾なので、\(C(S)\) と表してみる。
  7. 中値記法 \(aYb\) は数列連結の演算子なので、\(a\frown b\) と表してみる。
  8. 関数 \(e(s,m,n)\) は数列 \(S\) の \(m\) つ目から \(n\) つ目を抜き出す部分数列関数なので、\(s_{[m,n)}\) と表してみる。
  9. 中値記法 \(u\) は長さ比較演算子だが、\(e\) の中でしか使われないので \(e\) の動作を把握したら忘れることが可能。
  10. \({\rm Saachi}(s,n)\) は値が \(n\) より小さいものを右から探してそのインデックスを返す関数なので、\(\parent_S(n)\) と表してみる。
  11. \({\rm Saachi}(s,p(s,i(s)-1))\) は繰り返し出てくる表現だが、右端の子の親、つまり bad part 的なもののようなので、\(r_S\) と書くことにする。
  12. \(\ln(s,n)\) は数列\(s\)の全ての要素に\(n\)を加算する関数なので、\(S+n\) と表してみる。
  13. \(\cln(s,m,n)\) をちょっと \(\cln(B,m,n)\) と書いてみよう。

\begin{eqnarray} \cln(B,m,0)&=&B\\ \cln(B,m,n)&=&B\frown(\cln(B,m,n-1)+m)\\ &=&B\frown(B\frown(\cln(B,m,n-2)+m)+m)\\ &=&B\frown(B\frown(B\frown(\cln(B,m,n-3)+m)+m)+m)\\ &=&B\frown(B+1m)\frown(B+2m)\frown \cdots \frown(B+nm) \end{eqnarray} \(\cln\) は \(m\) ずつ上昇する bad part \(B\) のコピー作業っぽいですね。

  1. \({\rm Yumewomiru}\) は割と本体。\(\yume(S)[n]\) と書いて解析してみよう。

\begin{eqnarray} \yume(S)[n]&=&'[0]\frown S \if =S_0 \gt 0 \else\\ \yume(S)[n]&=&'[0]\frown S_{[0,N_S-1)} \if C(S)\gt 0\else\\ \yume(S)[n]&=&S_{[0,N_S-2)}\frown (n,2n) \if i(s)\gt 2 \land C(S)=1\else\\ \yume(S)[n]&=&S_{[0,r_S)}\frown \cln(S_{[r_S,N_S-1)},C(S)-1,n) \if r_S=0 \else\\ \yume(S)[n]&=&S_{[0,r_S)} \if r_S=0 \else\\ \end{eqnarray} これをもうちょっと分かりやすく翻訳すると \begin{eqnarray} \yume((s_0,s_1,\cdots,C(S)))[n]&=&(0,s_0,s_1,s_2,\cdots,C(S))\if a\neq0 \end{eqnarray} 初めが 0 でないなら0を付けるみたい。 \begin{eqnarray} \yume((s_0,s_1,\cdots,s_{N_S-1},0))[n]&=&(0,s_1,\cdots,s_{N_S-1}) \end{eqnarray} 末尾の 0 の単純カットか。 \begin{eqnarray} \yume((a,b,c\cdots,x,y,{\color{red}{z}},{\color{red}{1}}))[n]&=&(0,a,b,c,\cdots,x,y,{\color{red}{n}},{\color{red}{2n}}) \end{eqnarray} 末尾が1だとその1とその左を\(n,2n\)に置換してる。

\(S_{[0,r_S)}\) はgood part, \(S_{[r_S,N_S-1)}\) はbad partだが、原子数列とは違って、bad part に\(N_S-1\) は入らないようだ。\(S_{[0,r_S)}=G(S)\)、\(S_{[r_S,N_S-1)}=B(S)\) と書いてみよう。 \begin{eqnarray} \yume(G\frown B)[n]&=&G(S)\underbrace{\frown B(S)\frown B(S)\cdots\frown B(S)}_{C(S)-1{\rm times}} \if S_{r_S}=0 \end{eqnarray} bad root が0 のときは \(C(S)-1\) ずつ上昇させながらコピー?

ここからは長文なのでまずテキスト解析から入る。

e(s,0,Saachi(e(s,0,Saachi(s,p(s,p(s,i(s)-1))),p(s,Saachi(s,p(s,i(s)-1)))))Y
Cln(e(s,Saachi(e(s,0,Saachi(s,p(s,i(s)-1))),p(s,Saachi(s,p(s,i(s)-1)))),i(s)-1),
p(s,i(s)-1)-p(s,Saachi(e(s,0,Saachi(s,p(s,i(s)-1))),p(s,Saachi(s,p(s,i(s)-1)))))-1,n)

bad root Saachi(s,p(s,i(s)-1)) を r に置換する。

e(s,0,Saachi(e(s,0,r),p(s,r)))Y
Cln(e(s,Saachi(e(s,0,r),p(s,r)),i(s)-1),p(s,i(s)-1)
-p(s,Saachi(e(s,0,r),p(s,r)))-1,n)

good part e(s,0,r) を G に置換。

e(s,0,Saachi(G,p(s,r)))Y
Cln(e(s,Saachi(G,p(s,r)),i(s)-1),p(s,i(s)-1)
-p(s,Saachi(G,p(s,r)))-1,n)

Saachi(G,p(s,r)) がえらい出てくるな。bad root のさらに親だ。ground bad root として R と書いてやろう。

e(s,0,R) Y  Cln(e(s,R,i(s)-1), p(s,i(s)-1)-p(s,R)-1,n)

ここまできたのでやっと数式化する。grand good part \(S_{[0,R)}=G'(S)\)、grand bad part \(S_{[R+1,S_{N_S-1})}=B'(S)\) も使っていこう。 \begin{eqnarray} \yume(G'(S)B'(S)C(S))&=& G'(S) \frown \cln(B'(S), (S_{N_S-1}-S_R)-1, n)\\ \Delta(S)&=&(S_{N_S-1}-S_R)-1 \end{eqnarray} \begin{eqnarray} \yume(G'(S)B'(S)C(S)) = G'(S) &\frown& B'(S) \\ &\frown& B'(S)+1\Delta(S) \\ &\frown& B'(S)+2\Delta(S) \cdots \\ & \frown& B'(S)+n\Delta(S) \end{eqnarray}

残りは集計パートだ。

  1. Myaa(s,n) は s を展開して n をインクリメントする。
  2. Suya((s,n)) は s を空列になるまで展開して、それにかかった展開回数を返す。
  3. Nemasuka(n) = \((\underbrace{0,0,\cdots,0}_{n {\rm times}}, 1)\)
  4. Night(0) = 86400
  5. Night(1) = Suya(\((\underbrace{0,0,\cdots,0}_{86400 {\rm times}}, 1),86400))\)
  6. Night(2) = ...

Good Luck。

Advertisement