ICPC国内予選2021 参戦記

torisasami, tokusakurai とDELIAIR としてICPC国内予選2021に参戦しました。 結果は全体17位、学内6位で（正式発表はまだですが）残念ながら予選通過はなりませんでした。

開始前

discord で通話しながら参戦。 何回もチーム戦をしているので慣れてはいる。

とりあえず A : sapphire15 B : torisasami C : tokusakurai ではじめることに。

予選中

A

問題文が長い。読解に時間がかかった。 一気にすべての器が空になるパターンない？と思ったけど選んだ器は減らないのでそんなパターンはない。 これで少し手が止まってしまって、その間に torisasami が B を通してしまった。 なんだかんだで7分位でAC。

C

構文解析らしいがtokusakurai がそのあとがよくわからないらしいのでヤバそう。 全方位木DPでできそういう話はこの時点で出てたけど、さすがにCに出すか？という話になって実装しようとしなかった。

自分が構文解析担当と事前に決めてたのでのでとりあえず構文解析を書いて構文木を作るところまでやる。 その間でも簡単な解法は出ず、順位表を見ても誰もCを通してないということでDに行く。

D

ぱっと見できそうに見えるけど３人で話してもよくわからない。 かなり焦る気持ちも出てきたので心を落ち着かせるために E を見る。

E

最初にタクシーを使う回数が大体40回以下だからそれで拡張ダイクストラするという解法を提案するが、必ず歩道が使えるわけではないので２人に撃墜される。 そのあとすぐに、tokusakurai がタクシーを乗った回数を優先的に見るダイクストラもすることを提案して良さそうなのでそのまま実装はじめる。（天才） ここまで10分なかったと思う。

D 再び

ここでもう一度 D を見ると解法が降ってくる。

使う棒を入れ替えるときに入れ替えたもの同士を1つのグループとみれば、全体を３分割できる。 このとき３つのうち最小のものが風船を配ることのできる子供の数になる。 あとは２次元DPであらゆる３分割ができるどうかを判定すればいい。

解けたので自分が実装をすることに。 torisasami も同時にCの全方位木DPを書くことになった。

D は結構バグらせたけど複雑な実装ではないので通る。開始36分くらいだったらしい。 ここらで5完のチームも出てきて5完しないと予選通過は厳しいかもしれないという雰囲気がでてくる。

F, G

2人の実装を手伝うのも難しそうなので F, G を眺める。 F は問題文を説明すると実装中の tokusakurai が DM分解 っぽいと言う。 DM分解をググったけどよくわからなかったので、一旦スルーする。

Gは頑張ってbitDPすれば行けそうに見えるけど、詳細を詰めるのが大変そう。 個人的には F よりかは希望がありそうに見えた。

結局 30分くらい2人のサポートに回る。 テストケースの解析をしたり、テストケースを作ったり。 結局ここでたいした貢献ができなかったのでちょっともったいなかったかもしれない。

Eは問題を勘違いしてたみたいだけど2ペナしながらも修正して通す。そのあとすぐに C も合わせることができたみたいで通して5完。（まあまあな重実装だったけど2人ともさすが）

F, G 再び

順位表を見る限り完数勝負にしなければ厳しそう。 F はtokusakurai が結構見えてそうなので torisasami と解法を詰める。

一方で自分は G を頑張ったらできそうにみえたので予選通過のオッズを上げるためにも G を担当することにする。

G は縦列の通路でランプをおかなければならないものを保持しながらbitDPすればよさそうなんだけど、横列も見なければいけないし単純ではない。残り30分くらいで解法を詰めて実装にかかる。（終ったあとに嘘だったことがわかった（悲しい）） 残り5分で実装し終わるけど当然サンプルが合わない。 すると、tokusakurai がFが合いそうと言う。 残り1分でtestcase1を通したらしい。 行けるか？と思ったが、、、

残念ながらtestcase2でWAが出て終了。

感想、反省

悔しい結果となってしまいました。 問題は全体としてやや難しいセットですが一問一問はいい問題だっただけに残念です。

敗因ですが、個人的には実力不足はもちろん精神面にもあると感じました。

正直なところ開始前から浮き足立っていた感触はありました。*1 そこにC, Dで詰まったことが加わり、チーム全体としてあまり冷静になれていなかったように感じます。 実はそのような展開になる可能性があることを予想はしていましたし、そのため競技中の声かけを意識したつもりなんですがオンラインということもあってなかなか難しかったです。*2

その他、全体としての立ち回りなど反省はつきないですが終ったことですし一旦ここまでにしたいと思います。

最後に

最後になりましたが一緒に出てくれたチームメイトの2人には感謝でいっぱいです。 残念な結果となりましたが、2人のおかげでいい思い出ができました。

また、コーチを引き受けてくださった DEGwer さん、大会運営に関わる方々、OB/OGの会の方々にも深く感謝したいと思います。ありがとうございました。

来年はどうなるかわかりませんがこのまま終わるのは悔しいのでたぶん出ると思います。 そのために精進しなきゃですね......。 何とか人生との両立を頑張っていきたいと思います。*3

*1:これはPGBattleや国内模擬でいい結果が出せたことが裏目に出た部分もあると思います。

*2:自分もあまり冷静でなかったことは自覚していました

*3:留年すればICPCに1年多く出れるってマジ？！

Hadamard 変換とbitwise XOR convolution

最近の ABC は 8 問制になって知らない高度典型がたくさん出るようになりました。（ありがたいけど勉強が追いつかず困ったものです） そんな高度典型はあまり知られていないためでしょうか、解説している記事がとても少ないことが多いです。 XOR による畳み込みもその1つです。（出題は 6 問制のときですが）

↓この記事における XOR による畳み込み

judge.yosupo.jp

Hadamard 変換で畳み込みが可能という記述は見かけますが日本語でその証明を詳しく記してある記事はないようでしたのでここにできるだけ詳しく記しておきたいと思います。

ついでに高速 Hadamard 変換や他の bit 演算による畳み込みとの関係性についても紹介したいと思います。

Kronecker 積

まずは、Herdamard変換を説明する上で重要となる Kronecker 積を導入していきたいと思います。

Kronecker 積とは 2 つの行列$A = \lbrace a_{i, j}\rbrace_{n\times m}, B = \lbrace b_{i, j}\rbrace_{p\times q}$に対して 2 項演算$\otimes$を用いて次のように定義されます。

$$ \begin{align} \begin{split} A\otimes B&= \begin{pmatrix} a_{1,1} B & \cdots & a_{1, m} B \\ \vdots & \ddots & \vdots \\ a_{n,1} B & \cdots & a_{n, m} B \\ \end{pmatrix} \\ &= \begin{pmatrix} a_{1, 1}b_{1, 1} & \cdots & a_{1, 1}b_{1, q} & \cdots & a_{1, m}b_{1, 1} & \cdots & a_{1, m}b_{1, q} \\ \vdots & \ddots & \vdots & \cdots & \vdots & \ddots & \vdots \\ a_{1, 1}b_{p, 1} & \cdots & a_{1, 1}b_{p, q} & \cdots & a_{1, m}b_{p, 1} & \cdots & a_{1, m}b_{p, q} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{n, 1}b_{1, 1} & \cdots & a_{n, 1}b_{1, q} & \cdots & a_{n, m}b_{1, 1} & \cdots & a_{n, m}b_{1, q} \\ \vdots & \ddots & \vdots & \cdots & \vdots & \ddots & \vdots \\ a_{n, 1}b_{p, 1} & \cdots & a_{n, 1}b_{p, q} & \cdots & a_{n, m}b_{p, 1} & \cdots & a_{n, m}b_{p, q} \\ \end{pmatrix} \end{split} \end{align} $$

複数の Kronecker 積を簡単に表現するために

$$A_1\otimes A_2 \otimes \cdots \otimes A_n = \bigotimes_{i = 1}^n A_n$$

という記法も導入しておきます。

この Kronecker 積には$A, B, C$を適当なサイズの行列、$k$をスカラーとして以下のような性質があります。

$$ \begin{align} \begin{split} & k(A\otimes B) = (kA)\otimes B = A \otimes (kB) \\ & (A\otimes B) \otimes C = A \otimes (B \otimes C) \\ & (A\otimes B)(C\otimes D) = (AC) \otimes (BD) \\ \end{split} \end{align} $$

これらは要素を書き下すなどして簡単に証明することができます。

2 つ目の式は結合則が成り立つことを示しています。

また、1 つ目と 3 つ目の式をそれぞれ利用して次の式が成り立つことも示すことができます。

$$ \begin{align} \begin{split} \bigotimes_{i = 1}^n{(k_i A_i)} &= \left(\prod_{i = 1}^n{k_i}\right) \left(\bigotimes_{i = 1}^n{A_i}\right) \\ \left( \bigotimes_{i = 1}^n{A_i} \right)\left( \bigotimes_{i = 1}^n{B_i} \right) &= \left( \bigotimes_{i = 1}^n{A_i B_i} \right) \end{split} \end{align} $$

もう一つだけ性質を示しておきます。

$J_{n, m}$を要素がすべて 1 のである${n\times m}$行列、行列に対する 2 項演算子$\circ$を行列の各要素ごとの積（$(A\circ B)_{i,j} = a_{i, j} b_{i, j}$）とします。 このとき$A = \lbrace a_{i, j}\rbrace_{n\times m}, B = \lbrace b_{i, j}\rbrace_{p\times q}$に対して、

$A\otimes B = (A\otimes J_{p, q}) \circ (J_{n, m}\otimes B)$

が成り立ちます。これも要素を書き下せば明らかだと思います。

Hadamard 変換

Hadamard 変換は$2^n$個の実数から$2^n$個の実数への線形写像であり Hadamard 行列$H_n$によって記述されます。 信号解析で結構使われるみたいです。

Hadamard 行列

Hadamard 行列は以下のように定義されます。

$$H_n = \begin{cases} J_{1, 1} & n = 0 \\ \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1 \\ 1 & -1 \end{pmatrix} \otimes H_{n-1} = H_1 \otimes H_{n-1} & otherwise \end{cases}$$

すなわち

$$H_n = \overbrace{H_1 \otimes H_1 \otimes \cdots \otimes H_1}^{n個} = \bigotimes_{i = 1}^n{H_1}$$

です。

具体的に書き下すと

$$H_1 = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1 \\ 1 & -1 \end{pmatrix}, H_2 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ \end{pmatrix}, H_3 = \frac{1}{2^{3/2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ \end{pmatrix} $$

です。

Hadamard 行列の性質

まず、$H_1$が対称行列であることから 任意の Hadamard 行列も対称行列であることがわかります。

さらに、

$$ \begin{align} \begin{split} H_nH_n &= \left(\bigotimes_{i = 1}^n{H_1}\right)\left(\bigotimes_{i = 1}^n{H_1}\right) \\ &= \bigotimes_{i = 1}^n{(H_1H_1)} \\ &=\bigotimes_{i = 1}^n{I_2} = I_{2^n} \end{split} \end{align} $$

であることから、Hadamard 行列は逆行列が自分自身であり、ユニタリ行列でもあることがわかります。

xor による畳み込みとの関係を示す上で重要なものが次の性質です。

$$(H_n)_{i, j} = \frac{1}{2^{n/2}} (-1)^{\mathrm{popcount(i\&j)}}$$

$i\&j$は$i, j$の bitwise-AND、$\mathrm{popcount}$は 2 進数で表わしたときの 1 の個数を表わしています。この性質を示していきます。

まず、Hadamard 行列は次のように分解できます。

$$H_{n} = \left({J_{2^{n-1}} \otimes H_1 \otimes J_{2^{0}}}\right) \circ \left({J_{2^{n-2}} \otimes H_1 \otimes J_{2^{1}}}\right) \circ \cdots \circ \left({J_{2^{n-i}} \otimes H_1 \otimes J_{2^{i-1}}}\right) \cdots \circ \left({J_{2^{0}} \otimes H_1 \otimes J_{2^{n-1}}}\right)$$

これだけでは少しわかりにくいので、$H_3$の場合を図にしました。

これを見ると $J_{2^{3-k}} \otimes H_1 \otimes J_{2^{k - 1}}$ の$i$行$j$ 列目の要素は、$i$と$j$の bitwise-AND の下から$k$桁目の値によって決まっていることが分かります。具体的には値が 0 なら要素の値は $1/\sqrt{2}$ 、 1 なら $-1/\sqrt{2}$ となっています。

一般の$H_n$についても$\left({J_{2^{n-k}} \otimes H_1 \otimes J_{2^{k - 1}}}\right)_{i, j} $は$i\&j$の下から$k$桁目によって決まります。 したがって、$(H_{n})_{i, j}$は$i\&j$の 1 の数だけ符号が反転することになります。

XOR による畳み込み

いよいよ Hadamard 変換による畳み込みについて解説していきます。

長さ$2^n$のベクトル$\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c}$が

$$c_{k} = \sum_{i, j, i\oplus j = k}{a_i b_j}$$

の関係にあるとします。（$\oplus$は bitwise-XOR）このとき、

$$H_n \boldsymbol{c} = 2^{n/2}H_n \boldsymbol{a} \circ H_n \boldsymbol{b}$$

が成立します。

証明

変換後の$k$番目の要素を考えます。

$S = \{ j | (H_n)_{k, j} = 1/2^{n/2}, 0 \le j < 2^{n} \}, T = \{ j | (H_n)_{k, j} = -1/2^{n/2}, 0 \le j < 2^{n} \}$とします。

すると、

$$(H_n \boldsymbol{a})_k = \frac{1}{2^{n/2}}\sum_{i \in S}{a_i} - \frac{1}{2^{n/2}}\sum_{i \in T}{a_i}$$

となります。

$(H_n \boldsymbol{b})_k$についても同様なので、

$$2^{n/2}(H_n \boldsymbol{a})_k \circ (H_n \boldsymbol{b})_k = \frac{1}{2^{n/2}}\sum_{(i, j)\in (S\times S)\cup(T\times T)}{a_i b_j} - \frac{1}{2^{n/2}}\sum_{(i, j)\in (S\times T)\cup(T\times S)}{a_ib_j}$$

ここで、非負整数$x, y$について

$$\mathrm{popcount}( (x\oplus y)\&k) = \mathrm{popcount}(x\& k) + \mathrm{popcount}(y \& k) - 2\mathrm{popcount}( (x\& k)\& (y \& k))$$

が成立する*1ことから、パリティに注目すると

$$(-1)^{\mathrm{popcount}(i\& k)}(-1)^{\mathrm{popcount}(j\& k)} = (-1)^{\mathrm{popcount}( (i\oplus j)\& k)}$$

が得られます。

したがって、

$$(S\times S)\cup(T\times T) = \{(i, j) | (i\oplus j)\& k \in S \}$$ $$(S\times T)\cup(T\times S) = \{(i, j) | (i\oplus j)\& k \in T \}$$

です。

すなわち、$2^{n/2}(H_n \boldsymbol{a})_k(H_n \boldsymbol{b})_k$は$H_n \boldsymbol{c}$そのものであることがわかりました。

（追記）tokusakurai 氏から$H_n$が$n$個の$H_1$の Kronecker 積で表わすことができる事実を使えば$n = 1$のときのみ考えれば十分というという指摘をもらいました。

高速 Hadamard 変換

単純に Hadamard 行列を掛けるだけでは Hadamard 変換の計算量は $\Theta(4^n)$ であり、XOR の畳み込みを行うには愚直に計算した方が速いです。

これを$\Theta(n2^n)$で行うのが高速 Hadamard 変換です。

アルゴリズム

Hadamard 行列は以下のように分解できます。

$$H_n = \prod_{i = 1}^{n}{I_{2^{n-i}} \otimes H_1 \otimes I_{2^{i-1}}}$$

$H_{3}$の場合はわかりやすさのため$1/2^{n/2}$を分けて書くと、

$$H_3 = \frac{1}{2^{n/2}} \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \\ \end{pmatrix} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \\ \end{pmatrix} $$

です。

$$\boldsymbol{a'} = \left(I_{2^{n-i-1}} \otimes H_1 \otimes I_{2^{i}}\right)\boldsymbol{a}$$

は、$i$ bit 目のみが異なる$x, y$に対し、

$$ \begin{pmatrix} a'_{x} \\ a'_{y} \end{pmatrix} = H_1 \begin{pmatrix} a_{x} \\ a_{y} \end{pmatrix} $$

とする操作に当たります。

したがって、分解によって得られる$n$個の行列を掛ける操作は、行列 1 つあたり$\Theta(2^n)$で可能なので全体で$\Theta(n 2^n)$で Hadamard 変換を行うことができました。

この高速 Hadamard 変換と、前に示した Hadamard 変換と XOR の畳み込みの関係より、長さ$2^n$のベクトルに対するXORの畳み込みも$\Theta(n 2^n)$でできることが分かります。

実装例

剰余環では$2^{-n/2}$を掛ける操作はできない場合があるので、高速 Hadamard 変換では$2^{n/2}H_n$を掛ける操作、逆変換では$2^{-n/2}H_n$を掛ける操作を行うことでプログラム中で足し算、引き算、掛け算と整数の割り算しかしなくともよくしています。

2021/11/20追記

上のプログラムで行っている変換を$\tilde{H}_n = 2^{n/2}H_n$とすると、$\boldsymbol{a}, \boldsymbol{b}$をたたみ込んだあとの配列を$\boldsymbol{c}$として、

$$\tilde{H}_n \boldsymbol{c} =\tilde{H}_n \boldsymbol{a} \circ \tilde{H}_n\boldsymbol{b}$$

が成立します。 したがって、何度も畳み込みを行いたいときでもいちいち逆変換を行う必要がありません。 さらに線形性にも注意すると様々な問題に応用できます。（特に Nim が絡む問題 *2）

追記終

// fast Walsh–Hadamard transform
template<class T>
std::vector<T> fast_hadamard_transform(std::vector<T> vec) {
    using hadamard_size_type = typename std::vector<T>::size_type;

    auto vec_size = vec.size();

    // check vec_size is power of 2
    assert(((vec_size - 1)&vec_size) == 0);
    
    for(hadamard_size_type i = 1; i < vec_size; i = i << 1) {
        auto mask = ~i;
        for(auto j = i; j < vec_size; j = (j+1)|i) {
            T a = vec[j&mask];
            T &b = vec[j];
            vec[j&mask] += b;
            b = a - b;
        }
    }

    return vec;
}

// inverse fast Walsh–Hadamard transform
template<class VecType>
auto inv_fast_hadamard_transform (VecType &&vec) {
    auto vec_size = vec.size();
    auto &&ret = fast_hadamard_transform(std::forward<VecType>(vec));
    for(auto &i : ret) i /= vec_size;
    return ret;
}

// bitwise xor convolution
// using fast-Walsh–Hadamard-transform
template<class T>
std::vector<T> xor_convolution
    (const std::vector<T> &a, const std::vector<T> &b) {
    using xorconv_size_type = typename std::vector<T>::size_type;

    assert(a.size() == b.size());

    auto vec_size = a.size();
    std::vector<T> &&transa = fast_hadamard_transform(a),
                   &&transb = fast_hadamard_transform(b);
    
    for(xorconv_size_type i = 0; i < vec_size; i++) {
        transa[i] *= transb[i];
    }
    return inv_fast_hadamard_transform(transa);
}

Library Checkerへの提出

AND、OR による畳み込みへの応用

アルゴリズム

まず、AND による畳み込みを考えます。

いきなりですが$G_n$を以下のように定義します。*3 *4

$$G_n = \bigotimes_{i = 1}^n \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix} $$

長さ$2^n$のベクトル$\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c}$が

$$c_{k} = \sum_{i, j, i\& j = k}{a_i b_j}$$

の関係にあるとき、

$$G_n \boldsymbol{c} = G_n \boldsymbol{a} \circ G_n \boldsymbol{b}$$

が成立します。

詳しく証明は記しませんが、

$$(G_n)_{i, j} = \begin{cases} 1 & (i\&j = i) \\ 0 & otherwise \end{cases} $$

であることを利用すると Hadamard 変換のときと同様に証明できます。

また、逆行列は

$$G_n^{-1} = \bigotimes_{i = 1}^n \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix}^{-1} = \bigotimes_{i = 1}^n \begin{pmatrix} 1 & -1 \\ 0 & 1 \\ \end{pmatrix}$$

となります。

AND による畳み込みが理解できれば OR による畳み込みも bit を反転させたようなものなので、

$$\bigotimes_{i = 1}^n \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ \end{pmatrix}$$

でできることが分かると思います。

実装例

今までのことを踏まえて AND, OR, XOR の畳み込みが全部できるようなライブラリを書きました。

もっと簡潔になると思っていたのですが 100 行を超えてしまいました。*5

template<class T>
class Bitwise_convolution {
    using Vec = std::vector<T>;
    using conv_size_type
    = typename Vec::size_type;

    template<T (*a)(), T (*b)(),
             T (*c)(), T (*d)()>
    static constexpr std::pair<T, T>
    liner_map(const T &x, const T &y) {
        return {a()*x + b()*y, c()*x + d()*y};
    }

    template<std::pair<T, T> 
            (*liner_map)(const T&, const T&)>
    static constexpr Vec 
    kronecker_product(Vec vec) {
        using kp_size_type =
        typename Vec::size_type;

        auto vec_size = vec.size();

        // check vec_size is power of 2
        assert(((vec_size - 1)&vec_size) == 0);
        
        for(kp_size_type i = 1; i < vec_size; i = i << 1) {
            auto mask = ~i;
            for(auto j = i; j < vec_size; j = (j+1)|i) {
                T &a = vec[j&mask];
                T &b = vec[j];
                std::pair<T, T> &&tmp = liner_map(a, b);
                a = tmp.first;
                b = tmp.second;
            }
        }
        return vec;
    }

    static constexpr T conv_zero() { return T(0);  }
    static constexpr T conv_one()  { return T(1);  }
    static constexpr T conv_neg()  { return T(-1); }

    template<class VecType>
    static auto and_map (VecType& vec) { 
        return kronecker_product
               <liner_map
                <conv_one , conv_one ,
                 conv_zero, conv_one >>(vec);
    }
    template<class VecType>
    static auto and_map_inv (VecType& vec) { 
        return kronecker_product
               <liner_map
                <conv_one , conv_neg ,
                 conv_zero, conv_one >>(vec);
    }

    template<class VecType>
    static auto or_map (VecType& vec) { 
        return kronecker_product
               <liner_map
                <conv_one , conv_zero,
                 conv_one , conv_one >>(vec);
    }
    template<class VecType>
    static auto or_map_inv (VecType& vec) { 
        return kronecker_product
               <liner_map
                <conv_one , conv_zero,
                 conv_neg , conv_one >>(vec);
    }

    template<class VecType>
    static auto xor_map (VecType& vec) { 
        return kronecker_product
               <liner_map
                <conv_one , conv_one ,
                 conv_one , conv_neg >>(vec);
    }
    template<class VecType>
    static auto xor_map_inv (VecType& vec) { 
        auto ret = xor_map(vec);
        for(auto &&i : ret) {
            i /= vec.size();
        }
        return ret;
    }

    template<Vec (*Transform)(const Vec&),
             Vec (*Inverse)  (const Vec&)>
    static auto convolution (const Vec &a,
                             const Vec &b) {
        auto vec_size = a.size();
        auto &&transa = Transform(a),
             &&transb = Transform(b);
        for(conv_size_type i = 0; i < vec_size; i++) {
            transa[i] *= transb[i];
        }
        return Inverse(transa);
    }

    public:

    static auto and_convolution(const Vec&a, const Vec&b) {
        return convolution<and_map, and_map_inv>(a, b);
    }
    static auto xor_convolution(const Vec&a, const Vec&b) {
        return convolution<xor_map, xor_map_inv>(a, b);
    }
    static auto or_convolution(const Vec&a, const Vec&b) {
        return convolution<or_map, or_map_inv>(a, b);
    }
};

Library Checkerへの提出 - Bitwise And Convolution

Library Checkerへの提出 - Bitwise Xor Convolution

最後に

最後の方は少し雑になってしましましたが、ここまで読んでいただきありがとうございました。

今後も解説記事の少ない高度典型を理解した場合は何かしら書くかもしれません。*6

この記事に限らず記事中にミスを見つけた場合や、質問等があればご連絡ください。

参考資料

アダマール変換 - Wikipedia

クロネッカー積 - Wikipedia

アダマール変換, 高速 Walsh-Hadamard 変換, xor-畳み込み

更新履歴

2021/11/20更新 実装例に問題例のリンクなどを追記

2022/02/26更新 tokusakurai 氏からの指摘により一部追記、修正

2022/09/06更新 誤植を修正

*1:各bitごとに考えればいいです

*2:問題例 :https://yukicoder.me/problems/no/1753

*3:気持ちとしては (G_n)_i,j において i の k bit目が 1 なら j の k bit目も1です。

*4:これはメビウス変換だかゼータ変換だかと類似の変換となります。

*5:テンプレートを多用したためです

*6:今回で筆が遅いことを自覚したのであまりたくさんはできない気がしますが

AtCoder Beginner Contest 197（Sponsored by Panasonic）

atcoder.jp

46:42全完ノーペナで46位でした。 久しぶりにノーペナで終えれて嬉しかったです。

A - Rotate

文字列を扱うのはC++よりPythonの方が簡単なのでPythonで実装しました。提出欄直打ちでACしました。

B - Visibility

Bにしては難しい気がします？ $(X, Y)$から上下左右に#が出てくるまで１文字ずつ見ていけばいいです。少し実装に手間取ったので他の人のコードを参考にしたいところです。

C - ORXOR

ぱっと見難しそうですが制約が$N \le 20$と小さいので、bit全探索すればいいです。 より具体的には$N-1$桁の2進数のbitが立っているところと区間の切れ目を対応させて区間の切り方を全探索します。 区間の切り方を決め打ったときに値がどうなるかは$\Theta(N)$で求められ、区間の切り方は$2^{N-1}$通りあるので全体で計算量は$\Theta(N2^{N})$になります。

D - Opposite

まず考察です。$(x_0, y_0)$と$(x_{\frac{N}{2}}, y_{\frac{N}{2}})$を結ぶ直線は正$N$角形の中心を通ります。このことから$(x_0, y_0)$と$(x_{\frac{N}{2}}, y_{\frac{N}{2}})$の中点$((x_0+x_{\frac{N}{2}})/2, (y_0+y_{\frac{N}{2}})/2)$が正$N$角形の中心だと分かります。あとは、この点を中心として$(x_0, y_0)$を$\frac{2\pi}{N}$だけ回転移動させれば$(x_1, y_1)$を求めることができます。

実装ですが、点の回転移動は複素数を使うと便利です。C++だと標準ライブラリにstd::complex<T>があるのでそれを使うとよいと思います。また、点の回転移動にはstd::polarを使うとよいです。

complex - cpprefjp C++日本語リファレンス

polar - cpprefjp C++日本語リファレンス

E - Traveler

個人的には少し難しいと感じたのに、かなり通されててびっくりしました。

全体の順番としては色の番号が小さい順に取ることしかできないので同じ番号のボールを取る順番を考えます。 よく考えると、最適に動いたとき同じ番号のボールの中で最後に取るのは、同じ番号のボールだけを見たときの両端のボールのどちらかであることが分かります。なぜなら、両端のボールのどちらも取ったときその間にあるボールはすべて回収できているはずだからです。

以上の考察により、各番号について、最後に左端と右端のボールそれぞれをとった場合の最小移動回数を求めていくdpで答えが求められます。

F - Construct a Palindrome

これもそこそこ難しいと思ったんだけど、結構通されてますね...

上手く状態を定義してあげてそれを頂点とした新しい有向グラフを作ります。

状態$v(a, b)$を「頂点$1$から頂点$a$へのパスと頂点$N$から頂点$b$のパスで、それらのパスによって得られる文字列が一致するものが存在する」と定義します。このとき、$v(a, b)$から$v(c, d)$への有向辺が存在する条件は「頂点$a$から頂点$c$を結ぶ辺と頂点$b$から頂点$d$を結ぶ辺で書かれた文字が同じものが存在する」ことです。

このとき$d(0, N)$から$d(N, 0)$へのパスが存在すれば所望の回文が存在することになります。また、辺を１つ通ることは文字を１つ追加することに相当するので距離が回文の最短長になります。嘘でした。解説と同じように偶数か奇数かで場合分けすれば良さそうです。

実際に辺を張るのは同じ文字の辺をまとめて処理することで$O(M^2)$、$d(0, N)$から$d(N, 0)$へのパスの最短長を求めるのは$O(N^2)$で可能です。(新しく作ったグラフ頂点数は$N^2$なので)したがって、全体で$O(M^2+N^2)$でこの問題を解くことができました。

FFC001

mario.exout.net

解説は書く気力がないから感想だけ． fastestを取りたかったので後ろから見ていった．

Fを見る．むずい何もわからないので5分くらいで切り上げてに行く．

Eは問題の理解に少し時間がかかる．全域木だね，gcd見ればよさそうだねですぐ解ける．

D．方針はすぐに見えるがDPを合わせるのが難しい．途中でFとmodが違うのに気づくが合わない．こういう時は深呼吸して．．．も合わないが，突然合ってACする．

C．むずい．いろいろ考えてなぜか木の直径-1をひねり出す．WAが出てやっと葉以外に操作をするだけだと気づく．コーナーケースに気が付いていただけにもったいない．

なんとなくAに行く．ギャグっぽいなと思いつつ分からないのでBに行く．Wavelet Tree作りたいなと思いつつ簡単枠なので適当に実装してAC．

Aをちょっと考えると対称な位置を選ぶのが強そう．よっぱりギャグだった．ヒカルの碁を思い出した．

残り50分ぐらいFに費やす．そもそも期待値DPが苦手すぎるのでやり方を調べたりしていた．これを思い出して銀冠レベルか？と思ったけどさすがに違った．副産物としてこっちの方のとっかかりがつかめたかもしれないので後からじっくり考えたい．

分割数が小さいのが意外だった．Wikipediaに漸近式として， $$\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{\frac{2n}{3}}}$$ が乗ってた．やば．

面白かったです．次回があるのかわかりませんがふもふも君がWriterのコンテストには積極的に出たいなと思いました．

ABC196

AtCoder Beginner Contest 196 - AtCoder

全完3ぺナ127位でした。全体的に難しいと感じました。 最初Dに30分以上書けたあげくWAが出たときは焦りましたが何とか全完することができました。

A - Difference Max

を最大化するにははできるだけ大きく、をできるだけ小さくしたいです。は今独立に選べるのでの最大、の最小を選べばよく、すなわち答えはとなります。

B - Round Down

が非常に大きい可能性があるので、浮動小数点数で扱うと丸め誤差によって正確な処理ができません。 したがって、まず文字列として入力を受け取るとよいです。 小数点以下を切り捨てるので.より左の文字列を出力すればいいです。 C++で実装する場合は１文字ずつなめるのがやりやすいと思います。

C - Doubled

の前半と後半の文字列を整数として見たものとするとの桁数はの半分です。ここで制約をみると、が高々12桁の整数なので は高々6桁です。したがって、を以上未満の範囲で全探索してあげればいいです。これは十分高速ですが、を文字列として2つ繋げた後、整数とみたものをとするとは単調増加なので二分探索を使えばより高速解くことができます。

1WAしましたがこれは探索範囲をまでにしていました。

D - Hanjo

難しかったです。

制約がと小さいので全探索できそうです。 まず、の畳がおければ（中途半端な置き方をしない限り）残りのマスにの畳は一意に置き方が決まるのでの畳だけ考えればいいです。更に、

• 各マスについて下方向への畳を置く
• 右方向への畳を置く
• 何もしない

の３通りの操作を考えればの畳の置き方を全部調べられるので、この操作の仕方を右上から適当な順序で全探索していけばいいです。 計算量はですが実際は枝刈りが入るためこれよりかなり高速です。

1WAしましたがこれはとを取り違えてました。

E - Filters

個人的に今回のコンテストで最難に感じました。

と定義します。 手元でいろいろ実験してみると は必ず以下の形で表わされることが分かります。 $$ \begin{align} g_i(x) = \begin{cases} L_i + b_i & (x\le L_i) \\ x + b_i & (L_i \le x \le R_i) \\ R_i + b & (R_i\le x) \end{cases} \end{align}$$

ここで$b_i$は整数で、$L_i, R_i$は整数もしくは$\infty, -\infty$であり$L\le R$とします。 グラフに書くと大体こんな感じです。（水平線の部分がない場合や、斜め線の部分がない場合があることに注意してください。） 証明は数学的帰納法でよいでしょう。証明のポイントとしては$g_i(x)$が単調増加であることを使うと見通しがよいです。

このことを踏まえると、$L_0 = -\infty, R_0 = \infty, b_0 = 0$として$L_i, R_i, b_i$を順に計算していくとよいことが分かります。 具体的には$t_{i+1} = 1$のとき、$L_{i+1} = L_i, R_{i+1} = R_i, b_{i+1} = b_i + a_i$、$t_{i+1} = 2, 3$のとき$L_{i+1} = f_{i+1}(L_i + b_i) - b_i, R_{i+1} = f_{i+1}(R_i + b_i) - b_i, b_{i+1} = b_i$となります。

よって、$L_N, R_N, b_N$を$\Theta(N)$で計算できたので$g_N(x)$を$\Theta(1)$でもとめられるようになり、全体で$\Theta(N+Q)$でこの問題を解くことができました。

SegTree beatというデータ構造を使うとライブラリをはるだけの問題になるそうです。

F - Substring 2

排他的論理和を使うと問題を簡単に記述できます。 求めるべきは $$\min_{0\le i < |S|-|T|}\left\lbrace\sum_{j = 0}^{|S|-1}{S_i\oplus T_{i+j}}\right\rbrace$$ です。 なんか見覚えのある形になりそうです。 ここで$S$を反転してあげると $$ \min_{0\le i < |S|-|T|}\left\lbrace\sum_{j = 0}^{|T|-1}{S_{|S|-j-1}\oplus T_{i+j}}\right\rbrace = \\ \min_{0\le k < |S|-|T|}\left\lbrace\sum_{i+j = |S|-1, 0\le i, 0\le j}^{}{S_{i}\oplus T_{j+k}}\right\rbrace $$ 畳み込みの形になりました。これを高速に計算できればこの問題は解けることになります。

さて、排他的論理和が普通のかけ算なら畳み込みはFFTというアルゴリズムを用いて$O(NlogN)$（配列の長さを$N$とする）で計算できます。排他的論理和をそのままではFFTに持ち込めませんが、$a^2 = b^2 \neq ab $を満たすような$a, b$が存在するとそれぞれ1と0に対応づけることで排他的論理和での畳み込みを一回のFFTで計算できます。（FFTをした後に連立方程式を解けばよいです）実は$a = 1, b = -1$とすると上の式は満たされるのでこの問題を解くことができました。

WBC004

mario.exout.net

全完2位でした。今までで一番難しかった。

A. 79Gold

なんかタイトルが動いて笑った。解法は全体の3割が何人かを計算して、はい。

B. Linear Code

奇跡的に線形符号の性質を知っていた。 答えはだが、線形符号であるという性質を使うとなので、に注意して、求めるべきは。*1

ここまではよかったが、popcountを求めるときに__builtin_popcountllでなく__builtin_popcountを使って1WA。

なんか202点とれるらしい。（競プロ中に謎解きを始めるな）

C. Blurred Numbers

正規表現が読めるなら正規表現を見た方がわかりやすいかも。 1000の位、100の位、10の位、1の位がどこで区切られるかを全探索する。 各位は空文字列でもいいことに注意。 最初?がI, V, X, L, C, D, M以外になることはあるかのclarを送ろうとしたけど調べたら、そもそもローマ数字は基本3999までらしい。

D. Photosynthesis

光合成をするのに必要なコストは初めに各からを引いておけばいい。 これによって、を含む区間で、その和が最大のものが求める問題になるが、これは累積和を使ってで処理できる。

...がデバック出力消し忘れ+オーバーフローで4WA...

E. Link

見た目がごついが、よーく見るとギャグ。

制約から最初の状態はある１つの連結成分に含まれるノード以外はすべて次数は0。 このことに気をつけると帰納的に、すべてのタイミングである１つの連結成分に含まれるノード以外はすべて次数は0で、追加されるリンクに繋がるノードのうち片方は必ずその連結成分に含まれるノード、もう片方は等確率で選ばれたノードであることが分かる。 よって、最初の状態の連結成分のサイズが分かれば、時刻にネットワークが連結である確率がdpで計算できる。() したがって、最初の状態での連結成分の大きさごとの場合の数が分かればよく、これは連結成分の大きさをとして、で計算できる。（自由に割り当てられるリンクが個、割り当てる場所が個なので）

計算量は

F. Maximum Flaw Problem

まず、条件を満たす流れ方が存在するかを考える。 1番目のタンクから考えるとすぐ次のタンクには流せるだけ流す必要があり、余った分も可能な限り他のタンクに回せばいい。 このことを踏まえて、割れ目が最大になるようなタンクとその流出量を決め打つと、決め打ったタンクについてのみ流出量を減らして上と同じようにすればそれが実現可能かどうか判定できることが分かる。 これをすべてのタンクについて二分探索すれば、計算量はで十分高速となる。

全体を通しての感想

どれもなかなか歯ごたえがあって面白かった。WBC005も期待しています！

あとブログ書くのってとても疲れる...

*1:証明が不十分ですが気持ちだけ。あとは0000......0が必ず含まれるので...という感じです