えびちゃんの日記

えびちゃん（競プロ）の日記です。

素数の数え上げのスライドについて

最近スライドを公開しました：

動機について

やや前に Beamer でスライドを作る機会があったのと、最近 LuaLaTeX を触ってみたというのがあって、LuaLaTeX + Beamer でスライドを書きたいなという欲がありました。

素数の数え上げや乗法的関数の和は、一部界隈では知られていそうだったものの、あまり浸透していない印象があったので勉強したいと思っていました。 そこで、それをスライドに書くことで一石たくさん鳥にしようと思いました。文字ベースの記事だと説明がごちゃつきそうに感じたというのもあります*1。

スライドに関して

スライドのこだわりポイントや、作っていてうれしかった点などをぽんぽん挙げていきます（淡々と空行区切りで書いたところ思ったより読みにくくなった感があります）。

暗めの赤と青の配色は、大学時代に学生たちから畏れられていた教授がよく使っていたテーマを真似して作ったものです*2。

Beamer に詳しい人は知っているかもしれませんが、スライドの以下のような部分がリンクになっていて、ページ遷移が容易なのがうれしいです。

  • ヘッダ部にあるセクション名
  • ヘッダ部にある〇
  • フッタ部左側のタイトル

同じトピックのスライドに関して、タイトルに「I, II, III, IV, ...」と振っている箇所が複数ありますが、これはそういう制御綴を置いておくことで自動で採番してくれるのでうれしいです。

\newcounter{slidetopic}
\renewcommand{\theslidetopic}{\stepcounter{slidetopic}\Roman{slidetopic}}

\setcounter{slidetopic}{0}
\begin{frame}
  \frametitle{タイトル \slidetopic}  % タイトル I
\end{frame}
\begin{frame}
  \frametitle{タイトル \slidetopic}  % タイトル II
\end{frame}
% ...

右下にあるページ番号も（当然）自動採番ですが、\appendix と書いた後は appendix 用のものと切り替えられるらしいのを知ってうれしくなりました。

\addtobeamertemplate{navigation symbols}{}{%
  \usebeamerfont{footline}%
  \usebeamercolor[fg]{footline}%
  \hspace{1em}%
  \makeatletter%
  \ifbeamer@inappendix{%
    \textsc{appendix} {\insertframenumberinappendix} / {\insertappendixframenumber}%
  }\else{%
    {\insertframenumber} / {\insertmainframenumber}%
  }\fi%
  \makeatother%
  \hspace{0.8em}%
}

小文字の appendix だと配置が崩れたので small caps を使いました。

\(+=\) ではなく \(\xleftarrow{+}\) と書くのは、\(\gets\) で代入を意味する擬似コードではいい感じの見栄えなんじゃないかなぁと自画自讃しています。 そこはいいと思うんですが、「記法について」のスライドがちょっと突飛かもと思いました。「記法と言えば prelim で、prelim と言えば最初でしょ」みたいなノリだったと思います。

木の部分は気に入っていて、TikZ はえらいなあと思いました。

\usetikzlibrary{
  graphs,
  graphdrawing,
}
\usegdlibrary{trees}

% ... in {tikzpicture}
\graph[tree layout, sibling sep=0pt]{
  1 -> {
    2 -> {
      4 -> {
        8 -> 16,
        12,
        20
      },
      6 -> 18,
      10,
      14
    },
    3 -> {
      9,
      15
    },
    5,
    7,
    e/...,
    19
  }
};

辺ラベルは、白い太文字を書いた上に黒文字をかぶせることで実現しています。

\usepackage{pdfrender}
\newcommand{\tpr}[1]{%
  \textpdfrender{
    TextRenderingMode=FillStrokeClip,
    LineWidth=3pt,
    FillColor=black,
    StrokeColor=white,
    MiterLimit=1
  }{#1}%
}

% ... in {tikzpicture}
\begin{scope}[every node/.style={font=\tiny}]
  \path
  (1) -- node {\tpr{2}} (2)
  (1) -- node {2} (2)
  (1) -- node {\tpr{3}} (3)
  (1) -- node {3} (3)
  % 各辺に対して同じようなことを書いた。Lua を使えばもっと楽にできたと思う。
  ;
\end{scope}

この構成方法（自身を最小素因数で割ったものが親になる）で作られた木に名前がついていないのか気になります。ないのかなあ。

冒頭の篩や付録ページの DP の差分スライドたちは Lua で実際に DP しながら値を計算して、その結果を出力しています*3。 こういうのが柔軟にできるのはうれしいなあという気持ちになります。Lua なのがうれしいかというと怪しいですが、十分ありがたいですね。

付録スライドに載せるようなコンテンツ（擬似コードなど）は、発表後にゆっくり読んでもらう側面が強いと思ったので、付録の擬似コードはめちゃくちゃに縮小してみました。 最初は、

function lucy()
|  foo
|  bar
+ ...
function lucy()
| ...
| baz
| qux
+ ...
function lucy()
| ...
| quux
| corge
+---

などのように分割することも考えたのですが、シンプルに読みにくいし書くのも大変だなとなってやめました。 スライドを PNG などの画像に変換して読んでいる人がいたらかわいそうなことになりますが、まぁいいかなと思いました。

改行位置には結構気をつけたつもりです。

おまけスライドにちょっとした問題を追記したのですが、「読者への課題です」と言って説明を放棄して迷宮入りするのは好ましくないと思ったので、文字を逆向きにしてちょっと読みにくくして載せる手法を使いました。小さい子向けのなぞなぞの本とかでこういうのがあったような気がしていますが、参考書とかではあまり見ないような気がします。 えびちゃんのセグ木スライドでも同様の手法を使った気がします。

スライドを更新した際に（スライドの TeX ファイルなどは private repository で管理しているのですが）commit hash をつけておくと何らかの捗りがある気がしたので、更新日時とともに載せてみました。LuaLaTeX で比較的簡単に実現できたのでうれしかったです。

ねこねこ勉強ぱーてぃというのは架空の勉強会の名前です。とりあえず仮置きで名前をつけていたところ、考え直すのを忘れて投げてしまいました。

承認欲求の満たされについて

うれしい。競プロ界隈でスライドを作っている人が少ししかいないかもという気持ちも少しあります。と見せかけてそんなことないかも？

うれしい。書いてみた甲斐があります。

その他

実験コードを書いて、計測をした後、「念のため擬似コードにしておくか」と思ってコードを読んでいたところ、実装に誤りに気づいてつらくなりました。\(p_{\pi} \gt n^{1/6}\) で判定するところを \(\pi \gt n^{1/6}\) と書いていました。たぶん log 倍悪くなっていそうですが、修正したらちゃんと速くなってくれたのでうれしかったです。

擬似コードで書く利点ってなんなんでしょう。Rust のコードをそのまま貼る方がうれしいかもとも思ったりはしました。 \(\text{\textbf{foreach }}v \in S\) とか \(x \xleftarrow{+} \sum_i f(i)\) のように数式混じりの表現をそのまま使っても違和感がなさげなのがちょっとうれしいかもと思ったりはしました*4。 特定の言語依存の表現だと、たとえば log(x, y) と書いたときどちらが底なのかわかりにくいとか、そういう嫌な点があるかなとも思いました。

どの言語にも依存していないが、どの言語に移植するにも手間がかかってしまうというのはありますね*5。

擬似コードでオブジェクト指向っぽく \(v.\text{push}(x)\) とか書くのが邪道なんじゃないかと思ったりしつつ、どう書くべきかわからなかったりしました。

あと \(\text{\textbf{for each}}\) のように 2 語にする方が気持ちいいんじゃないかという気持ちもあります。どうしよう。

\(\Theta(n^{2/3})\) の方は \(\Theta(n^{3/4}/\log(n))\) のものよりも定数倍が重くてしんどいかもという先入観があったのですが、意外と勝っていてうれしかったです。\(\Theta(n^{2/3}/\log(n)^{1/3})\) の方も速くてご満悦です。

最初は乗法的関数の \(\Theta(n^{2/3})\) の方は難しいと思ったので 2 回シリーズにしようかと思ったのですが、分かれちゃうのもアレかと思って、詰め込んでしまいました。

きもち

AtCoder でこの手のアルゴリズムが出題されるされないとかそういうのは抜きにして話します。 内容自体はそこまでレートが高くなくても読める内容だと思うので、読んでみてもらえるとうれしいかもしれないと思いつつ、書いた後だからそう思うだけで難しいのかもと思ったり、ぐるぐるしています*6。

参考にしていたブログは最初は行間たっぷりに見えていたのですが、今では簡単に見えてしまったりしているので、えびちゃんの目はあてにならないです。

省略する。

とブログで書かれていた部分も、今では「そりゃ省略したくもなるよなぁ」と思ってしまうまであります。

なつかし

floor sum の解説記事を書いたときや、ACL math の解説記事を書いたときにあれこれ調べたのを思い出しました。数学のことを調べるのはやっぱりすきなんだろうなぁと思ったりしました。

おわり

おわりにゃ。次はなにの勉強会をしようかにゃぁ。

*1:実際、前に書いた記事はそういう感じになった気がします。

*2:Thank you! スライドも同様です。

*3:SATySFi でもそういうことができそうな感はありますね。

*4:下手に書くと計算量のごまかしや行間になりそうですが、それについてはスライド中で説明をしているつもりです。

*5:擬似コードってラテン語っぽい雰囲気があったりするでしょうか。

*6:あまり難しくないですよーと言って読んでもらおうとするのは、読めなかったときに落ち込んでしまいがちなので、あまりよくない気がしています。