2021/05/02

ZONe-Fを考えた(備忘録)

 昨日Atcoderにて行われたZONeコンテストにて、F問題がどうにも理解できず、うんうん考えてやっと理解したので、備忘録です。たぶん、自分で書いておかないと来週には忘れる…。

問題は、$N=2^n$、$\mathcal{N} = \{0,...,N-1\}$ と、$A = \{A_1,...,A_M\} \subset \mathcal{N}\setminus \{0\}$(但し $M < N$)について、$\mathcal{N}$ の数字の全てを $B = \{1,...,N-1\} \setminus A$ の元の XOR で繋いだ木で表せ、というもの。

例えば $N = 8, A = \{2,3,5,6\}$ だとすると、XOR に使っていいのは $\{1,4,7\}$で、

\begin{array}{ccccccc}
7 &\xleftarrow{7} &0 &\xrightarrow{1} &1 &\xrightarrow{4} &5 \\
  & &\downarrow^4 & &\downarrow^7 & &\downarrow^7 \\
3 &\xleftarrow{7} &4 & &6 & &2
\end{array}

と、$\{1,4,7\}$ だけを XOR することで $\{0,...,7\}$ の数字を作ることができ、かつ、それが連結な木になっています。問題は、そもそも $\mathcal{N}$ をすべて繋げるかどうかを判定することと、もし連結ならば実際に木を構成することの二段階で、解説では(1)まず $B$ から $(\mathbb{Z}/2\mathbb{Z})^n$ の基底を構成できれば連結、(2)次にその基底を使ってグラフを作成する、という流れになっていました。

さて、ではまずはそのまま作ってみようとすると、基底はなんとなく作ることができるのだけれど(上のビットから一つずつ残していけばいい)、そこからグラフを作成するのが大変で、どうするのが美しいのかよくわからない。ともかく、めちゃめちゃメモリと計算時間を使えば、(3)基底を作成するときにあらかじめどの$b\in B$を使ってその基底を作ったかをメモしておく、(4)基底の全組み合わせについて、$B$ の元の列=$B$ の元の部分集合を構成し、その順にlinkを張ったグラフを作る。(例えば $2$ が基底だったとすると、 $2 = 1 \oplus 4 \oplus 7$ より $\{1,4,7\}$ が記録されているので、$0 \rightarrow 1$、$1 \rightarrow 5$、$5 \rightarrow 2$ を繋ぐ。または、$3,6$ が基底に取られていたとしたら、$3$ と $6$ との組み合わせでできる $5$ は、$3\oplus 6 = 4 \oplus 7 \oplus 1 \oplus 7 = 1 \oplus 4 = 5$ なので、$0 \rightarrow 1$、$1 \rightarrow 5$ を繋ぐ、など。)しかしこの構成方法だと繋ぎすぎてループができてしまうので($B=\{1,4,7\}$ の例だと基底数と$\# B$が一致していてループができませんが、$n < \# B$ だとパスが$N-1$より多くなってしまう可能性がある気がします)、最後にダイクストラなどをやって、木に戻してあげると、めでたく回答になります。

ただ、この方法だとコードがえらい冗長になってしまう。TLEにこそならないけれど、なんかエレガントでないので、巧い人らはどうしてるのかなと思って拝見したところ、めちゃめちゃ平易に書いてあってびっくりしました。最初はなんでそれでOKなのかわからず、二、三時間ほど格闘してやっと腑に落ちました。以下はその概説備忘録。

まず、$S$ で$0$ を含む連結成分の元を管理する。最初は $0$ を入れておく。

次に、$B$ の元を順に取ってくる。まず一つ目を $b_1$ とすると、$B$ の元は $A$ に入らないからXORで遷移するのに使える。特に、今 $S$ に入っている $0$ に対して、 $0\oplus b_1 = b_1$ なので、$0 \xrightarrow{b_1} b_1$ のlinkを張れば $0$ と $b_1$ が繋がることから、このlinkを張って $S$ に $b_1$ を入れる。

次に $b_2$ を取ってきて、同じことを繰り返すのだが、$S$ には現在 $0$ と $b_1$ が入っているので、まず $0\oplus b_2 = b_2$ に向かって $0 \xrightarrow{b_2} b_2$ を張り、次に $S$ に入っていた $b_1$ を使って、$b_1 \oplus b_2$ を作れば、$b_1 \xrightarrow{b_2} b_1 \oplus b_2$ の link を張って、$b_1 \oplus b_2$ を $S$ に入れることができる。但し、もし既に $b_1 \oplus b_2$ が $S$ に入っていたら、この作業は実施せず、linkも張らない。

以下同様に、$B$ の元を順に取ってきて、それと $S$ のすべての元とを連結する作業を、$B$ の元が無くなるまで繰り返す。それが終わったら、もし張ったlinkの数が $N-1$ と一致すれば連結で、これがそのまま求める木になっているのでそれを出力して終了、もし $N-1$ より小さければ連結で無いので、$-1$ を出力して終了すればよい。

 

・・・が、なぜこれで十分なのかが全くわからない。

(1) まず、この操作で $A$ の元は明示的には作っていない。よって、作られているとすれば必ずどこかの $b_i$ と、それより以前に作成された $S$ の元 $t \in S$ とのXORで作られているはずなのだけれど、なぜそう巧い具合に $A$ の元に飛んで行ってくれるのか。重複して作成された場合は入れなければいいんだけれど、十分 $A$ の元を構成できるのが不思議。

(2) また、linkも、なぜちょうど $N-1$ 本だけ作られて木になるのか。

(3) 最後に、なぜこれが時間内に終わるのか。$N$ は最大で$2^{18} ≒ 10^5$ くらいになるので、$\mathcal{O}(N^2)$ だとアウトなんだけれど、$B$ の元を回して $\mathcal{O}(N)$、その中で $S$ の元をまわしていたら、$S$ も最大 $N$ 個くらいになるとすれば、$\mathcal{O}(N^2)$ になっちゃわない?

と、三つの疑問を以下で考えます。 

まず、一番簡単な(2)から。

これは、$S$ に新しい元が挿入されたとき、かつ、そのときにのみ、linkが追加されるので、$S$ が $\mathcal{N}$ と一致していれば自ずと、linkは $N-1$ 本。で、linkの作り方から、$S$ の元は必ず $0$ から伸びるlinkで繋がっているので、連結。 $N$ 元 $N-1$ 本連結だから、一本の木になっています。

次に、(1)。 

話を簡単にするために、$S_i$ を、$b_i$ に対する処理が終わったあとの $S$ のことととします。つまり、$S_0 = \{0\}$ で、$S_1 = S_0 \cup S_0\oplus b1$、...、$S_i = S_{i-1} \cup S_{i-1}\oplus b_i$ です。$S_{i-1} \oplus b_i$ は、$S_{i-1}$ の元と $b_i$ とのXORの元の集合とします。

さて、この作業の最初の方を観察すると、次のようになります。

\begin{array}{ccccc}
S_0    &     &     &    & \\
0    &    &     &     & \\
    &     &     &    & \\
S_1    &     &     &    & \\
0    & b_1    &     &     & \\
    &     &     &    & \\
S_2    &     &     &    & \\
0    & b_1    & b_1 \oplus b_2    &     & \\
    & b_2    &     &     & \\
    &     &     &    & \\
S_3    &     &     &    & \\
0    & b_1    & b_1 \oplus b_2    & b_1 \oplus b_2 \oplus b_3    & \\
    &         & b_1 \oplus b_3    &     & \\
    & b_2    & b_2 \oplus b_3    &     & \\
    & b_3    &     &    & \\
    &     &     &    & \\
S_4    &     &     &    & \\
0    & b_1    & b_1 \oplus b_2    & b_1 \oplus b_2 \oplus b_3    & b_1 \oplus b_2 \oplus b_3 \oplus b_4    \\
    &        & b_1 \oplus b_4    & b_1 \oplus b_2 \oplus b_4    & \\
    &         & b_1 \oplus b_3    & b_1 \oplus b_3 \oplus b_4    & \\
    & b_2    & b_2 \oplus b_3    & b_2 \oplus b_3 \oplus b_4    & \\
    &        & b_2 \oplus b_4    &                            & \\
    & b_3    & b_3 \oplus b_4    &                            & \\
    & b_4    &                    &                            &
\end{array}

すると、各回の組み合わせ総数は $1, 2, 4, 8, 16, ...$ と、新しい元を入れるたびに$2$ 倍になっていき、最後には $B$ の元のすべての組み合わせが $S$ に入ることがわかります。ですから、この方法で「$B$ の元のすべての組み合わせのXOR」は網羅できることになります。 この操作は、愚直に全組み合わせを実施すると $2^{\#B}$ 個の組み合わせができるのですが、至る所で重複が発生しています。重複した場合はlinkを張らないので、例えば、$b_8$ のターンにて挿入しようとした $b_3 \oplus b_5 \oplus b_8$ が $b_1 \oplus b_2$ と同じだったとすれば、この元は入れません。また、その次に入る予定だった $b_3 \oplus b_5 \oplus b_8 \oplus b_9$ は別の場所で $b_1 \oplus b_2 \oplus b_9$ として挿入されるので、全組み合わせから失われるわけではありません。

つまり、最終的にできあがった $S$ には、$B$ の元の全組み合わせが入っているので、これが求めたいものの全てです。これに$A$ の元が全て入っていれば連結ですし、入っていなければ $-1$ を出力します。

ということで、(2)もOKでした。

最後に (3) です。いくら至る所重複によって $\# S$ が $2^{\# B}$ よりは少なくなるとはいえ、$\# B \times \# S$ は $N^2$に近づく可能性があります。

そこで、上のアルゴリズムに一つ、$b_i \in S_{i-1}$ ならば、$S_i = S_{i-1}$ とする、つまり、$S_{i-1}\oplus b_i$ の計算をしない、という仕組みを入れます。実装上は、$S$ を使い回すようにしていれば、何もしなくていいです。

では、なぜこの仕組みを入れてもいいのか。

例えば $b_i$ を取った時点で $b_i \in S_{i-1}$ だったとすると、$i$ より小さい数列 $i_1 < ... < i_k < i$ があって、$b_ i = b_{i_1} \oplus ... \oplus b_{i_k}$ と書けているので、その先の任意の $S_{i-1}$ の元 $t$ に対し、$t \oplus b_i = t \oplus b_{i_1} \oplus ... \oplus b_{i_k}$ は $S_{i-1}$ の中に既に存在します(思い出すと、$b_i$ を処理している時点で、インデックスが $i$ より小さい $B$ の元のすべての組み合わせが $S_{i-1}$ に入っているのでした)。ですから、$b_i$ を取り出したらまずそれが $S_{i-1}$ にあるかどうか確認し、もしなければ $S_i$ を作る作業をしますが、既にあれば何もせずに次の $b_{i+1}$ に移ることができます。

また、$b_i$ が $S_{i-1}$ に入っていない、という事態が起こった場合、そのあとの $S_{i-1}$ の元との掛け合わせは、すべてが $S_{i-1}$ にとって新しい元になっていきます。これは、$S_{i-1}$ が、XOR演算において $\{b_1,...,b_{i-1}\}$ の組み合わせのすべてが入っていることから、$(\mathbb{Z}/2\mathbb{Z})^n$ の中での閉じた部分空間になっていること、そこに $b_i$ が入っていないということは、$b_i$ は $(\mathbb{Z}/2\mathbb{Z})^n$ 内での新しい基底になっていて、その結果、部分空間の次元が一つ上がる。つまり、$S_{i-1} \oplus b_i$ は全てが $S_{i-1}$ からはみ出していて、 $S_i$ は$S_{i-1}$ と $S_{i-1} \oplus b_i$ との、重複のない和集合になります。ところで、$(\mathbb{Z}/2\mathbb{Z})^n$ は$n$ 次元だったので、部分空間が拡大するのは $n$ 回だけ。つまり、 $b_i$ が $S_{i-1}$ に入っていないという事態は $n$ 回しか発生しないので、$S_{i-1} \oplus b_i$ の処理をする回数も $n$ 回だけであり、その回毎に $S_i$ の大きさが $2$ 倍になるのだから、結局追加処理は $b_i$ が $S_{i-1}$ に入っているかどうかを確認する $\#B$ 回と、$S$ に元を追加する $2^n = N$ 回しか発生しないことになります。

代数っぽくない書き方をすると、$b_i$ が入ってくるまでの $S$ は、$n$ 個ある bit のうち一部がすべて止まっているか、もしくはいくつかがすべて同期してON/OFFしているなどしています。例えば、$b_1 = 1, b_2 = 2, b_3 = 4$ だったとすると、最初の $3$ bitだけが動き、残りの $n-3$ bitは止まっています。また、例えば $b_1 = 5, b_2 = 6$ だったとすると、この二つから作られる $S$ は、$\{0, 3, 5, 6\}$、二進数で書くと $\{000,011,101,110\}$ で、最上位bitは下位 $2$ つの bit の和(mod 2)になっている、つまり、独立して動いていない。そこに、これらとは独立した新しい元 $7$ が入ってくると($7 = \mathrm{0b}111$ は、最上位bitが下二つの和になっていない)、最上位bitがこれまでと異なる元が生まれます。具体的には、$0\oplus 7 = 7$, $3\oplus 7 = 4$, $5\oplus 7 = 2$, $6\oplus 7 = 1$ の四つの元が生まれ、かつ、これらは全て元の $S$ に入っておらず、新しく $S$ に追加されます。二進数で見てみると、 $\{7,4,2,1\}$ $=$ $\{111, 100, 010, 001\}$ で、全て最上位bitが下二つの和になっていません。この例ではたまたま、元の $S$ の性質が「最上位bitが下二つの和になっている」というものでしたが、$B$ がどのような集合だったとしても、新しい次元が生まれる前はどれかのbitが他のbitに従属して動いており、新しい世界が広がるとその瞬間、$S$ に一次元分のすべての元が一気に投入されることになります。で、そのような回数は $n$ 回だけ、次元が一つずつ拡大して $n$ になるまで、ということになります。

ということで、(3)もクリアしました。

と、ここまで考えてきてやっと、ユーザー解説にさらっと「基底は高々 $n≤18$ 個であることから、このような頂点 a は余裕をもって全探索出来ます」と書いてあることの意味が理解できました。なるほど確かに。


以上、備忘録でした。

最後にSさん、コード見せて頂きました。勉強になりました。ありがとうございます!

参考(Sさんのコードを元に改変): https://atcoder.jp/contests/zone2021/submissions/22264498

2021/04/29

競プロ典型90問-005 Restricted Digits(★7)へのアプローチ

はじめに

先月から開催されている、「競プロ典型90問」について、005 Restricted Digits(★7)に全く歯が立たず、答えを見てやっと理解しました。

そこで思ったのが、確かに答えを見れば「なるほど!」と思えるし、確かにその通りの実装もできるのですけれど、 私は一体これをどうやったら自力でひねり出せるようになるのか、と。私の現在のratingは1200付近なので、おそらくこの問題が次に出ても全く回答できる気がしません。

では、どのような思考の道順で考えていけばゴールにたどり着けるのか、つけないのか、整理してみようと思って書き始めたのがこれです。よって、上位の方には一瞬でわかることでも冗長に書いている点はご容赦ください。あくまでも、ratingが1200程度の人の頭の中の一例です。

 

まずは観察

ということで、最初に実際の数字を入れてみて観察します。$B$ の倍数になるものの個数を求めると言うことは、言い換えると $\bmod B$ で $0$ になるものの個数を求めればよいです。よって、$\bmod B$ の世界の中で考えればOK。

例:$B = 7, c = 1$
$1 = 10^0 ≡_7 1$
$10 = 10^1 ≡_7 3$
$100 = 10^2 ≡_7 2$
...

($\bmod B$ を $≡_B$ で略記する。また、明らかな場合は $B$ も省略する。)


$c = \{1, 4, 9\}$ とすると、例えば

\begin{eqnarray*}
149 &=& 100 + 40 + 9 \\
    &=&  1 \times 10^2 + 4 \times 10^1 + 2 \times 10^0 \\
    &\equiv_7& 1 \times 2 + 4 \times 3 + 2 \\
    &\equiv_7& 2
\end{eqnarray*}

\begin{eqnarray*}
449 &=& 400 + 40 + 9 \\
    &=&  4 \times 10^2 + 4 \times 10^1 + 2 \times 10^0 \\
    &≡& 4 \times 2 + 4 \times 3 + 2 \\
    &≡& 1
\end{eqnarray*}

\begin{eqnarray*}
949 &=& 900 + 40 + 9 \\
    &=&  2 \times 10^2 + 4 \times 10^1 + 2 \times 10^0 \\
    &≡& 2 \times 2 + 4 \times 3 + 2 \\
    &≡& 4
\end{eqnarray*}

下二桁を固定し、上一桁だけ替えてみたところ、$49$ の方は $0 \bmod B$ で変わらず、その値に上一桁の値を足した値が $\bmod B$ での三桁数の値になります。よって、$n$ 桁目までで $0,...,B-1$ のそれぞれになる組み合わせを求めておけば、あと一桁追加して $n+1$ 桁目までの組み合わせ数を求めることができます。

つまり、(1)「桁を増やしていくDPが使えそうだ」、と思いつきます。緑~水色だと、このくらいまでは思いつけそう。私もここまではいけました。

 

DP漸化式を書く

桁を増やしていくDPということは、桁に対して逐次更新していけば $N$ 桁にたどり着けそう。また、各桁について、$\bmod B$ でいくらになっているかを保存しなければならないので、$V[\bmod B の値]$ というベクトルを逐次更新していけばできそう。

そこで $D_n[x]$ を、「$\bmod B$ で $x$ になるような $n$ 桁の組み合わせの数」としてみる。$n$ を増やしていき、$D_N[0]$ を求めることができれば、これが本問題の解答になります。

まず一桁の場合。$D_1[x]$ は

\begin{equation*}D_1[x] = \#\{c_k ≡ x \}\end{equation*}
 
例:$B = 7, c = \{1,4,9\}$ の場合、$\{1,4,9\} ≡ \{1,4,2\}$ なので、 $D_1[x] = (0,1,1,0,1,0,0) $($x = 1,2,4$ のところに$1$が立っている。)
 
$2$ 桁の場合を例で観察。$1$ 桁目の数を$10$ 倍すると$\bmod B$ での値が変わります。例えば $B = 7, c = \{1,4,9\}$ のとき、 $10 ≡ 3$ なので、

\begin{eqnarray*}
1 &≡& 1 \rightarrow 10 = 1 \times 10 ≡ 1 \times 3 ≡ 3\\
4 &≡& 4 \rightarrow 40 = 4 \times 10 ≡ 4 \times 3 ≡ 5\\
9 &≡& 2 \rightarrow 90 = 9 \times 10 ≡ 2 \times 3 ≡ 6
\end{eqnarray*} 

これと$1$ 桁目、つまり、$\{1,4,2\}$ とを和してできあがる値が $\bmod B$ でいくつになるかの組み合わせ数が $D_2[x]$ だから、$\{1,2,4\}$ と $\{3,5,6\}$ とをたしてみると

\begin{eqnarray*}
11 &=& 10 + 1 ≡ 3 + 1 ≡ 4 \\
14 &=& 10 + 4 ≡ 3 + 4 ≡ 0 \\
19 &=& 10 + 9 ≡ 3 + 2 ≡ 5 \\
41 &=& 40 + 1 ≡ 5 + 1 ≡ 6 \\
44 &=& 40 + 4 ≡ 5 + 4 ≡ 2 \\
49 &=& 40 + 9 ≡ 5 + 2 ≡ 0 \\
91 &=& 90 + 1 ≡ 6 + 1 ≡ 0 \\
94 &=& 90 + 4 ≡ 6 + 4 ≡ 3 \\
99 &=& 90 + 9 ≡ 6 + 2 ≡ 1
\end{eqnarray*}  

よって、$D_2[x] = (3,1,1,1,1,1,1)$ となりました。

では、$D_3[x]$ はどうなるか。

$3$ 桁の組み合わせは、$2$ 桁の組み合わせ$\times 1$ 桁の組み合わせだから、$2$ 桁の数字の頭に $1$ つ数字を追加することを考える。つまり、$2$ 桁の数字に $c \times 100$ をたして、$\bmod B$ すると $3$ 桁の数字になるから、$\bmod B$ で $y$ である $2$ 桁の数字(個数は $D_2[y]$)は、$c \times 100$ をたすと、$c \times 100 + y \bmod B$ となります。

例($B = 7, c = \{1,4,9\}$)ならば、$2$ 桁の組み合わせ $D_2[x]$ に対して $100, 400, 900$ をたせばよい。

\begin{eqnarray*}
100 &≡& 2\\
400 &≡& 1\\
900 &≡& 4
\end{eqnarray*}

これを、例えば $D_2[0]$ に入っている$3$ つの組み合わせ$14, 49, 91$ にたすと、

\begin{eqnarray*}
100 + (14, 49, 91) &≡& 2 + 0 ≡ 2 \\
400 + (14, 49, 91) &≡& 1 + 0 ≡ 1 \\
900 + (14, 49, 91) &≡& 4 + 0 ≡ 4
\end{eqnarray*} 

また、他にも例えばたして $2$ になる組み合わせとしては、

\begin{eqnarray*}
400 + 99 &≡& 1 + 1 ≡ 2 \\
900 + 19 &≡& 4 + 5 ≡ 2
\end{eqnarray*} 

があるので、$D_3[2]$ は先の $3$ つと合わせて $D_3[2] = 5$ となる。

つまり、$D_3[x]$ には、$c_k \times 100 + y ≡ x$ となる $(k,y)$ の組について、$D_2[y]$ をたしていけばよい。式で書くと、 

\begin{equation*}
D_3[x] = \sum_{c_k \times 100 + y ≡ x} D_2[y]
\end{equation*}

これを $n$ について一般化すれば、

\begin{equation*}
D_{n+1}[x] = \sum_{c_k \times 10^n + y ≡ x} D_n[y]
\end{equation*}

なる漸化式を得られ、$n$ を $1$ ずつ増やしていけば答えにたどり着けます。

さて、この方法だと計算量は $\mathcal{O}(NKB)$になりまして、制約条件が★1の $N \le 10^5$ は超えられるのだけれど、★4の $N \le 10^{18}$ は超えられない。そもそも $N \le 10^{18}$ という制約は $\mathcal{O}(N)$だけでも超えられないので、必ず $\mathcal{O}(\log N)$ にするアルゴリズムがあるはず・・・つまり、桁数 $N$ を割り算で分割して小さい計算を行い、それらを組み上げて元の $N$ を構成する方法が必ずあるはず。

そういう目つきでさっきの式をもう一度眺めてみます。

\begin{equation*}
D_{n+1}[x] = \sum_{c_k \times 10^n + y ≡ x} D_n[y]
\end{equation*}

これは、一番上の桁に新しい数字を付加しているけれども、実は

\begin{equation*}
D_{n+1}[x] = \sum_{y \times 10 + c_k ≡ x} D_n[y]
\end{equation*}

でも同じになる。つまり、$n$ 桁の方を一段上に上げて、一番小さい桁に $c_k$ をくっつけても同じになる。計算済みのdpベクトルに対して、その上に $1$ 桁追加するのも、下に $1$ 桁追加するのも同じ、ということは逆に $1$ 桁に対して、(2)「$n$ 桁まとめて追加する」こともできるのでは?

 

10^18の壁を越える

この(2)を思いつくのは、私程度のランクのCoderには非常に厳しい気がするのですけれど、ひとまず思いついたとします。

すると、$1$ 桁というのは $D_1[z]$ でしたから、先ほどの式を次のように書き直すことができます。

\begin{equation*}
D_{n+1}[x] = \sum_{z \times 10^n + y ≡ x} D_1[z] \times D_n[y]
\end{equation*}

よく見るとこの式は $D_1$ 側と $D_n$ 側とが対等なので、$n$ 桁の数に対して上に $1$ 桁付加していると考えることもできるし、逆に $1$ 桁の数に対して下に $n$ 桁付加していると考えることもできる。実際、$n+1$ 桁の数があったときに、どちらを先に作ったとしても、場合の数は変わりません。

ということは、$n$ 桁の数に $m$ 桁を付加することもできるのではないか?と思って立式を試みると(下の方で $m$ の文字を使いたいので、ここでは $i,j$ に記号を替えて)、

\begin{equation*}
D_{i+j}[x] = \sum_{z \times 10^j + y ≡ x} D_i[z] \times D_j[y]
\end{equation*}

と書けることがわかります。$j$ 桁の数の上に $i$ 桁付加しているとも取れるし、$i$ 桁の数の下に $j$ 桁を付加しているとも取れますが、いずれにしても、任意の $i,j$ についてこの式が成立します。

さて、求めたいのは $D_N[x]$ であり、これを$\mathcal{O}(N)$ 程度の計算で求められればよかったのだから、 $N$ を $\log N$ 個程度の足し算で構成すればよい。最も単純なのは $N$ を二進数展開すること、つまり、$M = \lfloor\log_2(N) \rfloor$ として、$N$ を

\begin{equation*}
N = \sum_{m=0}^M n_m 2^m
\end{equation*}

(但し、$n_m$ は$0$ または $1$)と書き表すと、まず $D_{2^m}[x]$ を全部作っておいて(これは $\log_2 N$ 回程度で可能)、次にそれらを足し込んでいけば(これも $\log_2 N$ 回程度で可能)、$D_N[x]$ を作ることができます。計算量は、一回の遷移に $\mathcal{O}(B^2)$ かかるので、 全部で $\mathcal{O}(B^2 \log N)$ 程度になりそうです。

具体的には、まず $P_m[x] = D_{2^m}[x]$ としてこれを全て作成します。

\begin{eqnarray*}
P_m[x]&=& D_{2^m}[x] \\
&=& D_{2^{m-1} + 2^{m-1}}[x] \\
&=& \sum_{z \times 10^{2^{m-1}} + y ≡ x} D_{2^{m-1}}[z] \times D_{2^{m-1}}[y] \\
&=& \sum_{z \times 10^{2^{m-1}} + y ≡ x} P_{m-1}[z] \times P_{m-1}[y]
\end{eqnarray*}

次に、$0 \le m$ について $V_m$ を $\sum_{l=0}^m n_l 2^l$ 桁目までの組み合わせ数とすれば、$V_{-1} = (1,0,...,0)$ として、$n_m = 1$ならば

\begin{equation*}
V_m[x] = \sum_{z \times 10^{2^m} + y ≡ b} V_{m-1}[z] \times P_m[y]
\end{equation*}

$n_m = 0$ ならば

\begin{equation*}
V_m[x] = V_{m-1}[x]
\end{equation*}

として、$m$ を増やしていけば、$\log_2 N + 1$ 回の更新で $V_M[x] = D_N[x]$ が得られます。特に $V_M[0]$ が解答になります。

 

おわりに

ということで、思いつきたかったのは、

(1)「桁を増やしていくDPが使えそうだ」

(2)「$n$ 桁まとめて追加する」

でした。式を見ながらこの二つに気づければ、005は攻略できたように思います。・・・ただ、実際には、自分では(2)は思いつけないだろうな・・・。

あと、美しい式を書くのが大事だなと思いました。おそらくrating上位の皆さんはそれが頭の中で瞬時に構成できているんだろうと思いますが、修行が足らないと、それを何らかの外部装置で補う必要があって、一つの有力な手段が、「きれいに式を描く」ということだなと。実際、

\begin{equation*}
D_{n+1}[x] = \sum_{c_k \times 10^n + y ≡ x} D_n[y]
\end{equation*}

では全然先が見えませんが、

\begin{equation*}
D_{n+1}[x] = \sum_{z \times 10^n + y ≡ x} D_1[z] \times D_n[y]
\end{equation*}

これが描けた段階で、かなり視界が開けるような気がします。(さらに、回答例でも注釈のあった、たたみ込みを高速計算する可能性も示唆されます。)もちろん、この記事は答えを見てから書いているので、自力でこれを導出できる気が全くしないのですけれど、ともかくその前に、美しい式を描くこと。描こうとすることが、rating積み増しを目指す上で大事だと思いました。

2021/04/06

Blogger で google code prettify を使うときに、コードが折り返されてしまう

一つ前の記事を投稿する際、コードを書きたくて「google code prettify」を使ったのですが、横スクロールバーが表示されず、コードが強制的に折り返されてしまう問題が発生しまして。

ググると、

pre.prettyprint {
    word-wrap: normal;
    overflow-x: auto;
}
という感じで書けばいいですよ、というのがいくつか出てくるのですが、おそらくベースのスタイルシートの設定か何かで、全然効かない。ってことで、Chromeの開発ツールなどを適当に触ってみていたところ、

pre.prettyprint {
    word-wrap: normal;
    overflow-x: auto;
    white-space: pre;
}
でできることがわかりました。white-space の設定が pre-wrap になっているテーマだとダメみたいです。

ということで、上の設定を、Bloggerの管理画面から「テーマ」→「カスタマイズ」→「詳細設定」→「CSSを追加(プルダウン)」に貼り付ければOKです。

GCPのdeployment managerでlocal ssdを繋げる

GCPの deployment manager で local ssd ( SCRATCH Disk ) を繋げて立ち上げる際の、jinjaの書き方です。ググってもなかなか出てこなかったので、備忘録。

deployment manager にくっついてくるサンプルのjinjaファイルには、deployするインスタンスにPRESISTENT diskをくっつけてありますので、そこからスタートします。

disks:
  - deviceName: boot
    type: PERSISTENT
    boot: true
    autoDelete: true
    initializeParams:
      sourceImage: https://www.googleapis.com/compute/v1/projects/debian-cloud/global/images/family/debian-8

サンプルの、disksの中はだいたいこんな感じになっています。sourceImageはdebian-8になっていますが、今は適当にアップデートされているはず。で、ここに、

disks:
  - deviceName: boot
    type: PERSISTENT
    boot: true
    autoDelete: true
    initializeParams:
      sourceImage: https://www.googleapis.com/compute/v1/projects/debian-cloud/global/images/family/debian-8
  - deviceName: local-ssd
    type: SCRATCH
    interface: NVME
    autoDelete: true
    initializeParams:
      diskType: local-ssd

local ssdを、こんな感じでくっつけます。device nameはおそらく何でもOK。interfaceはSCSIでもいいかも。autoDeleteは必須。このjinjaファイルでdeployすると、インスタンスにlocal-ssdがくっついて立ち上がります。但し、これだけでは使えるようにはなっていないので、同じくdeployment managerで使うstartup-scriptに、ディスクをフォーマットしてマウントするコマンドを書いておきます。公式に「ローカル SSD を使用するインスタンスを作成する」があるので、それを真似て、

sudo mkfs.ext4 -F /dev/nvme0n1
sudo mkdir -p /mnt/disks/local-ssd
sudo mount /dev/nvme0n1 /mnt/disks/local-ssd
sudo chmod a+w /mnt/disks/local-ssd

こんな感じでstartup-scriptに追記しておくと、立ち上がったときに使えるようになっています。マウント場所やアクセス権は適宜設定してください。あと、SCSIディスクをくっつける場合や、local ssdを複数くっつける場合はdev/nvme0n1 が変わると思います。

2020/10/27

iPad + Apple Pencil はリモートワーク必須アイテム

リモートワークの効率を上げるためのオンラインミーティングツールとして、iPad + Apple Pencil は必須だという話。さほど新しい話ではないですが、意外に知らない人が多いので、紹介します。

 

普段がデスクワークの方でしたら、自分一人でPCに向かって作業する時間と、打ち合わせの時間とがだいたい日常の業務の主だろうと思います。その中で、一人作業の効率化は、例えば椅子やキーボード、モニターなどのリモート環境を整えていくことで、かなり効率を上げることができました。

一方で打ち合わせについては、ZoomやTeams、Google Meetなどの対面コミュニケーションツールの性能がどんどん良くなってきて、音声と表情までは従来と変わらないくらいまで(多少慣れが必要ですが)コミュニケーションできるようになってきましたが、一つ欠けているのが「ホワイトボードの共有」でした。プレゼン資料の共有まではかなりイケていますが、ホワイトボードだけがなぜか置き去りにされてきています。

これは、「書く」という行為が多分にデバイスに依存するためです。紙と鉛筆、もしくはホワイトボードとマーカーは非常に洗練された表現ツールで、文字を書いたり、絵や図を描いたり、注目をひいたり、自分が表現したい事物や気持ちを自由自在に表現できますが、それを伝送できるものがなかなか出なかった。Zoomにもホワイトボードは備わっていて、それなりに使えますが、自由自在に入力するためにはマウスでは辛いですし、ペンタブもかなり大雑把だったり、思うように描けなかったりします。(おそらく専用の熟練が必要。)

そこで、iPad+Apple Pencil の出番です。

ただ iPad を液タブとして使う、というだけなのですが、これを他のホワイトボード共有サービスと組み合わせるとめちゃめちゃ便利、というのが主旨です。

 

用意するものは iPad と、Apple Pencil。単に「書く/描く」というだけでも、この組み合わせはめちゃめちゃ使いやすくて、ペン先の細かいコントロールが利くので、細かい数式などもしっかり書けます。私は書き心地を試す際には必ず積分の様々な公式を書いてみるのですが、上付き文字、下付文字、インテグラル、インフィニティなどがきれいに書けると、これはいいデバイスだなと思います。

次に、iPad にホワイトボードアプリを入れます。リアルタイム共有ができるものを使いましょう。私は日頃 Google Workspace (旧 GSuite)を使っているので、Jamboard のiPad用アプリを入れます。Teams のユーザーならば Office 365 の MS Whiteboard でもOK。これらは iPad に専用アプリがあるので、これが書き心地的にかなり重要です。

さて、これらのサービス、Jamboard や MS Whiteboard は、クラウドを通じて共有できるのが特徴ですが、これを自分自身と共有するのがミソ。だいたいこういうクラウドサービスは、同じサービスにアカウントを持っていないと共有できなくて、「使えます?」「使えません」っていう会話がそこかしこで繰り広げられています。社内ならそうでもないですが、外部ミーティングだとしばしばおこります。ですが、自分と自分は当然同じクラウドサービスを使えますので、iPad と PC で同じサービスを使うことができる。つまり、iPad で立ち上げた Jamboard や MS Whiteboard を、PC でも見ることができます。

そこで、その画面をミーティングで共有します。