メモ

yukicoderでゆるふわgolf

A Sequence of Permutations

ほんまか？

a_{n}=a_{n-1}-a_{n-2} は a_{n}=a_{n-6} を満たすので、mod 6で見たいという気持ちで式変形をすると
a_n\\ = a_{n-1} a_{n-2}^{-1}\\ = a_{n-2} a_{n-3}^{-1} a_{n-2}^{-1} \\ = (a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1}) (a_{n-5} a_{n-6}^{-1} a_{n-5}^{-1})^{-1} (a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1})^{-1}\\ =(a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1} a_{n-5}) a_{n-6} (\ldots)^{-1}
となって
a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1} a_{n-5}\\ =(a_{n-5} a_{n-6}^{-1}) a_{n-5}^{-1} (a_{n-5} a_{n-6}^{-1})^{-1} a_{n-5}\\ = a_{n-5} a_{n-6}^{-1} a_{n-5}^{-1} a_{n-6}\\ = a_1 a_0^{-1} a_1^{-1} a_0 =:X
として
a_n = X a_{n-6} X^{-1}
を得る。よってO(N\log K)で解けた。

ところでなんでこれうまくいくんすかね。

例えばa_{n}=a_{n-1}a_{n-2}^{-1}a_{n-3}a_{n-4}^{-1}で同じ問題を考えると、同様にある定数 X により a_{n}=X a_{n-10} X^{-1}と書けるが、途中の計算は違っていて、例えば a_{n}=X(n) a_{n-5}^{-1} X(n)^{-1} とは書けない。

証明or反例を募集しています

yukicoder 1322

お断り：提出してないので間違ってるかも

O(N^0.75) prime countingを完全に理解していてこれが解けないのは端的に言ってカスなんだよね

・そもそもφはmultiplicativeなので、当然素因子ごとにわけて考えたくなる
・dp[i][j]=#{n | nの全ての素因子はPi以下、φ(n)=j}としてDPできる
遷移はdp[i-1][j]からdp[i][j*(Pi-1)*Pi^k]に配れば良い
・第2添字には乗算しか登場しないので、「あと何倍したらNを超えるか」しか情報がいらない。平方根で分けるテクで状態数がO(√N)になる
・in-placeに更新することにすると、O(N^0.75) prime counting とほとんど同じ計算量解析により、p*(p-1)≦Nを満たす素数p=O(√N)までO(N^0.75)で計算できることがわかる
・それ以降の素数は高々1個しか含まれないので、各pに対してφ(x)≦N/(p-1)となるxの個数がわかればよい（そしてこれは既に計算済み）
・N/(p-1)は小さいので、pごとではなく、N/(p-1)ごとにまとめて計算すれば高々O(√N)。N/(p-1)=kとなるようなpの個数はO(N^0.75) prime countingを実行すると副産物として手に入っている。（境界が1個ずれてる分はいちいちチェックすれば良い）
・よって解けた

純粋培養競技プログラマが就職して１年

ポエム

■スペック
国立大理系院卒
就職まで競プロ以外でのプログラミング経験なし
今はAtCoder橙
社会性破滅・就活破滅
英語壊滅
IT中小企業にどうにか潜り込む

就活編はこちら
sugarknri.hatenablog.com

■1年経過時点での環境
pythonで機械学習やってる
git使ってない(バージョン管理はSVN)
Linuxわからない
Docker？ AWS？ なんすかそれ

上の方の役職にいる人や意欲的な人は、機械学習の最新の論文を追ったり、Kaggleで遊んでいたりするらしい。俺よりすごいというのはわかる。
そうでない大多数の人たちはどうなんでしょう

周りの人たちと比べてコーディング速度が3倍くらい違うので異世界転生感があってよい。
そういう環境なので向上心は持っておかないとそのまま怠惰で破滅しそう（持ってますか？）

■仕事
最初の数カ月は研修。残りはPoC案件2つを主にやっていたら1年終わった。ソースコード書く人は俺と先輩1,2人だけ、みたいな状況なので、チーム開発とかいうのはよくわからず。PEP8に従ったコーディングをしろと言われたのでそれは守ってる。
コードレビューも最初は熱心な先輩に丁寧に見てもらっていたけど、それ以外の人からは……。ところで、前任者から引き継いだ納品済みのコードが無限にバグっていました。大丈夫ですかこれ？（自明なバグから非自明なバグまで大量に指摘して、私の評価が大変に上がったのでありがたいといえばありがたい（いいえ））

■今後
どうするんでしょうね

指数型母関数

テクニック

この記事は 37zigenさんによる以下の記事をもとに、お気持ちパートを自分にとってわかりやすいようにメモしたものです。
真面目な解説は書いていないので、そういうのを読みたい人は元記事の方をみてください。
37zigen.com




・物を数える

気持ち：「互いに区別できるN要素のものがあります。いい感じの条件を満たすような構造の個数を考えます」というタイプの問題を考えます
構造ってなんやねん。なんらかのなんかです。例をみて

自明１：互いに区別できるN要素のものからなる集合はいくつありますか？
1個。それはね、そう

自明２：互いに区別できるN要素のものからなる順列はいくつありますか？
N!個。はい

自明３：互いに区別できるN個の箱に互いに区別できるK個のボールを入れる方法はいくつありますか？
N^K　はい

自明４：互いに区別できるN要素のものからなる有向サイクルはいくつありますか？
(N-1)!　円順列って知ってる？

非自明：互いに区別できるN要素のものからなる木はいくつありますか？
実はN^(N-2)なんですね

こういう各問題について、Nに対する答えをa_nとしたとき、\sum(a_n \frac{x^n}{n!})というものを考えます。
これ{a_n}の指数型母関数(EGF)っていうらしいですよ。

以下では構造Aの指数型母関数をそのままA(x)と書きます。



・母関数の積

互いに区別できるN要素のものがあります。そのうちいくつかを使って構造Aのものを、残りの全部を使って構造Bのものを作ります。そのような方法は何通りありますか。

適当に計算をすると、こいつの指数型母関数はA(x)B(x)になることが示せます。
2種類以上の構造が登場するときに役に立ちます。

問題：互いに区別できるN個の要素を、aの倍数個の要素からなる集合とbの倍数個の要素からなる集合の2つに分ける方法はいくつありますか？　ただしa≠b
「互いに区別できるN要素のものからなる、aの倍数個の要素の集合はいくつありますか？」は、Nがaの倍数のとき1、そうでないとき0なのでEGFもそんな感じで求まる。
それぞれA(x)、B(x)としてA(x)B(x)が答え

他にも構造Bを「集合」にすると包除もできます。

問題：N要素の撹拌順列はいくつありますか？
撹拌順列のEGFをA(x)、集合のEGFをB(x)、順列のEGFをC(x)とすると、A(x)B(x)=C(x)です。
B(x)、C(x)の正体はわかっているので、A(x)は頑張ると計算できます。

問題：互いに区別できるK個のボールを互いに区別できるN個の箱に入れる方法はいくつありますか？　ただし、どの箱も空になってはいけない
Kを固定して、「i個の箱に入れる。空はダメ」というもののEGFをA(x)、集合のEGFをB(x)、「i個の箱に入れる。空でもOK」というもののEGFをC(x)とすると、A(x)B(x)=C(x)です。
B(x)、C(x)の正体はわかっているので、A(x)は頑張ると計算できます。



・母関数の合成

構造Aをなす各要素を、構造Bをなしているもので置き換えます。全体でN要素になるような方法は何通りありますか。

構造を「代入」しているように、実はEGFの方も代入してA(B(x))になるんですね。なにそれすごい

問題：互いに区別できるN頂点の連結functional graphの個数を求めよ
連結functional graphは、有向サイクルの各頂点を根付き木に置き換えたものです。
有向サイクルのEGFをA(x)、根付き木のEGFをB(x)とすると、求めるもののEGFはA(B(x))です。

問題：互いに区別できるN頂点の森の個数を求めよ
森は、集合の各要素を木に置き換えたものです。
集合のEGFをA(x)、木のEGFをB(x)とすると、求めるもののEGFはA(B(x))です。

問題：互いに区別できるN頂点の単純連結無向グラフの個数を求めよ
連結性の条件を落とすと、明らかに2^(N(N-1)/2)個です。EGFをC(x)とします。
連結とは限らない単純無向グラフは、集合の各要素を単純連結無向グラフに置き換えたものです。
集合のEGFをA(x)、求めるもののEGFをB(x)とすると、A(B(x))=C(x)です。
A(x)、C(x)の正体はわかっているので、B(x)は頑張ると計算できます。



・余談

重みつきで和をとりたかったら、当然係数に重みをつければいいわけですね。

問題：互いに区別できるN頂点の森について、「2^(連結成分の個数)」の和を求めよ
集合のEGFの代わりに a_n=2^n に関するEGF をA(x)、木のEGFをB(x)として、A(B(x))です。

問題：互いに区別できるN頂点の森について、「各連結成分の大きさの積」の和を求めよ
木の大きさをどうやってEGFに載せようかという話になるわけです、a_nの代わりにn*a_nを使いたいという話なので、木のEGF B(x)のかわりにx(d/dx)B(x) を使えばよくて、終わりです。

コネと学歴は就活の役にたつ

ポエム

就活記事です

M2 5月

なんで就活の記事がM2から始まるんですか？
社会のことを何も知りません。人々はいつから就活をしているんですか？
実は修論どころか単位がそろわない可能性があって、就活どころじゃなかったし、この時点でもそれどころじゃない
けどまあAtCoderJobs経由で某社に応募した（コンテストも開いているところ）
当時のレートは1800くらい
なんか面接の途中から人生相談が始まって、1回で落ちた（それはね、そう）
競プロは就活の役にたたない！を主張する以前に、人間性・社会性さんがね……

M2 9月

大学の学生課から「そろそろ後期が始まりますが、学生の皆様いかがお過ごしでしょうか。内定ないやつおりゅ？」というメールが来た
内定ないでーすと返信すると、面談が始まって、パソコンカタカタがやりたいですと言ったら、じゃあここかここでも受けてみたらと2社選択肢を出される
そのうちの一方に言われるままにメールを出したら（なんで一方にしか出さないんですか？）面接2回で内定が出た。やったねたえちゃん
何を話したか何も覚えてない
正直この人間学歴以外評価するとこある？
GPAは多分高かったと思う（計算してない）

M2 1月

実はまだ単位が足りてない。M2後期に講義に出るやつおる？
割と真面目に勉強したにも関わらず期末試験が驚くほど解けなくて、土下座でもなんでもするつもりで「成績早めに教えてください。なんでもするので単位ください」とメールを出したら60可だった。ウケ


就活勝率は1/2なので50%です

終わりです