0-origin についての自分の主張まとめ

自然数：

• 本当に考えたい概念が「x以上の整数」ではないことがほとんど。
• 有限集合の代表元として使う場合 0 から。（空集合を早々に除外する合理性はまずないです。）
• 整数の四則演算（素因数分解など）に興味がある場合、整数環 Z の正則元を可逆元で同一視するのが大事で、この場合は 1 から。つまり ±1, ±2, … のことを自然数と思っているということ。
• トポロジーの次元、次数などはベクトル空間としての次元が 0 から始まるのを基準にしていたら −1 次や −2 次にも自然に拡張されてしまった。この分野で「正整数」「非負整数」より長い呼称を許せない派閥がこれを「自然数」と呼ぶことがある。

数学の添字：

• 1 … n 表記をする場合は 1 からにしておくのが楽。（一般的に変数名が1文字の分野は手書きの楽さが重要。）
• 1つ追加した概念（射影空間とか）が便利なことも多く、そのために0を空けておくメリットもある。

自然言語：

• 並べて呼んでいってnで終わったらnにしたい気持ちは優先したい。口頭での日常的な 0-origin は分かっている人同士でやってもネタ以上の実用性にならなかったように思う。
• でも、序数が半端におしゃれな言語で技術的な話をするのは嫌い。 x[0] を英語で読むとき zeroth か first かで困る。Rust の x.0 は？
• その点 ground floor と呼べるからイギリス式階数は良い。

プログラミング：

• 現実と数学をつないでいる分野なのでどこに寄っているかで決めてください。
• CPU に div mod があるので最終的にはそこにあわせるために 0 からになる。
• プログラミング言語レベルにビジネスロジックを持ち込みたくないのでここでもまだ 0 からが良いと思う。
• Optional[uint] で 0 をバグらせないように1枠捨てて 1 からにするみたいな合理性はいろいろある。（この例は型が弱い言語が「悪い」けど。）
• 技術者以外にも表示する可能性があるもの（line 1, column 1 など）は技術者としては悔しいが 1 からなことを受け入れる。

Simulating Time With Square-Root Space のアルゴリズム

空間計算量に対して高々指数オーダーの時間計算量になることは（鳩の巣原理から）自明なのに対し、逆は対数オーダーにはできないと予想されつつも（L≠PもPSPACE≠EXPTIMEも未解決）、(1-ε)乗オーダーの空間計算量にすることさえできないでいた。そんな中、ほぼ平方根オーダーの空間で計算できることが示された¹。その論文 Simulating Time With Square-Root Space や引用先をちょっと前に読み、最近人に説明するためにまとめたのでそのメモをブログに転用。

読んだきっかけは

https://t.co/H4Tu31Sbvh これ、前に読んだ Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛) https://t.co/F5BW0PYr3e の結果を応用しているらしいんだけど、あれってそんな即座に凄い結果に結びつくんだ。すごいなあ

— kinaba (@kinaba) March 7, 2025

で、後から振り返ると "Tree Evaluation is in Space O(log n · log log n)" のkinabaさんの要約

eccc.weizmann.ac.il/report/2023/174/ 面白い。葉に1~kの値、内部ノードにk*kの表で関数が乗った二分木の式の評価値を求める問題、logspaceで解けなそう（高さ*log k要りそう）候補だったのが、高さ*log log kまでは迫れたという。可逆計算みたいなのと有限体の性質を駆使してスタック無しで値復元しながら再帰する

で（前提知識がある人にとっては）十分な気もしてくるのだが、これだけで具体的なアルゴリズムが想像つかなかったので自分で詳細を追った。Tree Evaluation という問題の提案自体（2012年）は別として、それに対してだいたい3つのアイデアを積み重ねると表題の結果を得るというのが私の理解。順に、

• 「可逆計算みたいなの」が提案されたのが2014年出版 Computing with full memory: Catalytic space （論文1）
• 有限体の性質を駆使して Tree Evaluation の空間計算量を改善したのが2023年出版 Tree Evaluation is in Space O(log n ⋅ log log n) （論文2）
• Tree Evaluation への帰着をしたのが今年のプレプリント Simulating Time With Square-Root Space （論文3）

で、以後の箇条書き番号もここで振った番号にあわせる。

Tree Evaluation をナイーブに再帰計算しようとするとスタックが必要というのは、2つの subtree のうち先に評価したほうを覚えておくため。とくに最後の leaf を訪れたときにどの深さでも必要になる。LOGSPACE (L_(complexity))) の知名度が低いのか P vs PSPACE への応用に注目されがちな感もあるが、（入力長未満のオーダーの空間計算量を考えるときは）入力は読み取り専用で与えられることに注意しておく。つまり、関数を与える表の入力の部分を計算結果に書き換えるとかはできない。（他にも対角線論法の詳細とか time-constructible など技術的定義とかはたとえば Sipser, Michael. "Introduction to the Theory of Computation." の Chapter 9 Intractability に書かれていることは確認したのでこれか適当な教科書を読みましょう。）

---

研究の流れ

1. "Computing with full memory: Catalytic space" (Corollary 6) で（有限の）環上の多項式を省メモリで計算することができることが示されていた。
2. "Tree Evaluation is in Space O(log n ⋅ log log n)" で、任意の（有限集合上の）2項演算を適当な有限体に埋め込んで多項式に帰着できる（もちろんこの帰着も十分省メモリにできる）ことを示して、TreeEval がかなり省スペースで計算できることが言えた。
3. TreeEval はもともとこれで L と P を分離できるのではと予想されていただけあって、Lの中での難しさ（NP「完全」的な意味）をちゃんと任意のプログラムの帰着の話に言いかえた。これによって時間計算量 O(t(n)) に対しての空間計算量上限という形での改善結果を得た。

アルゴリズムや具体的なオーダー

1. "Computing with full memory: Catalytic space" では n 個のレジスタだけでスタックメモリを使わず再帰計算するテクが提案されている。cleanly computes f （ここでは Section 3 Transparent computation） を基本単位にして組み合わせるというアイデアで、 f の計算を代入ではなく加算 で許すことにするとあとで同様の関数を呼んで今度は減算すればレジスタを元に戻せる。そのかわりに、f の計算結果の利用が難しくなって、 r_i にもともと何が入っていたかを覚えずに f を用いた計算を組んでいく必要がある。
2. "Tree Evaluation is in Space O(log n ⋅ log log n)" では alphabet size k 上の2項演算を binary tree 上再帰計算する（1ノードあたりの入力長 k² log k）。もとの alphabet の値は 1bit のレジスタ log k 個で表現できるが、多項式の次数に応じた大きさの有限体に埋め込む必要があり log log k bit のレジスタを使う（Section 5 のように埋め込みのオーバーヘッドをさらに削ることもできる）。レジスタの個数は2入力1出力それぞれに割り当てればよく 3 log k 個で済む。スタック変数はループ変数（log log k bit）のみ。
3. Theorem 3.2 として引用しているように oblivious simulation という入力長 n にしか依存しない two-tape Turing machine に変換できる（時間のオーバーヘッドはもとの log が掛かる）ということを使う²。計算時間を b ステップごとに切ると、この b が tree の高さ h と値の情報量 log k のトレードオフになるので平方根くらいを選ぶと良い。

「実用的」かどうかについて

1. clean computation はサブルーチンを少なくとも2倍の回数呼ぶ必要がある。これだけでも再帰の深さ h に対して 2^h 倍のオーバーヘッド。
2. 有限体に埋め込むテクは、有限体の元をすべてまわって足すとほしいものだけ残ることを使っている。同じ関数を O(log k) 回呼ぶのでさらに大変。
3. 普通に書くプログラムは値にあまり計算手順が依存しないはずだとするとTreeEvalへの帰着のオーバーヘッドは少ないはず（だが、ここまでの1,2がやばい）。

---

1. 既存の結果 O(t / log t) も今回の結果 O(√(t log t)) も multitape Turing machine での定式化。↩
2. テープ数を減らしてデータ用を1テープで済ませる帰着ではテープヘッド位置でそろえて転置するが、テープ内容を毎ステップずらすともとの時間計算量 t に対して O(t²) になってオーバーヘッドが大きい。ずらす処理を適切に遅延させると O(t log t) になるというのが Two-Tape Simulation of Multitape Turing Machines の主張。さらに O(t log t) 版もobliviousにできることは（この論文をざっと見て見つからなかったので）強調はされていないようだが、それ込みで引用するのは他の論文でもされているっぽい。ここがナイーブに O(t²) のままだと2乗の平方根で自明な評価になってしまう。↩

PDFにiPadで手書きメモする方法の比較

再編集が全体的に厳しかったのでPDFの中身を見た。

要件

1. 論文やレクチャーノートを読みながら計算したりコメントを残したりしたい。ノートが別になると管理が面倒そうだし、どの箇所を指した内容なのかを分かりやすくするためにもPDFに直接書けると嬉しい。
2. 論文の文字と同じくらいのサイズで書きたいことがあり、それで困らないくらい細い線を書ける必要がある。最初は意識していなかったが私にとっては必須要件だった。
3. 数式とか図とかをすぐ書きたくなるので手書き。iPadとApple Pencilを持っているのでそれらを使う。文字だけでも筆圧利用のほうが綺麗に書ける。

ちなみに、白紙からデジタル手書きする用途はiPadにデフォルトで入っているFreeformでOK。1つ1つの内容が長くなることが今のところないので。

iPadアプリ比較

結論：今の手持ちの環境でやりくりするなら以下の2択

• Goodnotesにimportして書く。これをソース扱いし、必要なときにPDF出力。（管理がやや面倒。）
• Dropboxで書く。古い線の編集はAcrobat Readerを用いる。（筆圧を諦める。）

全体的な話

アプリ間での互換性を考えると、PDFのannotation（後述）になっていれば扱えることもあるというくらいの状況。逆に元のデータと追記の区別がつかない保存の仕方は平坦化(flattened)と呼ばれているらしい。

アプリ内でも過去に保存した線を編集できるかに注意が必要。アプリ独自形式で保存している場合は大丈夫だが、PDF形式のまま編集した場合や、PDFにexportしたものを再度importした場合は編集できないことが多い。

Acrobat Reader

最細の線に設定にしても太すぎる。同じ筆で続けて書いた線が1つのannotationにまとまる。筆圧なし。後から1画単位で移動・リサイズ・削除ができるが筆圧情報は消える。PDFファイルを上書き保存するので、有料のexport機能は不要。

Dropbox

同じ筆で続けて書いた線が1つのannotationにまとまる。筆圧なし。

Files

最細の線に設定にしても太すぎる。他アプリで編集できないように見えるが、ビットマップ画像を持つsquare annotationとして保存されている。

Goodnotes

PDFをimport/exportできる。Editableを選択すればPDF出力は1画ずつannotationになる。無料プランだとノート3つまでだが、独自形式のままimport/exportすれば詰まない（不便だけど）。

Notability

PDFをimport/exportできる。PDF annotationになるようなexport設定が見つからない。無料プランだと1週間あたり編集回数制限があるのがリスク。

OneNote

iPadOS 17以上が必須で、手持ちのiPadのバージョンが上げられないため未検証。

Preview (macOS) + Sidecar

annotation単位での移動と削除ができる。移動しても筆圧情報が消えないところは良いが、リサイズできないのは残念。

Sidecarは筆圧対応しているらしいが、Previewでは効かなかった。

技術的詳細

PDFのファイルフォーマットとしてどう保存されているか確認するには（テキストエディタで直接開いてもわりとなんとかなるが） pypdf でほとんど情報を落とさずに読める。repr にstreamの内容が出ないことに注意して（pypdf.generic.EncodedStreamObject に .get_data() して）おけばあとは __getitem__, .get_object() していれば良い。例えば

reader = pypdf.PdfReader("input.pdf")
print(reader.pages[0]["/Annots"][0]["/AP"]["/N"].get_data().decode())

で1ページ目の最初のannotationの形状が得られたりした。

ここにデータがあることはファイルの中身を見れば想像がついたものの、内容を理解するのに必要な情報が都合よくまとまっていることはなく、pypdfの解説からPDFの仕様書をたどって検索するのが早かった。

pypdf.readthedocs.io

annotation (/Annots) のうち手書きの線はink annotation (/Subtype /Ink) でパスのリストが /InkList に保存されている。ただし、これだけだと表示は実装依存で、border style (/BS) に太さなどが入っていたりやappearance stream (/AP の通常 /N の stream) にgraphics objectというベクターデータが入っていたりで表示が定まる。

実際のアプリの実装を考えると、筆圧（パスの点ごとの線幅）をPDFに保存する標準的な方法はなく¹形状を /AP に書き出すくらいしかない。表示については /AP が存在すれば /InkList, /BS より優先という仕様とはいえ、annotation編集にまでそのルールなのかは微妙で²、 /InkList を編集して /AP は消すか再計算という実装になるのも仕方ない。実際、Acrobat Readerがそうで、他アプリ由来の線は一定の線幅(/BS)なら維持されるが太さの変化(/AP)はなくなる。

---

1. 例えばApple (Files, Preview)は画像化する前の元データか何かを /AAPL:AKExtras に保存しているようだが……。↩
2. 図形としてリサイズするのが実装が良いかは好み。線の太さがバラバラになってしまうと美しくないという考えも分かる。↩

URLSearchParams は使って良い

概要

• URLSearchParams の仕様は HTML form submission の仕様と揃えられている。
• これを RFC 3986 違反と言うのはやめてほしい。

本文

この記事では（"URLSearchParams RFC" で検索して出てきがちな）以下のような主張から URLSearchParams を弁護していきます。

URLSearchParams を使ったら * を %2A に変換せずそのままにしていた。RFC 3986 で * は予約された文字なので厳密には仕様に準拠していない。

実は WHATWG の出している URL Standard に

Align RFC 3986 and RFC 3987 with contemporary implementations and obsolete the RFCs in the process.

と書かれているので、もし仕様変更があったとしても WHATWG が正統とみなすというので終わる話だったのですが、中身を読んでしまったので確認した話が続きます。

---

URLSearchParams の仕様 https://url.spec.whatwg.org/#urlsearchparams の Note は URL.search と URL.searchParams の差の説明を目的としているようにも読めるが、ともかく application/x-www-form-urlencoded を利用することが書かれている。名前のとおり HTML form submission で使われる形式で、エンコード対象は

https://url.spec.whatwg.org/#application-x-www-form-urlencoded-percent-encode-set

The application/x-www-form-urlencoded percent-encode set contains all code points, except the ASCII alphanumeric, U+002A (*), U+002D (-), U+002E (.), and U+005F (_).

なので RFC 3986 で unreserved の記号 -._~ と差がある。

---

そもそも RFC 3986 の reserved character とは何なのか。

https://datatracker.ietf.org/doc/html/rfc3986#section-2.2

reserved    = gen-delims / sub-delims

gen-delims  = ":" / "/" / "?" / "#" / "[" / "]" / "@"

sub-delims  = "!" / "$" / "&" / "'" / "(" / ")"
            / "*" / "+" / "," / ";" / "="

URL をコンポーネントに分解するのに用いる区切り文字 (gen-delims) より多くを予約しているらしい。

The purpose of reserved characters is to provide a set of delimiting characters that are distinguishable from other data within a URI.

で始まる段落を読むと、目的は区切り文字として使用可能にすること、実装は percent encode するしないを区別することだと分かる。より具体的に言えば、

• sub-delims が &, = を含むので以下を区別することができる：

  > new URLSearchParams([['x', 'a'], ['y', 'b&y=c']]).toString()
  'x=a&y=b%26y%3Dc'
  > new URLSearchParams([['x', 'a&y=b'], ['y', 'c']]).toString()
  'x=a%26y%3Db&y=c'

• sub-delims が + を含むことが form data のスペースを + にエンコードする実装を許している一方、そのために form data の + を %2B にエンコードすることと直接の関係はない。

すなわち reserved characters は勝手に encode, decode されないという仕様であって、一律に使うなと言われているわけではない。実際、RFC 3986 が query について定める範囲では

pchar         = unreserved / pct-encoded / sub-delims / ":" / "@"
query       = *( pchar / "/" / "?" )

なので #[] 以外の reserved characters は使用が想定されている。

微妙なところとしては "specifically allowed by the URI scheme to represent data in that component" でなければ送信は厳格に受信は寛容にと（いつものパターンで）書かれている。こうなると RFC 3986 に閉じた話でなくなり、現実は WHATWG に反映されているはずなのでそちらを見ると、

• URL.search は single quote ' も http(s) を含む一部 scheme でエンコードしているのでこれだけは何か事情がありそう。
• application/x-www-form-urlencoded のデコードでは &=+ 以外は percent decode するだけなので、他に特別な意味を持つ記号がない前提で寛容な受信をしているようだ。
• application/x-www-form-urlencoded のエンコードで * がそのままなので、意味を持たない記号として定義されているとみなせるかもしれない。

---

ちなみに URL に現れない printable ASCII は"<>\^`{|} の 9 文字。これに加え

• # fragment 開始専用
• % percent encoding 専用
• [] IPv6 (or later) を囲む専用

が除外されていることが古い仕様書では説明されている。https://datatracker.ietf.org/doc/html/rfc2396#section-2.4.3

最近の仕様書には使える文字のほうのリストしかないようだ。https://url.spec.whatwg.org/#url-code-points

---

また、 encodeURIComponent についてはどの scheme のどの component に使うか分からないから reserved character すべてをエンコードする仕様だったほうが適切という主張に理がある。（sub-delims の差なので「URL の」パース結果が変わるようなひどいことにはならないが。）

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/encodeURIComponent#encoding_for_rfc3986

URL の query 部分に限って言えば form data から * がそのまま入る仕様を消すとしてもさらに十分な時間が経つまでは * に別の意味を持たせる状況は考えにくいので URLSearchParams が将来の標準に沿っているかの点でも懸念は少ないだろう。

戦力を3つに分けて2勝したら勝ちのゲームのナッシュ均衡

概要

• 「分割して番勝負」はゲームの基本的なメカニクスの1つだと思うが、知っていたのは三すくみを含んでいることくらいで、考察したことがなかった。
• こういう具体例を計算してみると、ナッシュ均衡の特徴付けのどれが便利かが分かってくる。
• 正六角形（内側を含む）の上の確率分布で辺に垂直な成分への射影がどれも（長さ√3の）線分上の一様分布となるものを挙げよ。

経緯

課金ゲームを無課金で遊んでいたら、レベルカンストで3編成作るのが難しいという困難が発生して、3つに分ける部分がそれなりに重要になってしまう。

ボードゲームでこのタイプの判断が出てくることもよくある。リソースを今使うか後で使うかということ。どちらかというと前の勝敗を見てから後の分割を決めてよいルールになりがちなので違うゲームだが今回は考察しない。

ゲームのメカニクスは構成要素にすぎないが、それぞれの要素について考察しておくと有用そうな気がしたので、最も簡単な「3つに分けて2本とったら勝ち」だけのゲームを解いてみよう。

定式化

（純粋）戦略 $(x, y, z) \in \Delta = \lbrace x + y + z = 1, x ≥ 0, y ≥ 0, z ≥ 0\rbrace$ 上の零和ゲーム。利得は $\mathrm{sign}(x - x') + \mathrm{sign}(y - y') + \mathrm{sign}(z - z')$ で与えられる。

• ゲームの例として紹介されるときは「石100個を分けて、〜〜」などとされるが連続にした。
• 勝敗数から線形に利得になることを用いた。
  • 「2勝以上したら勝ち」と表現されがちだが、全勝できないので。
  • 4つ以上に分けるときや合計値が不公平なときは今回のようにはできない。
  • 一方、「サイコロの目を書いて振る」ようなゲームなら分割数（何面ダイスか）によらずこのように扱える。(0, 3, 3) > (2, 2, 2) > (4, 1, 1) > (0, 3, 3) の三すくみがあることは有名（漫画のネタで使われているのも見た）。

混合戦略のナッシュ均衡が存在するかについては、コンパクト集合上の連続関数なら良かったはずで、今回は符号関数 sign が不連続だが sigmoid にかえた場合は存在することは言える。その極限っぽいが存在だけを先に厳密に示す方法はよく分からない。なお、以下で実際に構成できるので良い。

必要条件をつめる

ナッシュ均衡の存在定理を勉強したときには補題がいろいろあったり、どれが重要な特徴付けなのか記憶に残らなかったのだが、実際に手計算していると決まったテクがあるように感じられてくる。（コンピュータで解く場合のアルゴリズムについては私はあまり詳しくないがCounterfactual Regret Minimizationがよく使われているかもしれない。）

ナッシュ均衡を手計算するテクを一言でまとめると、混合戦略であって純粋戦略に exploit されないものを探すと良い。

• 例1：じゃんけん。対称零和ゲームなので目標の利得は0。ナッシュ均衡になりうる混合戦略（それぞれの手を出す確率）を(p, q, r) (p+q+r=1)とおくと、相手の手に対して q−r≥0, r−p≥0, p−q≥0 を得るので p=q=r=1/3 である。

• 例2：利得行列 $\begin{pmatrix}1 & -1 \newline -2 & 2\end{pmatrix}$ の零和ゲーム。行を選ぶプレイヤーの混合戦略を (p, q) とおくと、 min(p−2q, −p+2q) を最大化したいので (p, q) = (2/3, 1/3) のとき最大値 0 を得る。同様に列を選ぶプレイヤーの混合戦略 (1/2, 1/2) が求まりこれらについてナッシュ均衡となる。

  • ところで、ある漫画で例2のゲームについてナッシュ均衡と異なる戦略がセオリーとされていたが、人の直感の当てにならなさを表していたのか、キャラの頭の悪さを表していたのか、作者が知らなかっただけなのかどれだろう。

• 補足：手番が1度きりのゲームのみここでは扱っているが、複数回の手番があるゲームでも、相手の純粋戦略のみ考えればよい。すなわち、どの状態でも相手は非確率的に選択するとしてよい。

では3つに分けて2勝するゲームを考えていこう。対称零和ゲームなので 0 にできれば良い。混合戦略を表す $\Delta$ 上の確率分布 μ(x, y, z) と相手の純粋戦略 $(a, b, c)\in\Delta$ について満たすべき条件は

ただし確率分布 μ(x, y, z) の射影（同時分布に対する周辺分布）を μ(x), μ(y), μ(z) とおいた。さらにcdf（累積分布関数）を f(x), g(y), h(z) とおけば、 $f(a) + g(b) + h(c) \le 3/2$ と同値（厳密にはcdfが端点を1/2だけ算入するように定義をいじる必要があるが）。

また、 x+y+z = 1 だったので、cdfたちは $\int f(x)\mathrm{d}x + \int g(y)\mathrm{d}y + \int h(z)\mathrm{d}z=2$ を満たす。なぜなら、

構成

ここからは予想して証明する感じになっていく。

$f(x) + g(y) + h(z) \le 3/2 \;(x+y+z=1)$ を満たしつつ f, g, h を大きくしようとすると、 f(x) = g(x) = h(x) = min(3x/2, 1) くらいしかないと予想できるので、こうなる分布 μ を構成したい。

言い換えると、正六角形 $\lbrace x+y+z=1, 0\le x\le 2/3, 0\le y\le 2/3, 0\le z\le 2/3\rbrace$ 上の分布で、それぞれの成分が [0, 2/3] 上の一様分布であるものがほしい。

ここで何らかのひらめきにより、 (2/3, 1/3, 0), (0, 2/3, 1/3), (1/3, 0, 2/3) を結ぶ正三角形の周上の一様分布（$\mu_1$ とおく）が条件を満たすことが分かる。このゲームをするように迫られた場合の実用上はこの戦略でとりあえず損しないので覚えておくと良さそう。

別のひらめきにより、正六角形の辺からの距離が辺と中心の距離 (= √6/6) の (1-t) 倍である点の確率密度を t に比例するようにした分布（$\mu_2$ とおく）も条件を満たすことが分かる。実際、 $$ t^{2} + 2\int_{t}^{1} s\mathrm{d}s = 1 = \textrm{const.} $$

分布 μ1, μ2

唯一性

このようにナッシュ均衡は唯一ではないが、「内側含む正六角形上の分布で3つの射影がすべて一様」という特徴付けが正しいことは以下のように示せる。

2個めに紹介する有用なテクとして、強そうな戦略が見つかったら相手に代入すると良い。（今回は対称なのでそのまま代入しているが、一般には考察するプレイヤーがここで入れ替わる。）

言い換えた条件の側でいえば、見つけた戦略（確率分布）$\nu=\mu_1$ や $\nu=\mu_2$ で $f(x) + g(y) + h(z) \le 3/2$ を積分することを意味し、 $$ \begin{aligned} \frac{3}{2} &\ge \int_\Delta (f(x)+g(y)+h(z))\mathrm{d}\nu(x,y,z) \newline &= \int f(x)\mathrm{d}\nu(x) + \int g(y)\mathrm{d}\nu(y) + \int h(z)\mathrm{d}\nu(z) \newline &= \frac{3}{2} (\int_0^{\frac{2}{3}}f(x)\mathrm{d}x + \int_0^{\frac{2}{3}}g(y)\mathrm{d}y + \int_0^{\frac{2}{3}}h(z)\mathrm{d}z) \end{aligned} $$ が分かる。 f ≤ 1, g ≤ 1, h ≤ 1, $\int f(x)\mathrm{d}x + \int g(y)\mathrm{d}y + \int h(z)\mathrm{d}z=2$ を思い出すと ν 上確率1で等号成立して $f(x) + g(y) + h(z) = 3/2$ となっている。$\nu = \mu_2$ のほうを用いると内部を含む正六角形上ほとんどいたるところで成立するので、あとは単調性と加法性から線形性を示す関数方程式でよくある議論をすれば f(x) = 3x/2 (0 ≤ x ≤ 2/3) などが出る（はず）。

あとがき

相手を純粋戦略として良いことと、相手にうまい混合戦略を代入すると良いことを紹介した。これらは相反して見えるが、ナッシュ均衡の同値な定義は形式上近い一方うまい使い方に違いが出るということだと思う。

記事を書いていて、線形計画法あたりの分野で知られている話題なのではと思った。（仕事じゃないから先行研究調べないのが許されている。自分で考えるのは楽しい。）

ナッシュ均衡の例を挙げ、そこそこの必要条件を出しただけなので、均衡 (μ, ν) 全体のなす空間をうまく書けるかは未解決。別のfuture workとしては分割前の戦力が不公平な場合や分割数が4以上の場合などがある。知っている方、計算した方がいたら教えてください。

ナッシュ均衡をしっかり手計算したのは、ポーカーのベット部分だけをうまく簡略化して解けないかな、とか考えていたとき以来。結局何回もレイズできる場合を解けずに放置してしまっていて悔しい。

heads-up preflop only game の厳密解の議論を探したのに出てこず、（ポーカーの教科書的なものを読まずに）まずは raise 1回までの場合とかを自分で解こうとしていたけれど、解かれてしまった……。https://t.co/enVvO6DPYc

— tos（とす） (@toslunar) August 8, 2022

実際のゲームに適用するには、混合戦略のナッシュ均衡が何を意味するか理解しているほうが良く、よくある誤解への解説がこれもmaspyさんのポーカー記事にまとまっている。

AtCoder で Option も Result も ? で .unwrap() する

競技プログラミングでの Rust のつらさのひとつに .unwrap() と9文字も書くのがだるいというのがあります。エラー伝搬は ? 1文字なのでエラー無視も楽に書きたいところですが、この記事にあるように stable Rust が入っている競プロサイトでは無理そうに見えます。ところが、実はできます。¹

fn main() {
    main1().ok().unwrap()
}
fn main1() -> Result<(), Never> {
    // ここにメインの実装
    dbg!("foo 42 bar".split_ascii_whitespace().nth(1)?.parse::<i32>()?);
    Ok(())
}
enum Never {}
impl<E: std::fmt::Debug> From<E> for Never {
    fn from(e: E) -> Self {
        panic!("unwrap ?: {:?}", e)
    }
}

解説

現在の AtCoder 上の Rust はコンパイラのバージョンが 1.42.0 なので ? の仕様は (v2 になる前の) try_trait です。ここで Option に ? して Result を early-return するための型 std::option::NoneError は #[feature(try_trait)] がないと名指しできないのですが、 Debug トレイトを持つすべての型からの変換なら stable の範囲で書けるため、 From<NoneError> が実装できてしまいます。標準的に使われるエラーは std::error::Error トレイトなので Debug + Display 以上と分かっているし fn binary_search(&self, x: &T) -> Result<usize, usize>² のように「エラー」ではない Result もだいたい Debug です。

ちなみに try_trait_v2 では専用の FromResidual トレイトを実装する必要がある³のでこういう抜け穴はありません。

main 関数に書きたい場合

fn main() -> Result<(), Never> {
    // ここにメインの実装
    Ok(())
}
#[derive(Debug)]
enum Never {}
impl<E: std::fmt::Debug + Clone> From<E> for Never {
    fn from(e: E) -> Self {
        panic!("unwrap ?: {:?}", e)
    }
}

Never: Debug にするとそのまま main にできるのですが、 T: From<T> との重複実装が許されないため、変換できるエラー型を絞る必要があり、たとえば Debug + Clone を課すと良さそうです。 std::marker::PhantomPinned を用いて Never: Debug + !Unpin にして E: Debug + Unpin にできれば使い勝手良くなりそうですが、なぜかできませんでした (T: From<T> との重複判定が消えないため)。

---

1. .unwrap() を直接書く場合と比べるとエラー時に表示されるソースコード位置が変わってしまう問題はあります。 RUST_BACKTRACE=1 で1つ下を見ましょう。↩

2. partition_point が 1.52.0 からなので AtCoder では仕方なく使ったりします。↩

3. try_trait_v2 については以前の日記にも書きました。 https://toslunar.hatenablog.com/entry/2021/08/03/230856↩

Rust の Iterator で cumsum をどう書くべきか、あるいは map の闇

Rust の Iterator で cumsum をどう書くべきか、あるいは map の闇

最近、競プロ典型90問を解いて競プロのリハビリ兼 Rust 練習しています。

Iterator::scan の謎

cumulative sum といえば Haskell でいう scanl 0 (+) だと思っているので it.scan(0, |a, b| a + b) と書けば良いだろうと scan を見に行くと、予想に反する型がついている。型は少し省略して書くと

fn scan<St, B>(
    self,
    initial_state: St,
    f: impl FnMut(&mut St, Self::Item) -> Option<B>,
) -> impl Iterator<Item = B>

なのだが、 St と B が異なっていることからも分かるように 0 番目に initial_state を返す実装ではないのが残念だし、逆に長さを縮める機能を Option を返すことで実装しているのも意図が分からない。

つまり、後者の目的で scan を使うくらいなら map_while (since 1.57) で十分だし、 _while 要素もないので map (FnMut(Self::Item) -> B を渡す) で良く、 cumsum は

std::iter::once(0)
    .chain(it.map({
        let mut s = 0;
        move |a| {
            s += a;
            s
        }
    }))

となる。

Iterator と FnMut

副作用のある関数を書いて良いのが盲点で、実際そういう言語だから map という名前で

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

あるいは mapM 相当だと思っておくのが自然だった。 Rust だと state monad 使う面倒さがなくて楽。めでたしめでたし。

とはいえ、 Fn/FnMut/FnOnce の区別みたいなところでも mut ref は unique ref という話みたいな対応もあって、 API 設計の意図が mut 側か unique 側かは分からない。副作用があっても実装が変わらないから FnMut とも言えるし、必要条件の側を考えて「同時に callback が呼ばれないから Fn を課す必要はなく、 Option::map などと違って 2 回以上呼ばれるかもしれないから FnOnce では足りない」という理由で FnMut になっているとも言える (これらは言い方が違うだけ)。

DoubleEndedIterator

Rust の Iterator のうち一部は後ろからも値を取り出せる (next_back)。たとえば、よく書くのは for i in (0..n).rev() だが、全部読んで Vec::reverse のような実装ではなく end -= 1 を返すような効率の良い実装が呼ばれる (std::ops::Range<A> については Iterator ならば DoubleEndedIterator)。

さて、 Iterator::map のドキュメントをよく見るともとの iterator が DoubleEndedIterator なら map 結果も DoubleEndedIterator を実装するらしい。見るからに副作用がやばい。そう思ってドキュメントを確認するともっと目立つところに具体例付きで注意書きがある。上の cumsum 実装も同じ理由で .rev() などすると壊れる。

.map(f).rev() は .rev().map(f) に直すように lint 出ても良いくらいだと思うが、 DoubleEndedIterator は 1 回 rev して終わりと限らず両端から自由な順序で取り出す想定の API だから pure function で map して DoubleEndedIterator を保ちたい用途がないとも言い切れない。

advanced_by

ところで、 for i in (0..n).step_by(k) は上限と modulo を指定できて便利なだけでなく O(n/k) 時間で動く。これは Iterator (required method は next のみ) は nth を自動実装しているが std::ops::Range が O(1) 時間の nth を与えることで実現されている。

自分で .map(f).rev() と書くことはないはずだが、 .map(f).step_by(k) は書きかねないので、 rev がやばいのなら step_by もやばいのではと思って調べたところ、これはセーフ。

Iterator::map が副作用無視の nth の高速化をしないことが保証されているか気になって iterator map nth で GitHub issue を検索したら advanced_by (unstable) の tracking issue の中で議論されていた。 map の副作用の注意書きすでにあるし nth でも副作用飛ばそうぜみたいな意見もあって一応予断を許さない雰囲気はちょっとある。競プロに限らなければ順序不定でもよい副作用とか消えても良い副作用とかいろいろあるので対立もやむなし。

立場をあえて明確にすれば自分は現状に賛成。 DoubleEndedIterator::rev は subtrait として分かれているから自己責任で、 Iterator::step_by が自動実装と挙動が違ったらやばすぎるみたいな裁定で正しいと思う。 Iterator::last は DoubleEndedIterator::next_back ではないし Iterator::count は ExactSizeIterator::len ではない。

AtCoder で cumsum したいとき

自分で書きたくないなら itertools_num::ItertoolsNum::cumsum か ndarray::ArrayBase::accumulate_axis_inplace を使えばよさそう。いずれも最初に 0 をつけたい場合はいじる必要あり。

cumsum を書く場合は map 後すぐ collect_vec() しておけば罠を踏むリスクはない。そもそも、ライブラリ整備せずその場で書くとなれば短いのが強く、

let mut s = vec![0];
// let n = a.len(); // 別のところで入力しているはず
// s.reserve(n); // Rustでそんなにパフォーマンス気にせずともACとれるはず
for i in 0..n {
    s.push(s[i] + a[i]);
}

とするか、 i, n の typo を避けて

let mut s = vec![0];
for a in &a {
    s.push(s.last().unwrap() + a);
}

にしそう。