GCJ 2018 round2

A 問題

i 番目と i+1 番目の間をいくつのボールが通過するかを計算できると、それをそのまま。

B 問題

丁度にする必要はなくて、適当に辻褄をあわせることができる、というのが重要な考察。
(i,j) を使う、というのを n×n グリッドの (i,j) の位置に駒を置くと言い換える。駒がおいてある場所の総和が R, B 以下なら良いわけだけど、もし駒の上が空になっていたら上に動かしたほうが得である。
つまり駒の置いてある形はヤング図形のようになっている。また、ヤング図形の幅、高さは 40 程度である(これは 1+2+3+...+40 > 500 から言える)。
以上を踏まえると DP で解ける。

C 問題

値ごとにバラして考えて、変えない場所を最大化することを考える。これは単純な最大二部マッチングに帰着される。

D 問題

単なる場合分けだと思うけど通らなかった…。

FFT (2)

Wikipedia には Hadamard Transform について次のように書かれている。Hadamard transform - Wikipedia

The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2.

まあ分かるのだが,FFTと同様に多項式で説明できる。恐らくどこかで既出だと思う。

記述の煩雑さを防ぐために 2×2×2 の Hadamard Transform に関して説明する。一般に関してもほとんど変わらない。数列 a[n] の Hadamard Transform は多項式で説明できる。具体的には 3 変数多項式

$$f(x,y,z)=a[000] + a[001] x + a[010] y + a[011] xy + a[100] z + a[101] xz + a[110] yz + a[111] xyz$$

に対応させる。xor convolution が高速に計算できるというのは,多項式 f, g の積が係数表現より具体値表現の方が高速に計算できることに由来する。実際にどのような具体値で計算するのがいいのかというと,書くのが大変なので 2 変数多項式で書くと,

\begin{align}
f(+1,+1) &= a[00] + a[01] + a[10] + a[11] \\
f(-1,+1) &= a[00] - a[01] + a[10] - a[11] \\
f(+1,-1) &= a[00] + a[01] - a[10] - a[11] \\
f(-1,-1) &= a[00] - a[01] - a[10] + a[11]
\end{align}

が良い。何故かと言うと,$x^2=1$ を満たすような $x$ というのが xor の性質をよく言い表していて,ちなみに Hadamard 行列にもなっていて,ということ。基本的には 2D FFT とかも $x^n=1$ を満たすような $x$ というのが鍵となっている。逆変換も存在しないと辛くて,Hadamard Transform の場合は標数 2 の体(-1=1 となるような体)は辛いし,一般には原始 n 乗根が存在しない体も辛い。

この議論を派生させると,$x^2=x$ となるような $x$ を使って変換するとどうなるのか,というのが出てきて,これが丁度 Zeta Transform に対応している。

April Challenge 2018

Chef 側の解説がまだ出てないので、それ読んで思うものがあったら更新します。

CHEFAT:
この制約なら SIMD O(n^2) 通る。そうは言っても 2 ケースほど TLE になってしまったので、平方分割+遅延評価で平均的に速くなるようにした。
多くの提出は $\log(1-x)=-x-x^2/2-x^3/3-...-x^{100}/100$ で近似してる。
最後に exp とったときの誤差は大丈夫なのかなと思ったけど $e^{x+\epsilon} - e^x \approx \epsilon e^x$ なので大丈夫そう。

SSPLD:
固有多項式を埋め込む(そんなに次数は大きくない)。具体値を埋め込むとコード長制限に引っかかるため実行時に計算。多項式乗算・剰余は FFT で高速にやらないと厳しい。多くの提出は hadamard transform を使ってるように見える。確かにできそう。

11 変数多項式 f(x,y0,...,y9) を FFT する感じ?f(x,y0,...,y9) にある多項式を掛けることで遷移を表現できる(下の桁から値を決めていくわけだが、遷移関数は周期的、周期は 10^k mod s に依存)。そして S×2×2×…×2 の FFT をしておけば係数の積から値の積に変換できて、解ける。(S に関して言うと 2 冪じゃないから FFT じゃないけど(高速ではない))→よく考えたらNTTなのでSでできない。いや体拡大でできるかもしれないけど、そうではないんだろう。