Universal Cup 3-27 A: (A + B) mod P
解法も面白かったし、背景も面白かった
問題
奇素数
- 任意の
に対し、0 \leq a,b < p としてv[d] := \max(A_a[d]+A_b[d],0) 次元ベクトルD を計算する。この時、v とv の内積が最も大きくなるB_k は ちょうど一つであり、それはk であるk = a+b \mod p -
でなければいけないD \leq 25
ちなみに元の問題文は機械学習の文脈で書いてあって、
アイデア
- 普通の
次元平面に、D = 2 と単位円上にプロットしてみることを考える。するとA_a = ( \cos(\frac{2\pi}{p} \cdot a), \sin(\frac{2\pi}{p} \cdot a) ) の方向は、円周上をA_a + A_b 個に分割した時の2p 番目の点c := (a+b)\%p 、あるいは真逆の点P_c := ( \cos(\frac{\pi}{p} \cdot c), \sin(\frac{\pi}{p} \cdot c) ) と同じ向きを向いているP_{c+p} - たとえば
として、p = 5 はA_1 + A_4 と同じ向きを向いている。P_0 = (1,0) は真逆であるA_2+A_3 の方を向いている。P_5 = (-1,0)
- たとえば
- なので、
とA_a + A_b の内積の最大値は、P_k , あるいはk = c のどちらかで取る、ということは言えるk = c + p - 内積の最大値で
なので|P_k|=1 の arg しか関係ないことに注意A_a+A_b -
奇数よりp と潰れることもないA_a + A_b = 0
- 内積の最大値で
- この二択をうまくひとつにまとめるために
の部分を使う\max(\cdot,0)
解法
実は
まず
A_a[0] := \cos(\frac{2\pi}{p} \cdot a) A_a[1] := \cos(\frac{2\pi}{p} \cdot a - \varphi) A_a[2] := -A_a[0] -
A_a[3] := -A_a[1]
と定義する。それぞれ をA_a 方向に射影した時の(符号付き)長さであることに注意。(1,0), (\cos \varphi, \sin \varphi), -(1,0), -(\cos \varphi, \sin \varphi)
B'_k[0] := |\cos(\frac{\pi}{p} \cdot k)| B'_k[1] := |\cos(\frac{\pi}{p} \cdot k - \varphi)| B'_k[2] := B'_k[0] B'_k[3] := B'_k[1] B_k := (B'_k の長さを 1 にしたやつ)
つまり、
これは長さ1のベクトルたち
(|cos t|,|cos(t-pi/3)|) のプロット。赤い点は (B'_k[0], B'_k[1]) たち。これを正規化してるので赤い点たちのargが一致しなければ良い
おまけ
元の文脈は、機械学習でこういうきれいな数理的関数を一部training dataを使って学習していると、途中までは training data に適合していくだけだが、途中から急に数理的性質を"発見" するという現象 (Grokking) があって面白いね、という話らしい。
https://pair.withgoogle.com/explorables/grokking/ ここにめちゃくちゃ綺麗にまとまっている。インタラクティブに遊べて楽しい。
Discussion