leaf1415の日記

競技プログラミングに関することを書きます

【色変記事】レッドコーダーになりました！

2023年9月8日の World Tour Finals 2022 Day1（Open Contest）をもちまして、レートが赤に突入しました！！！

のでいっぱい自分語りして気持ちよくなります。

1年目

2017春 競プロに出会う

大学で競プロをやる授業があったのをきっかけに競プロに遭遇。

形式こそはコンテストであったものの、授業なのでそんなに難しい問題は出ません。

が、授業で最難レベルの問題「各マスが白か黒で塗られたグリッドの黒い連結成分の個数を数えよ」は当時の自分には歯応えのある難易度でした。

国際大学対抗プログラミングコンテスト（ICPC）というものがあるというのを多分授業で教えてもらって、過去問が難易度別にまとめられたサイトを見つけました。

aoj-icpc.ichyo.jp

グリッドの黒い連結成分を数える問題はどれくらいの難易度かなと調べたら、100〜1200の難易度評価のうちなんと150しかなく、じゃあ400~500くらいはどれくらいかと見てみます。

「500円玉貯金」

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1603&lang=jp

全探索くらいは書く能があったので書いて提出しますが、当然(?)にもTLE。こんなのどうしたらいいんやという感じですが、「動的計画法」でこれは解けるらしい。

「ダルマ落とし」

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp

こんなもん解けるわけ………ホンマや！（出っ歯）

世の中には僕の知らない難しい問題がいっぱいあって、どうやっても不可能にしか見えない問題が、解説を見たら魔法みたいなカッコいい方法で解けるのに魅了され少しずつハマっていったのです。

チーター本を読む

「最強最速アルゴリズマー養成講座」、いわゆるチーター本が大学図書館にあったので借りて読みます。トップクラスのプレイヤーはレッドコーダー（←後に私がなるやつ）と呼ばれて恐れられている(?)らしい。レッドコーダーというのはとにかくすごいらしい（←後に私がなるやつ）。

本で紹介されていたTopCoderに登録するも環境の都合か重くてストレスフルだったのですが、そういえば友人のT君がAtCoderというのをやってたなあというのを思い出して登録します。

AtCoder始める

2017年6月3日「AtCoder Regular Contest 075」に初めて参加。

当時は、ABCとARCが同時開催で、ABCがA,B,C,D問題を、ARCがC,D,E,F問題をカバーする形式でした。結果はCの1完。

ICPC2017国内予選

友人のT君、H君とICPC2017国内予選にチームtojimboで参加。

結果は1人1問ずつ解いて3完。Cまでは実装さえできれば良いもののDからは計算量を意識する必要があって難しい。3人にコンピュータ1台というのも結構大変。

予選通過はなりませんでした。

蟻本購入

2017年7月24日にAmazonで蟻本が届きました。

ここから8ヶ月くらいかけてゆっくり読んでいきます。初級編でも1回読んだだけではわからないところも結構あったのですが、周回するごとにわかるようになっていき、読むたびに発見がある本です。（たぶんいま読み返してもまだまだたくさん勉強になりそう）

コンテストの際は近くに置いておいて、考察の際にパラパラめくってはこの世にはどんなアルゴリズムがあったっけなと参考にしてました。

CODE FESTIVAL 2017 qual A 通過

2017年9月23日 CODE FESTIVAL 2017 qual A

なんか予選に通過したら東京の本戦に招待されるらしい。

問題との相性に恵まれ僕だけが解ける天才パズルが出てなんと通過！

しれっと入青

DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選通過

2017年10月7日に参加した「DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選」に通過！！

のはずが、通過メールがGmailのプロモーションのカテゴリに入っていたのに気づいた時には返信期限を過ぎていました。うんち。

入黄

2017年11月11日 人知れず入黄

CODE FESTIVAL 2017 本戦

2017年11月25日秋葉原UDX(?)みたいなとこで本戦！

日本人80人と海外勢20人の計100人で1泊2日で競プロづくしをやるすごいイベント

結果は惜しくも98位

chokudaiさんによる各問題の生解説があり、1000点問題とかの解説を聞いて、これが1000点問題かすげ〜〜〜ってなった記憶。

他にもトッププレイヤー同士のエキシビションマッチや、チーム対抗リレーなどいろんなコンテンツがあって、交通費と宿も提供してもらえてすごい贅沢。

集合写真を撮る際にtouristの半径50cm内に接近するという実績解除（いま思えばおしりくらい触っておけばよかった）

 Codeforcesを始める

ちょうどAtCoderに登録した頃はARC/AGCが割と高頻度で開催されていたのですが、間もなく月1回ペースとかになり、ratedが足りない！！！という気持ちに耐えられずCodeforcesとかいうのを始めました。

2017年12月11日にCodeforces Round 450 (Div. 2)に初参加。

2回目に出たEducational Codeforces Round 34 (Rated for Div. 2)では想定解が64ビット整数に収まらずhack祭りに見舞われ教育される。

2年目

このあたりの時期は、AtCoder Scoresの問題を配点が小さい方から順に埋めていってました。

ICPC 2018 国内予選

前年と同じくT君、H君とチームtojimboでICPC国内予選にリベンジします。

例のごとく1人1問ずつ解いたあとDに挑むも間に合わず…

またしても予選敗退でめちゃくちゃ悔しいという気持ちに

ICPC 2018 横浜大会

と思いきや、後に参加辞退したチームの補欠枠が降りてきてなんとICPC横浜大会に行けることに。2018年12月8日〜10日に横浜産貿ホール(?)みたいなとこでやります。

日本人同士での会話も含め会場内での公用語は英語。何言ってるかよくわからないのでとりあえずうなずいておきます。

初日は説明とリハーサルコンテストで本番のコンテストは2日目にお預け。早く本番やりたくてじれったい気持ちに。

本番は9時〜14時の5h。いつもとキー配列が違うのが最大の敵で、その影響で、タイピングと全く関係ない考察パートとかでもなぜか頭が混乱します。

3日目は東京をうろうろして、帰りは3人で高速バスで帰ったのですが、静電気恐怖症なので、バスのUSB端子(?)みたいなところからくる静電気に怯えてまともに眠れず、来年は一人で新幹線で帰ろうと心に決めました。

Twitterアカウント作成

競プロ界隈はtwitterでかなり情報共有とかされているので、2019年1月2日にtwitterアカウント「りーふ@競プロ」を作りました。

その結果、同学の後輩にあたる競プロerのs君、e君に認識してもらえます。

全国統一プログラミング王決定戦本戦

の懇親会でtwitterで事前に連絡を取っていたs君、e君と初めてエンカ！いつも同じ大学に通ってるのになぜか東京で初遭遇。

翌日が卒論の提出日でしたが、元から締め切りが1日早かったことにするテクを使ったので問題ありませんでした。

3年目

その後、僕の研究室にe君とその友人のn君が入ってきてくれました！！

これまで1人で競プロしてきたので、学内で共有できる仲間が増えてこの年あたりからモチベがかなり上がっていきました。

一緒にクリスマスコンに参加したりたこ焼きを焼きながらバチャをする謎の遊びをしました。

精進としてはAtCoder Problemsを片っ端から埋めていったり、Recommendationの問題を解いていきました。

ICPC2019国内予選通過

2019年7月12日 ICPC2019国内予選があったのですが、残念ながら学会発表が被っており、ボスには一人でフランスに行ってもらいました。

例年通りにT君、H君とチームtojimboで参加。

参加資格上この年が最後のチャンスで、結局4完の壁が破れなかった点は悔しかったのですが、3完早解きで今回は順当に予選通過！！

ICPC2019 横浜大会

4完24位でした！！

入橙

2020年1月11日入橙！！！

4年目

2020年の4月から学科に競プロerのi君が入ってきてくれて弊学の競プロコミュニティのメンバーが1人増えました！図書館でi君っぽい人に話しかけたらi君でした！！

クリスマスコンではそのとき始めて遭遇した同学科のc君と、s君、i君との4人で参加して撃沈

こ。この頃に、JOI埋めに手を出してみましたが、なんか問題傾向がしんどくて続きませんでした。友人（競プロerではない）からやっぱそういうのは実戦形式でやらんと〜と言われてたしかにとなったので、2020年11月〜2021年7月にかけてこどふぉのばちゃを毎日1バチャずつくらいやりました。上達した実感とかはよくわからなかったんですが、現象としてはレートが上がっていった気がします。

Yukicoderで単独writerのコンテスト

天才コンを作りました

yukicoder.me

5年目

ABCのwriterになれるチャンス

2021年3月20日、chokudaiさんがtwitterでABCのwriterやりたい人を募集していたのですかさずDM！

こんな感じの内容ですがどうでしょう？！と説明をもらいましたが、ABCには直接writerをしてない回でも参加出来なくなるというのにちょっと尻込みしてしまい、やります！と返信するのが1日後になった結果、既に枠が埋まってしまいました

（多分こいつのせい↓↓）

ICPC2021 国内予選

2021年11月5日 ICPC2021国内予選は学生コーチとして、このとき初めて会うm君と、s君、c君のチームを応援。

そして弊学初の4完を達成して予選通過してくれました！！

コロナの影響でオンサイトにはならず横浜に行けなかったのだけが惜しかった

ABC writerデビュー

もう1度声をかけてもらう機会があったので今度こそwriterとしてすぐに名乗りを上げました。その後、

「原案作りたいです！」

「わかりました試しに送ってみてください」

（原案いろいろ送る）

「…どうしても原案やりたいですか…？？」

「そこをなんとか〜（泣）」

そしてついに、

その後ABCに賞金付きコンテストが増え始める

許せね〜

 

その後、同学の競プロerで以前からtwitter上で相互に認識していたt君ともエンカ！！

6年目

7年目

CodeChefを始める

精進ペースが落ち気味になったので、以前から気になりつつもやってなかったCodeChefに参加する習慣をつけてみました。

AGCのwriterデビュー

ARC用に投げていた原案が昇華してAGCに！

1700点とかもはや未知の領域だったので、これくらいの難易度感なのか〜と勉強になりました。それと報sy

レッドコーダーになる

そしてついに

6年ちょいかけてレッドコーダーになりました！！！！

今後

がんばります。

〇〇変換を使って畳みこみができる仕組み、完全に理解した

競技プログラミングでは、フーリエ変換やゼータ変換などを使って畳みこみの計算を行うことがしばしばありますが、こういった○○変換で畳みこみの計算ができる直感的なお気持ちを最近ようやくわかった気になったので、その勝手な解釈を文章にまとめました。
読みにくいところやいい加減なところがありますが、ご容赦ください。

畳みこみについて

集合 \lbrace 0, 1, 2, \ldots, N-1\rbrace 上の 2 項演算 \circ があって、
与えられた 2 つの N 次元ベクトル \mathbf{a} = (a_0, a_1, \ldots, a_{N-1})^{T}, \mathbf{b} = (b_0, b_1, \ldots, b_{N-1})^{T} から、c_k= \sum_{k = i \circ j} a_i b_j となる新たな N 次元ベクトル \mathbf{c} = (c_0, c_1, \ldots, c_{N-1})^{T} を作る操作を、ここでは「畳みこみ」と呼び、 \mathbf{c} = \mathbf{a} \ast \mathbf{b} で表します。

演算 \circ として、

  • x \circ y := (x+y)\bmod N
  • x \circ y := x \& y
  • x \circ y := x | y
  • x \circ y := x \oplus y
  • x \circ y := \gcd(x, y)

などの場合が競プロにしばしば登場します。
ただし、\& はbitwise-AND、| はbitwise-OR、\oplus はbitwise-XORを表します。

x \circ y := (x+y)\bmod N の場合は、 \mathbf{a} \ast \mathbf{b} を次の手順で計算できます。

  1. まず、\mathbf{a} と \mathbf{b} それぞれに離散フーリエ変換を行って、2 つの N 次元ベクトル \mathbf{\hat{a}}, \mathbf{\hat{b}} を得ます。
  2. 次に、\mathbf{\hat{a}} と \mathbf{\hat{b}} の各点積、つまり、 \mathbf{\hat{a}} \odot \mathbf{\hat{b}} := (a_0 b_0, a_1 b_1, \ldots, a_{N-1} b_{N-1})^{T} を計算します。
  3. 最後に、\mathbf{\hat{a}} \odot \mathbf{\hat{b}} に逆離散フーリエ変換を行うと、 \mathbf{a} \ast \mathbf{b} が得られます。

演算 \circ が他の定義の場合の例をいくつか挙げます。

  • x \circ y := x | yの場合は、\mathbf{a} と \mathbf{b} のそれぞれにゼータ変換を行ったものどうしの各点積を計算し、それにゼータ変換の逆変換であるメビウス変換を行うことで得られます。 x \circ y := x \& y の場合もほぼ同様です。
  • x \circ y := x \oplus y の場合は、\mathbf{a} と \mathbf{b} のそれぞれにアダマール変換を行ったものどうしの各点積を計算し、それに逆変換を行うことで得られます。
  • x \circ y := \gcd(x, y) の場合は、\mathbf{a} と \mathbf{b} のそれぞれに約数系ゼータ変換（競プロ界隈の呼称？）を行ったものどうしの各点積を計算し、それに逆変換である約数系メビウス変換を行うことで得られます。

この記事のテーマ

  1. 上に述べた畳みこみの計算方法はすべて、「〇〇変換を行ったものどうしの各点積に逆〇〇変換を行う」という形になってるけど、なんで全部そういう形になるんだろう？
  2. そもそも、なんで〇〇変換を使うと畳み込みの計算が出来るの？（数式で証明を見たら確かにそうなるのはわかるけど、もっと直感的なお気持ちが知りたい！）

↑これらは数ヶ月前の僕の疑問です。

畳みこみの別の捉え方

畳みこみは「半群代数上の積」と捉えることが出来ることが、こちらのmaspyさんの記事で触れられています。（わかりやすくてとても勉強になります）
[数学] 畳み込み入門：Dirichlet積とゼータ変換・メビウス変換 | maspyのHPmaspypy.com

以降の話に必要なところだけを大まかに述べると次の通りです。
集合 \lbrace 0, 1, \ldots, N-1\rbrace の各要素に対応する \lbrack 0\rbrack, \lbrack 1\rbrack, \ldots, \lbrack N-1\rbrack という N 個の"モノ"を準備します。そして、N 次元ベクトル \mathbf{a} = (a_0, a_1, \ldots, a_{N-1})^{T} を、 \sum_{i = 0}^{N-1} a_i \lbrack i \rbrack = a_0 \lbrack 0 \rbrack + a_1 \lbrack 1 \rbrack + \cdots + a_{N-1} \lbrack N-1 \rbrack という N 個の"モノ"の形式的な線形和で表すことを考えます。ここでは、この \sum_{i = 0}^{N-1} a_i \lbrack i \rbrack を \mathbf{a} の「線形和表現」と呼ぶことにします。
また、\lbrack i \rbrack と \lbrack j \rbrack の積を \lbrack i \rbrack \lbrack j \rbrack = \lbrack i \circ j \rbrack と定めます。
このとき、\mathbf{a} の線形和表現 \sum_{i = 0}^{N-1} a_i \lbrack i \rbrackと \mathbf{b} の線形和表現 e\sum_{i = 0}^{N-1} b_i \lbrack i \rbrack の積 (\sum_{i = 0}^{N-1} a_i \lbrack i \rbrack)(\sum_{i = 0}^{N-1} b_i \lbrack i \rbrack) を計算すると、 \mathbf{a} \ast \mathbf{b} の線形和表現が得られます。

例えば、N = 3 で x \circ y := (x+y) \bmod 3 の場合を考えます。
\mathbf{a} = (a_0, a_1, a_2) と \mathbf{b} = (b_0, b_1, b_2) を、それぞれ (a_0\lbrack 0 \rbrack + a_1\lbrack 1 \rbrack + a_2\lbrack 2 \rbrack) および (b_0\lbrack 0 \rbrack + b_1\lbrack 1 \rbrack + b_2\lbrack 2 \rbrack) のように線形和表現に変換し、それらの積を計算してみます。\lbrack i \rbrack と \lbrack j \rbrack の積を \lbrack i \rbrack \lbrack j \rbrack = \lbrack i \circ j \rbrack で計算することに注意すると、
(a_0 \lbrack 0 \rbrack + a_1\lbrack 1 \rbrack + a_2\lbrack 2 \rbrack) (b_0\lbrack 0 \rbrack + b_1\lbrack 1 \rbrack + b_2\lbrack 2 \rbrack) \\ = a_0b_0 \lbrack 0 \rbrack \lbrack 0 \rbrack + a_0b_1 \lbrack 0 \rbrack \lbrack 1 \rbrack + a_0b_2 \lbrack 0 \rbrack \lbrack 2 \rbrack + a_1b_0 \lbrack 1 \rbrack \lbrack 0 \rbrack + a_1b_1 \lbrack 1 \rbrack \lbrack 1 \rbrack + a_1b_2\lbrack 1 \rbrack \lbrack 2 \rbrack + a_2b_0 \lbrack 2 \rbrack \lbrack 0 \rbrack + a_2b_1 \lbrack 2 \rbrack \lbrack 1 \rbrack + a_2b_2 \lbrack 2 \rbrack \lbrack 2 \rbrack \\ = a_0b_0 \lbrack 0 \circ 0 \rbrack + a_0b_1 \lbrack 0 \circ 1 \rbrack + a_0b_2 \lbrack 0 \circ 2 \rbrack + a_1b_0 \lbrack 1 \circ 0 \rbrack + a_1b_1 \lbrack 1 \circ 1 \rbrack + a_1b_2 \lbrack 1 \circ 2 \rbrack + a_2b_0 \lbrack 2 \circ 0 \rbrack + a_2b_1 \lbrack 2\circ 1 \rbrack +a_2b_2 \lbrack 2 \circ 2 \rbrack\\ = a_0b_0 \lbrack 0 \rbrack + a_0b_1 \lbrack 1 \rbrack + a_0b_2 \lbrack 2 \rbrack + a_1b_0 \lbrack 1 \rbrack + a_1b_1 \lbrack 2 \rbrack + a_1b_2 \lbrack 0 \rbrack + a_2b_0 \lbrack 2 \rbrack + a_2b_1 \lbrack 0 \rbrack + a_2b_2 \lbrack 1 \rbrack\\ = (a_0b_0 + a_1b_2 + a_2b_1) \lbrack 0 \rbrack + (a_0b_1 + a_1b_0 + a_2b_2) \lbrack 1 \rbrack + (a_0b_2 + a_1b_1 + a_2b_0) \lbrack 2 \rbrack
となり、これが \mathbf{a} \ast \mathbf{b} の線形和表現と一致しています。\mathbf{a} \ast \mathbf{b} := (a_0b_0 + a_1b_2 + a_2b_1, a_0b_1 + a_1b_0 + a_2b_2, a_0b_2 + a_1b_1 + a_2b_0) である事に注意してください。

一般に、\mathbf{a} と \mathbf{b} をぞれぞれ線形和表現に変換し、その積を計算すると、
(\displaystyle\sum_{i = 0}^{N-1} a_i \lbrack i \rbrack)(\displaystyle\sum_{i = 0}^{N-1} b_i \lbrack i \rbrack) \\ = \displaystyle\sum_{i = 0}^{N-1}\displaystyle\sum_{j = 0}^{N-1} a_i b_j \lbrack i \rbrack \lbrack j \rbrack \\ = \displaystyle\sum_{i = 0}^{N-1}\displaystyle\sum_{j = 0}^{N-1} a_i b_j \lbrack i \circ j \rbrack \\ = \displaystyle\sum_{k = 0}^{N-1} (\displaystyle\sum_{i \circ j = k} a_i b_j) \lbrack k \rbrack
となり、\mathbf{a} \ast \mathbf{b} の線形和表現と一致します。

よって、\mathbf{a} と \mathbf{b} から \mathbf{a} \ast \mathbf{b} を求めるには下記の手順を行えばよいです。

  1. まず、\mathbf{a} \rightarrow \sum_{i = 0}^{N-1} a_i \lbrack i \rbrack, \mathbf{b} \rightarrow \sum_{i = 0}^{N-1} b_i \lbrack i \rbrackとそれぞれ線形和表現に変換します。
  2. 次に、それらの積 (\sum_{i = 0}^{N-1} a_i \lbrack i \rbrack) (\sum_{i = 0}^{N-1} b_i \lbrack i \rbrack) を計算し、得られた積を \sum_{i = 0}^{N-1} c_i \lbrack i \rbrack とします。
  3. 線形和表現 \sum_{i = 0}^{N-1} c_i \lbrack i \rbrack から ベクトル \mathbf{c} = (c_0, c_1, \ldots, c_{N-1}) を復元します。このとき、\mathbf{c} = \mathbf{a} \ast \mathbf{b} となっています。

〇〇変換で畳み込みをするアイデア

〇〇変換で畳み込みをすることの主たるアイデアは、 \lbrack 0\rbrack, \lbrack 1\rbrack, \ldots, \lbrack N-1\rbrack を N 本の複素ベクトル \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} で代用することです。そして、 \lbrack i\rbrack と \lbrack j\rbrack の積 \lbrack i\rbrack \lbrack j\rbrack の計算を、
\mathbf{v}_i \odot \mathbf{v}_j という各点積の計算に置き換えます。

下記の 2 つの条件をともに満たすように、 N 本の N 次元複素縦ベクトル \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を選びます。

  • i \circ j = k \Rightarrow \mathbf{v}_i \odot \mathbf{v}_j = \mathbf{v}_k が任意の 0 \leq i, j \leq N-1 に対して成り立つ。
  • \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} は線形独立である。

これらの N 本のベクトル \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を \lbrack 0\rbrack, \lbrack 1\rbrack, \ldots, \lbrack N-1\rbrack の代わりに用いると、\mathbf{a} と \mathbf{b} から \mathbf{a} \ast \mathbf{b} を求めるには次の手順を行えばよいです。

  1. まず、\mathbf{a} \rightarrow \sum_{i = 0}^{N-1} a_i \mathbf{v}_i, \mathbf{b} \rightarrow \sum_{i = 0}^{N-1} b_i \mathbf{v}_i の形にそれぞれ変換し、
  2. それらの各点積 (\sum_{i = 0}^{N-1} a_i \mathbf{v}_i) \odot (\sum_{i = 0}^{N-1} b_i \mathbf{v}_i) を計算します。このとき、得られた積が \sum_{i = 0}^{N-1} c_i \mathbf{v}_i の形で表せます。
  3. \sum_{i = 0}^{N-1} c_i \mathbf{v_i} \rightarrow \mathbf{c} = (c_0, c_1, \ldots, c_{N-1})^T と変換すると、 \mathbf{c} = \mathbf{a} \ast \mathbf{b} が成り立ちます。

上記の手順1. の変換 \mathbf{a} \rightarrow \sum_{i = 0}^{N-1} a_i \mathbf{v}_i は、
縦ベクトル \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を横に並べた行列 \mathbf{T} := (\mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1}) を用いれば、
\sum_{i = 0}^{N-1} a_i \mathbf{v}_i = \mathbf{T}\mathbf{a} と書けます。
上記の手順3. の変換 \sum_{i = 0}^{N-1} c_i \mathbf{v_i} \rightarrow \mathbf{c}には \mathbf{c} = \mathbf{T} ^{-1}(\sum_{i = 0}^{N-1} c_i \mathbf{v_i}) であることを用いればよいです。 \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を線形独立になるように選んだので、\mathbf{T} の逆行列は存在します。

結局、\mathbf{a} と \mathbf{b} から \mathbf{a} \ast \mathbf{b} を求めるには次の手順を行えばよいです。

  1. まず、\mathbf{a} と \mathbf{b} に変換行列 \mathbf{T} を左から掛けて、\mathbf{T}\mathbf{a} と \mathbf{T}\mathbf{b}を求めます。
  2. 次に、\mathbf{T}\mathbf{a} と \mathbf{T}\mathbf{b} の各点積 \mathbf{T}\mathbf{a} \odot \mathbf{T}\mathbf{b} を計算します。
  3. これに、変換行列 \mathbf{T} の逆行列 \mathbf{T}^{-1} を掛けると、 \mathbf{a} \ast \mathbf{b} が得られます。

実際、
\mathbf{T}\mathbf{a}\odot\mathbf{T}\mathbf{b}\\ =(\displaystyle\sum_{i = 0}^{N-1} a_i \mathbf{v}_i) \odot (\displaystyle\sum_{i = 0}^{N-1} b_i \mathbf{v}_i) \\ = \displaystyle\sum_{i = 0}^{N-1}\displaystyle\sum_{j = 0}^{N-1} a_i b_j (\mathbf{v}_i \odot \mathbf{v}_j) \\ = \displaystyle\sum_{i = 0}^{N-1}\displaystyle\sum_{j = 0}^{N-1} a_i b_j (\mathbf{v}_{i \circ j})\\ = \displaystyle\sum_{k = 0}^{N-1} (\displaystyle\sum_{i \circ j = k} a_i b_j) \mathbf{v}_k\\ = T(\mathbf{a} \ast \mathbf{b})
となります。

これで、いろんな畳み込みが「〇〇変換を行ったものどうしの各点積に逆〇〇変換を行う」という形で計算できる仕組みがわかりました。納得してください。

畳みこみの具体例

結局、演算 \circ の定義に応じて、変換行列 \mathbf{T}、すなわち N 本のベクトル \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を、

  • i \circ j = k \Rightarrow \mathbf{v}_i \odot \mathbf{v}_j = \mathbf{v}_k が任意の 0 \leq i, j \leq N-1 に対して成り立つ。
  • \mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} は線形独立である。

という 2つの条件をともに満たすように選べれば、「〇〇変換を行ったものどうしの各点積に逆〇〇変換を行う」方法で畳みこみの計算ができることになります。
いくつかの具体例を以下で挙げます。

x \circ y := (x + y) \bmod N の場合

\mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} として、
\mathbf{v}_i = (\omega^{0}, \omega^{i}, \omega^{2i}, \ldots, \omega^{(N-1)i})^T をとることができます。（ただし、 \omega := \exp(\frac{2\pi i}N)）
このとき、\mathbf{T} は離散フーリエ変換になっています。

x \circ y := x \oplus y の場合

\mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を次のように選ぶことができます。

  • \mathbf{v}_i = (v_{i, 0}, v_{i, 1}, \ldots, v_{i, N-1})^T を、v_{i, j} = (-1) ^ {\text{popcount}(i \& j)} と定める。

（ただし、\text{popcount}(x) は x の二進表示における 1 の個数を表します。）
このとき、\mathbf{T} はアダマール変換になっています。

x \circ y := x | y の場合

\mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を次のように選ぶことができます。

  • \mathbf{v}_i = (v_{i, 0}, v_{i, 1}, \ldots, v_{i, N-1})^T を、 i \& j = i のとき v_{i, j} = 1、そうでないとき v_{i, j} = 0 と定める。

このとき、\mathbf{T} はゼータ変換になっています。

x \circ y := \max(x, y) の場合

\mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_{N-1} を次のように選ぶことができます。

  • \mathbf{v}_i = (v_{i, 0}, v_{i, 1}, \ldots, v_{i, N-1})^T を、j \geq i のとき v_{i, j} = 1、j < i のとき v_{i, j} = 0 と定める。

変換 \mathbf{T} は累積和をとる操作になっています。

参考記事

[数学] 畳み込み入門：Dirichlet積とゼータ変換・メビウス変換 | maspyのHP

バグの記録

遭遇したバグの原因をここに列挙していきます。

増えてきたらそのうち整理します。

飽きました

 

・配列の長さが足りない

・与えられた N に対して、実際の数列の長さは 2N

・int型に収まらない入力をint型で受け取っている（以降の入力がおかしくなる）

・conitnue文で重要な更新処理をとばしている

・hとwが逆、xとyが逆

・非void型の関数が値を返していない（REになったりする）

・再帰が深すぎる（REになったりする）

・複数テストケースで、前のテストケースで使った変数を初期化してない

・sortの昇順と降順が間違っている

・配列の添え字の変数が違う（iとlを間違えたりする）

・>=と>を間違えてる

・浮動小数点数の計算誤差で落ちてる

・二分探索の上限値が足りてない