メモ

yukicoderでゆるふわgolf

純粋培養競プロerが応用情報技術者試験に合格するまで

Q.これはなに笑 
A.う笑 

・スペック
理系だが情報系ではない
競プロ以外のプログラミングをしたことはない


・2019年2月
基本情報技術者試験とかいうのを受けておくといいことがあるらしい
適当に参考書を1冊買う

・2019年3月
とりあえずノー勉で過去問を1回分解いてみると午前が5割弱、午後が1ミス(98点?)だった。
合格ラインは6割なのですぐ届く気がするが、4択問題なので、実は3割しか分かってなくても30%+70%×1/4=47.5%くらいの点が取れるんですよね~

・2019年4月
基本情報技術者試験ドットコムだかなんとかいうサイトの過去問をランダムに表示する機能を使ってとりあえず300問くらい解いてみる。
すると7割くらい解けるようになってきた気がするので過去問を2回分やってみるとどっちも7割前後とれている。
試験勉強終わり! 一度も開いてない参考書さん…………

・結果
午前が70ちょっと、午後満点。

・2019年8月
気付いたら申し込みの締め切りが翌日に控えていた。慌てて応用情報技術者試験に申し込みをする。

・2019年10月
気付いたら試験日が来週に迫っていた。
とりあえず午前の過去問を解いてみると7割くらい解ける。基本情報と難易度変わらね~ 勝ったなガハハ

・試験本番
そういえば午後ノー勉だけど大丈夫? → 配られた解答用紙を見たぼく「記述式マジ?初めて知った」

・結果
午前が70ちょっと、午後は80ちょっと


・所感
基本情報は英語と国語とプログラミングが出来ると合格できそう。
ぼくは英語ができないので英語の勉強をしました(はい?)
フォールトアボイダンスはフォールトをアボイドするという意味だし、フェイルセーフはフェイルしてもセーフという意味だし、フォールトトレランスはフォールトにトレランスだという意味。(トレランスという単語を初めて知りました)
応用情報は、基本情報との難易度の違いがわからなかった。出題の幅が広い気がするので、自分が取る予定の選択問題の難易度が爆発してたら死ぬってことがあるらしい? ぼくは全部の問題をざっと解いてから、高点数が取れそうな問題を選ぶ立ち回りをしたのでよくわかりませんが……

・いかがでしたか?
巷で言われてるよりもずっと簡単ですよ。
みなさんも受けましょう。
ちなみに恩恵はいまのところありません。

形式的べき級数

Operations on Formal Power Series - Codeforcesを読め 終わり


以下では形式的べき級数環および形式的べき級数体にという概念を既知とし、その演算を具体的に計算機で計算するという部分に焦点を当てる。係数環は体とする。

数学わかる人向けの説明:
形式的べき級数の操作は係数体の標数が0であることを課していることが多いが、競プロの文脈ではFpを係数体として考えることになる。
その辺の問題を回避するには、「p-1次未満の多項式に関する操作を、一旦\mathbb{Q}[[x]]に持ち上げて計算した後、\mathbb{F}_p[x]に戻している」と考えるのがよさそう(ほんとう?)



●加減算、スカラー
F±G,kFの結果をn次の精度で得るには、F,Gがn次の精度でわかっている必要がある。
やるだけO(n)

●形式的微積
F',∫Fの結果をn次の精度で得るには、Fがn+1,n-1次の精度でわかっている必要がある。
やるだけO(n)
ここで積分は、定数項が0になるようにとるものとする


●乗算
FGの結果をn次の精度で得るにはF,Gがn次の精度でわかっている必要がある。
FFTでO(nlogn)

●除算
1/Fの結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
1/Fが求められれば良い。Fの定数項は1であるとしてよい。
ニュートン法により求められる(※)。
具体的には、Fが与えられた時、FG=1となるGを次の手続きで求める。
f(x)=1/x-Fとおくと、求めるべきはf(x)=0の解。ニュートン法の漸化式はG_{k+1}=2G_k-G_k^2Fとなる。
この式を用いて計算するとG_{k+1}F-1=-(G_kF-1)^2を得、たしかに2次収束していることがわかる(※※)。
ニュートン法の計算過程において、G_kの精度がO(2^k)次程度であることから、Fもその程度の次数で打ち切ったもので計算を行って良い。
(実装上は2^kなのか2^{k+1}なのか2^k+1なのかなど、細かいところに注意が必要)
漸化式1回の計算には乗算が定数回あるので計算量は\sum_{k=1,2,4,8,...} O(k \log k)=O(n\log n)
(※ニュートン法が一般に形式的べき級数環でうまくいくかは考えてないが、体上の形式的べき級数環はHensel環なのでHensel's lemmaから言えるはず)
(※※一般の場合がどうであるにせよ、今回うまくいくことここで正当化されている)

平方根
√Fの結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
Fの定数項は1であるとしてよい。(mod pでの平方根を求める方法は既知とする)
ニュートン法により求められる。
具体的には、Fが与えられた時、G^2=FとなるGを次の手続きで求める。
f(x)=x^2-Fとおくと、求めるべきはf(x)=0の解。ニュートン法の漸化式はG_{k+1}=\frac{G_k}{2}+\frac{F}{2G_k}となる。
この式を用いて計算するとG_{k+1}^2-F=\frac{(G_k^2-F)^2}{4G_k^2}を得、たしかに2次収束していることがわかる。
漸化式1回の計算には除算が定数回あるので計算量は\sum_{k=1,2,4,8,...} O(k \log k)=O(n\log n)

●exp
Fを定数項が0であるような形式的べき級数とする。
このときexp(F)を\exp(F)=\sum_{k=0}^{\infty}\frac{F^k}{k!}により定める。
(定数項が0でない場合、定数項の計算に無限和が残って困る)
exp(F)の結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
実際に求めるときにはlogを使うので、説明はlogの話のあとで。

(※分母にn!があることから分かる通り、本当は係数体の標数が0のときにしか定義されないが、標数未満の次数についてのみ考える場合はいい感じになる。正確にはこういう可換図式を睨むことになるはず? もっと簡単だったら教えて)

 \require{AMScd}
  \begin{CD}
     \mathbb{Q}[[x]] @>>> \mathbb{Q}[[x]] / (x^n)  \ \ \supset @. \ \ \mbox{subset of } \mathbb{Z}_{(p)}[[x]]/(x^n) @>>> \mathbb{F}_p[[x]]/(x^n)\\
     @V{\exp}VV @V{\exp}VV @V{\exp}VV @V{\exp}VV    \\
     \mathbb{Q}[[x]] @>>> \mathbb{Q}[[x]] / (x^n) \ \  \supset @. \ \ \mathbb{Z}_{(p)}[[x]]/(x^n) @>>> \mathbb{F}_p[[x]]/(x^n)
  \end{CD}


●log
Fを定数項が1であるような形式的べき級数とする。
logはexpの逆演算で定義される。すなわち、定数項が1であるようなFに対して、\exp(G)=Fを満たすGがただ1つ存在し、それをG=\log(F)と定める。(※次数が低い方から順に考えると存在し一意であることがわかる)
log(F)の結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
合成関数の微分(※)から
\exp(G)=F\\
G'\exp(G)=F'\\
G'F=F'\\
G=\int F'/F
したがってO(n\log n)
(※expの実体はべき級数なので、(解析学の意味ではなく、代数学の形式的操作の意味で)成立することが示せる)

●expふたたび
ニュートン法により求める。
f(x)=\log(x)-Fとおくと、求めるべきはf(x)=0の解。ニュートン法の漸化式はG_{k+1}=G_k(1-f(G_k))となる。
計算するとf(G_{k+1})=-\frac{f(G_k)^2}{2}+O(f(G_k)^3)となり、確かに2次収束していることがわかる。
漸化式1回の計算にはlogと乗算が1回あるので計算量は\sum_{k=1,2,4,8,...} O(k \log k)=O(n\log n)

●expその2
冒頭で挙げた記事に書かれているやつ。
これもニュートン法だが、logを明示的に計算しない。
代わりにH_k=1/G_kとなるものを持つ(等号はmod x^(2^k))。具体的に漸化式は次のようになる。
H_k=2H_{k-1}-G_kH_{k-1}^2
G_{k+1}=G_k(1-\int H_k(G_k'-G_kF'))
Hの方の漸化式は少し前に述べた、逆元を求めるニュートン法そのものなので説明は不要だろう。Gの漸化式について述べる。
H_k=1/G_kを漸化式に代入すると
\int H_k(G_k'-G_kF')\\
=\int(\frac{G_k'}{G_k}-F')\\
=\log(G_k)-F\\
=f(G_k)
となり、同じ式が得られた。(※等号は mod x^(2^k))
(※最初に挙げたlogを使うものの計算量は各kで乗算2回除算1回積分1回。この方法は乗算3回微分1回積分1回である。どっちの方が早いかは知らん)

平方根その2
Fの定数項は1であるとしてよい。
指数法則の成立が確認できる。すなわち\exp(F+G)=\exp(F)\exp(G)が成り立つ。(※解析学の意味ではなくry)
このことから、n/mに対して\exp( (n/m)\log(F))=F^{n/m}になることがわかる。
したがって\exp( (1/2)\log(F))を計算すれば良くO(n\log n)

N以下の素数の個数

N以下の素数の個数π(N)をO(N^(3/4))で求めるアルゴリズムを説明する。
(真面目にやるとO(N^(2/3+ε))になったりO(N^(2/3)/(logN)^2)になったりするらしいですが、それらはまだ理解していないので……)

○DPテーブルの設計
DP[i][n]=(n以下の数のうちi番目の素数まで篩にかけて生き残る数の個数)
とする。例えば
DP[0][10]=9、(2,3,4,5,6,7,8,9,10)
DP[1][10]=5、(2,3,5,7,9)
DP[2][10]=4、(2,3,5,7)
DP[3][10]=4、(2,3,5,7)
となる。
定義よりDP[π(√N)][N]=π(N)となることがわかるので、これを求めることを目標とする

○DPの遷移
i番目の素数p_iで表すことにする。(1-indexed)
明らかに
DP[i][n]=DP[i-1][n]-(n以下の数のうち、p_iによる篩で新たに落とされる数の個数)
となる。
「n以下の数のうち、p_iによる篩で新たに落とされる数」
⇔「n以下の数のうち、最小素因数がp_iであるような数(p_i自身を除く)」
⇔「n以下の数のうち、p_i未満の素因数をもたず、p_iを素因数にもつ数(p_i自身を除く)」
であり、これはp_iで割ることで次と1対1対応する。
n/p_i以下の数のうち、p_i未満の素因数をもたない数(1を除く)」
⇔「n/p_i以下の数のうち、p_{i-1}以下の素因数をもたない数(1を除く)」★
定義より
DP[i][n]=(n以下の数のうちi番目の素数まで篩にかけて生き残る数の個数)
=(n以下の数のうち、p_i以下の素因数をもたない数(1を除く)の個数)+(p_i以下の素数の個数)
だったので、★を満たす数の個数はDP[i-1][ n/p_i ]-(i-1)となる。
よって
DP[i][n]=DP[i-1][n]-DP[i-1][ n/p_i ]+(i-1)
という漸化式を得ることができた。

○計算の省略
DPテーブルの第2添字に入る値は1~NまでのN通りがあり得るが、漸化式をよく睨むとDP[*][N]を求めるための計算にはN/kの形で書ける数しか必要ないことがわかる
よって平方分割により実際には高々O(√N)個の部分しか計算しなくてよいことがわかる

○計算の省略2
DPの漸化式を見ると、DP[i][*]はDP[i-1][*]のみから計算できることがわかる。
また漸化式の右辺に登場するものの第2添字は、左辺に登場するものの第2添え字以下であるから、第2添字の大きいほうから順に計算することでDPテーブルを使いまわすことができる。(01ナップサックを思い出そう)
よって以下DP[n]の形で表すことにする。

○計算の省略3
p_iによる篩の影響を計算する際には、k< p_i^2であるような範囲についてはDP[k]の値は変化しない。このことを考慮することで計算量を削減することができる。具体的には次の通り
p_i< N^{1/4}の範囲
毎回O(√N)箇所のDPテーブルすべてを計算する。
N^(1/4)以下の素数の個数は自明にO(N^(1/4))なので全体で高々O(N^(3/4))
N^{1/4}< p_i  \leq N^{1/2}の範囲
更新が必要なのはk \geq p_i^2範囲だが、前述の平方分割テクによりこの範囲で計算する必要があるのは N / p_i^2
したがって全体では\displaystyle{
\sum_{N^{1/4}< p_i  \leq N^{1/2}} \frac{N}{p_i^2}
}箇所の更新が必要になる。
\displaystyle{
\sum_{N^{1/4}< p_i  \leq N^{1/2}} \frac{N}{p_i^2}
< \sum_{k=N^{1/4}+1}^{N^{1/2}} \frac{N}{k^2}
< \int_{N^{1/4}}^{N^{1/2}} \frac{N}{x^2}dx
=N^{3/4}-N^{1/2}
=O(N^{3/4})
}
なので全体で高々O(N^(3/4))

以上のDPは、あらかじめ√N以下の素数を列挙しておけば行えるため、時間計算量O(N^(3/4))、空間計算量(N^(1/2))で計算できることがわかった。


見てわかるとおり、この評価は極めておおざっぱなので正確に評価すると多分O(N^(3/4)/logN)とかくらいになる気がする。

出典はproject eulerのthread。ただし、この問題に正解していないとみることができない。
冒頭で紹介したMeissel–Lehmer algorithmの簡略版(のはず)だが、threadに書き込んだユーザーの名前を借り、project eulerではしばしば"Lucy's Algorithm"と呼ばれる。

atcoder橙になるまでにやったこと

少し前に橙になったのでポエムを書きます
青になるまで:atcoder青になるまでにやったこと - メモ
黄色になるまで:atcoder黄色になるまでにやったこと - メモ

黄色から橙になるまでにしたこと
・コンテストに10回くらい出た
・800点を半分くらい埋めた
・銀パフォを出した(!?)

なぜか最近AtCoderが数学コンテストサイトになったおかげでめちゃくちゃ伸びた。
対800点問題の戦績が6勝2敗と好調だったことが大きな要因であるように思う。
(青~黄色の間には800点は1度も通したことがなかったのに)

橙のラインはこんな感じ
・600以下を確実に解く。可能なら早解き
(600早解きに成功すればその時点でパフォ2000-2200がほぼ確定するので大事故がなくなる)
・700をだいたい解く
・800に勝ち越す
・900以上も問題を読んで解けそうなら解く

やはり蟻本は読んだことがないです。
読まなくても橙にすらなれます、と胸を張って言いたいところですが、多分読んだほうがいいと思います。
次回「atcoder赤になるまでにやったこと」は10^18+9年後の予定です。お楽しみに

位数Xのアーベル群

出典

この問題は「互いに区別できるX要素の集合に、アーベル群の構造を入れる方法は何通りあるか?」と同じになる。
これはOEISで検索すると見つかる。
A034382 - OEIS
項の数が少なく(注:この記事を書いた当時は20項しかなかった)、求め方も乗っていないので、最初のツイートの制約で解くにはまだ足りない。導出を考えてみよう。

以下、単に群といえばアーベル群を指すものとする。
各記号を次の通り定める。
pは素数とする
C_n 位数nの巡回群 \mathbb{Z}/n\mathbb{Z}のこと
S(X) 位数Xの群の同型類の集合(各同型類とその代表元を同一視する) これはここだけの記号であり一般的なものではない
Aut(G) Gの自己同型群
GL(k,R) 可換環Rのk×k行列で可逆なものの集合
単に「元gの位数がn」といった場合は「ちょうどn」とは限らないものとする。(例えばC4の元は全て位数4である)


X=\prod p_i^{e_i}とする。
S(X)から群を1つとりGとすると、それと同型になるようにするには、どの元にどれを割り当てるかX!通り。……ではなくX!/#Aut(G)通り。
例えばC_3になるよう{0,1,2}に群構造を入れるとき、0を単位元にしたら、のこりの2つの元のどちらを1,2に割り当てても同じになるので。
ということで、求める答えは
\displaystyle{
\sum_{G \in S(X)} \frac{X!}{\# Aut(G)}
}
ここで、a,bが互いに素ならS(ab)=S(a)×S(b)であること、
GとG'の位数が互いに素ならAut(G×G')=Aut(G)×Aut(G')であることから
\displaystyle{
\sum_{G \in S(X)} \frac{X!}{\# Aut(G)}\\
=X!\prod_i \sum_{G \in S(p_i^{e_i})} \frac{1}{\# Aut(G)}
}
となる。
(これは\sum_{i,j,k}a_i b_j c_k=(\sum_i a_i)(\sum_j b_j)(\sum_k c_k)と同じ式変形)
位数p^eの群は、必ず\prod_i C_{p^{n_i}}^{k_i} の形で書くことができる。ここで\{n_i\}は狭義単調増加するようとるものとする。
位数の条件からe=\sum_i n_i k_iである。
巡回群は生成元の行き先さえ決めれば準同型が定まる。n_iの大きい方から考えることで、準同型が同型であるためには、C_{p^{n_i}}^{k_i}の生成元たちは送った先でもこの部分を生成していなければならないことがわかる。そのような割り当て方は
\displaystyle{
\# GL(k_i,\mathbb{Z}/p^{n_i}\mathbb{Z})=p^{(n_i-1)k_i^2}\prod_{j=0}^{k_i-1} (p^{k_i}-p^{j})
}通りである。
(n_i=1のとき、\mathbb{Z}/p\mathbb{Z}が体であることから「k次元ベクトルk本を一次独立に選ぶ」ことと対応するので総積部分が得られる。n_i \geq 2のときは、"1の位"をそのように決め、"pの位"から上は自由に決められるので残りの部分が得られる)
また各iについて、送った先でC_{p^{n_i}}^{k_i}にあたる部分以外は位数p^{n_i}であれば何を割り当ててもよいので、\displaystyle{
( \prod_{j\neq i} p^{\min(n_i,n_j)k_j} )^{k_i}
}通りとなる。
(例えばC2×C4×C8のとき、C4の生成元はC2の部分は自由に取れ、C8の部分は位数4の元4つの中から自由にとれる)

よって以上より
\displaystyle{
\# Aut(\prod_i C_{p^{n_i}}^{k_i})
=\prod_i \left( (p^{(n_i-1)k_i^2}\prod_{j=0}^{k_i-1} (p^{k_i}-p^{j})) ( \prod_{j\neq i} p^{\min(n_i,n_j)k_j} )^{k_i} \right)
}通りとなる。

ここで\# S(p^e)はeの分割数に等しいことがわかるので、これは対して大きくならず、結局計算のボトルネックになるのはXの素因数分解部分であり、計算量はO(\sqrt{X})である。

……と思ったのだが、プログラムを書いて計算すると、X=16のときがOEISの結果と一致しない。
上の計算式によれば
#Aut(C16)=8
#Aut(C2×C8)=(1×2)×(2×4)=16
#Aut(C4×C4)=(16×3×2)=96
#Aut(C2×C2×C4)=((3×2)×2^2)×(2^2×2)=192
#Aut(C2^4)=(15×14×12×8)=20160
であるから、求める答えは16!×(1/8+1/16+1/96+1/192+1/20160)=4250979532800となる。
一方、OEISでは4248755596800になっている。これは第4項が1/192ではなく1/196なら一致することがわかるが、プログラムを書いてみると、確かにAut(C2×C2×C4)=192であることが確かめられる。そもそも49の倍数になるわけないだろ、なんでだよ


ここまでの議論に誤りを見つけた方、または、OEISの記述が間違っていると確信が持てる方はご一報ください。
なお、上の議論に則って実装したコードはこれです。(mod 10^9+7で出力)
https://wandbox.org/permlink/9RLseRNaHU5CeQiU
自己同型群の位数が計算できてるので実装がバグってることはないはず

(2019/09/13追記)
mathoverflowできいた。
mathoverflow.net
OEISが間違っていた。(えー)
その結果、OEISにsugarknriの名前が載った(!!!???!??!?!?)